J-C Bermond

M Cosnard

D Coudert

F Havet

Groupage sur le chemin pour borner la largeur de coupe †

Keywords: largeur de coupe (cutwidth), groupage, densité

La largeur de coupe (cutwidth) est un paramètre utilisé dans de nombreux problèmes d'ordonnancement linéaire (layout). Calculer la largeur de coupe est un problème NP-complet, mais il est possible de concevoir des algorithmes de branch-and-bound efficaces si on dispose de bonnes bornes inférieures pour couper des branches lors de l'exploration. Savoir évaluer rapidement de bonnes bornes dans chaque noeud de l'arbre de recherche est donc crucial. Dans cet article, nous donnons de nouvelles bornes basées sur différents paramètres de densité du graphe. Nous donnons aussi une borne inférieure basée sur le groupage de requêtes sur le chemin.

Introduction

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a layout of an input graph in such way that a certain objective cost is optimized. A layout of a graph G is a linear ordering σ = (v 1 , . . . , v n ) of the vertices of G. A large amount of relevant problems in different areas can be formulated as graph layout problems (see the survey [START_REF] Díaz | A survey on graph layout problems[END_REF] and references therein).

The edge-cut of a set X ⊆ V is the set of edges with one endvertex in X and one endvertex in X = V \ X. Its size is denoted by ec(X, X). Let X i = {v 1 , . . . , v i }. The width w(G, σ ) of a graph G with respect to the layout σ is the maximum of ec(X i , X i ) over all i ∈ {1, . . . , n -1}. The cutwidth of a graph G, denoted by cw(G), is the minimum width of a layout : cw(G) = min{w(G, σ ) | σ layout of G}.

The cutwidth was first used as a theoretical model for the number of channels in an optimal layout of a circuit in the seventies. In general, the cutwidth of a graph times the order of the graph gives a measure of the area needed to represent the graph in a VLSI layout when vertices are laid out in a row. More recent applications of this problem include network reliability, automatic graph drawing, information retrieval and as a subroutine for the cutting plane algorithm to solve the traveling salesman problem. Due to its natural definition, the cutwidth has various applications in computer science : whenever data is expected to be roughly linearly ordered and dependencies or connections are local, the cutwidth of the corresponding graph is expected to be small. However, computing the cutwidth of graphs is NP-hard [START_REF] Díaz | A survey on graph layout problems[END_REF] in general. Fixed-parameter algorithms have also been designed (see [GPR + 19]). Furthermore efficient branch-andbound algorithms have been designed (see [START_REF] Martí | Branch and bound for the cutwidth minimization problem[END_REF]) but they need to have good lower bounds for the cutwidth, and in particular bounds that can be quickly evaluated at each node of the branch-and-bound tree. The quality of these bounds have a strong impact on the performances of the branch-and-bound algorithms.

In this paper, we first review previous lower bounds on the cutwidth of a graph G. Next, we introduce new lower bounds based on the maximum, minimum or maximum average degree of G. Note that all these parameters can be computed in polynomial time. Moreover, the bounds are mostly incomparable and hence are complementary. Finally, we give a new lower bound based on the results obtained for the Maximum All request Path Grooming problem [START_REF] Bermond | Optimal Solution of the Maximum All Request Path Grooming Problem[END_REF], a problem also known as the Call Control Problem in Path Networks in [START_REF] Adamy | Call control in rings[END_REF].

Consider the path

P σ = v 1 • • • v n associated to σ .
For each edge e ∈ E(G), the request associated to e by σ , denoted by R σ (e), is the subpath of P σ whose endvertices are those of e. Let R σ (G) be the set of requests associated by σ to the edges of G. Observe that the load of the edge v i v i+1 in P σ under R σ (G) denoted l(v i v i+1 ) is the number of edges v j v ℓ of G with j ≤ i and i + 1 ≤ ℓ, that is ec(X i , X i ). Hence w(G, σ ) is the maximum load of an edge of P σ under R σ (G).

The grooming factor C is the maximum load that is allowed on the edges of P. Given a grooming factor C, the maximum number of requests that can be satisfied (or groomed) together on P such that the load of any edge is at most C is denoted by T (C, n). We show that, if G is a graph with n vertices and m edges, then cw

(G) ≥ C * (m, n) = min {C | m ≤ T (C, n)}.

Previous lower bounds

Several lower bounds on the cutwidth of graphs have been proposed in [DPS02, JM92, Klo10, MPDP13].

Bound based on minimal edge-cuts. From the definition of the cutwidth, it is obvious that the minimum size of an edge-cut between any pair u, v of vertices of the graph, which we denote by κ ′ (u, v), is a lower bound on its cutwidth (see [START_REF] Díaz | A survey on graph layout problems[END_REF] for more details). So, we get :

cw(G) ≥ max{κ ′ (u, v) | u, v ∈ V, u ̸ = v} (1)
Bound based on spectral property. Let λ 2 denote the second smallest eigenvalue of the Laplacian matrix associated with the graph. The following lower bound is due to [START_REF] Juvan | Optimal linear labelings and eigenvalues of graphs[END_REF] :

cw(G) ≥ λ 2 n n 2 n 2 (2)
Bound based on the degeneracy. A graph G is k-degenerate if every subgraph H of G has minimum degree at most k. Equivalently, G is k-degenerate, if there exists a layout (v 1 , . . . , v n ) such that for all i ∈ {2, . . . , n} every vertex v i has at most k neighbours in {v 1 , . . . , v i-1 }. The degeneracy of G, denoted by δ * (G), is the smallest k such that G is k-degenerate. The following lower bound is proved in [START_REF] Kloeckner | Cutwidth and degeneracy of graphs[END_REF].

cw(G) ≥ 1 4 δ * (G)(δ * (G) + 2) (3)
3 New lower bound based on degrees Bound based on the maximum degree. Let ∆(G) denote the maximum degree of G. Let v i be a vertex with degree ∆(G). One set among {v 1 , . . . , v i-1 } and {v i+1 , . . . , v n } contains at least half of the neighbours

of v i . Consequently, cw(G) ≥ ∆(G) 2 (4)
Bound based on the minimum degree. Let δ (G) denote the minimum degree of G.

Set k = ⌊δ (G)/2⌋+1 and let X k = {v 1 , . . . , v k }. Every vertex in X k has at most k -1 = ⌊δ (G)/2⌋ neighbours in X k and so at least ⌈δ (G)/2⌉ neighbours in X k . Hence ec(X k , X k ) ≥ k⌈δ (G)/2⌉ = (⌊δ (G)/2⌋ + 1)⌈δ (G)/2⌉. Thus cw(G) ≥ (⌊δ (G)/2⌋ + 1)⌈δ (G)/2⌉ ≥ 1 4 δ (G)(δ (G) + 2) (5)
As δ * (G) ≥ δ (G), the bound of Eq. ( 3) is better than the bound of Eq. (5). However by definition of degeneracy, there is a subgraph H of G such that δ (H) = δ * (G). Since cw(G) ≥ cw(H), Eq. (5) implies the bound of Eq. (3) (with a simpler proof than the original one [START_REF] Kloeckner | Cutwidth and degeneracy of graphs[END_REF]).

Bound based on the average degree. Let σ = (v 1 , . . . , v n ) be an ordering of V (G) and let X i = {v 1 , . . . , v i }.

For each vertex v i , let d + (v i ) be the number of edges (v i , v j ) with j > i (forward edges from v i ).

Proposition 1 w(G, σ ) ≥ 1 n -1 n-1 ∑ i=1 d + (v i ) d + (v i ) + 1 2
Proof. We use a classical trick in grooming. We first compute the total load of G on

P σ = v 1 v 2 . . . v n , also called sum cut of the layout σ [DPS02], which is L(G, σ ) = ∑ n-1 i=1 l(v i v i+1 ) = ∑ n-1 i=1 ec(X i , X i ).
To compute L(G, σ ), we note that the load of the forward edges of G from v i is at least d + (v i ) on the edge v i v i+1 , at least d + (v i ) -1 on the edge v i+1 v i+2 and so on. Therefore the load due to the edges from v i is at least

1 2 d + (v i )(d + (v i ) + 1) and the total load is at least 1 2 ∑ n-1 i=1 d + (v i )(d + (v i ) + 1
). Then we note that, as the path has n -1 edges, there exists an edge with load at least L(G,σ ) n-1 and so w(G, σ ) ≥ L(G,σ ) n-1 . 2

The average degree of a graph G with m edges and n vertices is

Ad(G) = 2m/n. If a function f (x) is convex and if ∑ n-1 i=1 x i = m, then the minimum of ∑ n-1 i=1 f (x i )
is attained when all the x i are equal to m/(n -1). Applying this argument to the convex function x → x(x + 1) with x i = d + (v i ) and using the fact that ∑ n-1 i=1 d + (v i ) = m, we get :

cw(G) ≥ 1 2 m n -1 m n -1 + 1 = 1 8 1 + 1 n -1 2 Ad(G) Ad(G) + 2 - 2 n (6)
The maximum average degree of G is Mad(G) = max{Ad(H) | H subgraph of G}. Observe that this parameter can be computed in polynomial time. By definition of Mad, there is a subgraph H of G such that Ad(H) = Mad(G). Since cw(G) ≥ cw(H), Eq. ( 6) directly implies

cw(G) ≥ 1 8 1 + 1 n -1 2 Mad(G) Mad(G) + 2 - 2 n (7)
The bounds given by Eq. ( 6) and Eq. (3) are incomparable. Indeed, on the one hand, there exist graphs with bounded average degree and degeneracy as large as we want. For example, take a complete graph of order k + 1 and a path of length p and identify a vertex of each. Then the degeneracy is k but the average degree tends to 2 when p tends to infinity. So for p large, the bound of Eq. (3) is better. On the other hand, consider the graph G where vertex i is joined to the s vertices i + h, 1 ≤ h ≤ s with i + h ≤ n. Then its degeneracy is s (consider the layout (v 1 , . . . , v n )), but we have m = sns(s + 1)/2 and so for n large the bound of Eq. ( 6) is better.

The following tight inequalities are well-known (see e.g. Proposition 3.1 of [START_REF] Nešetřil | Sparsity : graphs, structures, and algorithms[END_REF]) : δ * (G) ≤ Mad(G) < 2δ * (G). Thus the bounds given by Eq. ( 7) and Eq. (3) are incomparable. The lower bound of Eq. ( 7) is better than the bound of Eq. (3) when Mad(G) > √ 2δ * (G) and worse in the other case.

A lower bound using the grooming on the path

Let σ be a layout of G such that w(G, σ ) = cw(G). As w(G, σ ) is the maximum load of an edge of

P σ under R σ (G), we have T (cw(G), n) ≥ m, and so cw(G) ≥ C * (m, n) = min {C | m ≤ T (C, n)} (8)
Note that the bound is reached by taking as edges of G the pairs of endvertices of T (C * (m, n), n) requests that can be groomed on a path of n vertices with grooming factor C * (m, n).

A closed formula for T (C, n) as been given in [START_REF] Bermond | Optimal Solution of the Maximum All Request Path Grooming Problem[END_REF]. We shall use it to determine C * (m, n).

Theorem 2 ([BCCP06]) Let n and C be fixed positive integers.

-If n is odd and n

2 -1 8 ≤ C ≤ n 2 -1 4 , then T (C, n) = (n-1) 2 4 +C ; -If n is even and n(n+2) 8 ≤ C ≤ n 2 4 , then T (C, n) = n(n-2) 4 +C ; -Otherwise, let C = C s -d with C s = s(s+1)
2 and 0 ≤ d < s ; n = qs + r with 0 ≤ r < s ; r = aq + α with 0 ≤ α < q ; sr = b(q + 1) + β with 0 ≤ β ≤ q ; T s = sn -C s ; A s = ar -a(a+1) 2 q and B s = (b + 1)(sr) -b(b+1) 2 (q + 1). We have T (C, n) = T sdq + min {A s + d, B s }. One could think that an optimal solution can be obtained by greedily selecting all requests of length 1, then all requests of length 2, and so on until the capacity limit C is reached. But that is true only for C ≤ 9.

In particular, one could have expected that, for C = C s = s(s + 1)/2, an optimal solution would be obtained by taking all the requests of size at most s in number T s = sn -C s (example at the end of Section 3). But it is not true for n = 11 and C = 10 (s = 4). The solution with all the requests of size at most 4 has T 4 = 34 requests. The maximum load is 10, but it is reached only for the edges of the path v 1 • • • v 11 of the form v i v i+1 with 4 ≤ i ≤ 8. So we can delete the request of length 4 : v 4 • • • v 8 and add the two requests of length 5 v 1 • • • v 6 and v 6 • • • v 11 to get a solution with 35 > T 4 requests. In that case, we say that we have an anomaly.

We did not find yet a simple closed formula for C * (m, n), but in some cases it is computed easily. For example, if n -

1 < m ≤ 3n-3 2 , then C * (m, n) = 2. Similarly, if 3n-3) 2 < m ≤ 2n -3, then C * (m, n) =
3 and so on. The computation would have been easier if there were no anomalies. Fortunately, we can have good approximations by using results of [START_REF] Bermond | Grooming on 3 or 4 paths with a common vertex[END_REF]. As example, for C = C s = s(s + 1)/2, we have T s ≤ T (C s , n) ≤ T s + An * (C s ) where T s is the value obtained by taking all the requests of size s and An * (C s ) represents the number of anomalies. A good upper bound on An * (C s ) ≤ (5 -2 √ 6)C S is given in [START_REF] Bermond | Grooming on 3 or 4 paths with a common vertex[END_REF]. One can show that the bound given by Eq. ( 8) is better than that of Eq. (6).

Proposition 3 C * (m, n) ≥ 1 2 m n-1 m n-1 + 1 Proof. According to the definition of C * (m, n), it suffices to prove that, for C = C b = 1 2 m n-1 m n-1 + 1 , we have T (C b , n) < m.
We give here the proof when m/(n -1) is an integer s. In that case, C b = C s = s(s+1) 2 and so T (C b , n) = sn -C s . On the other side m = sns. As C S > s for s ≥ 2, we get T (C b , n) < m. The proof is a more involved when m/(n -1) is not an integer but works by taking s = ⌈m/(n -1)⌉.

2

The gap between the bounds can be significant. For example, C * (21, 8) = 9 while Eq. ( 6) gives 6. If we take s = 10 (C 10 = 55) and n multiple of 21, according to [START_REF] Bermond | Optimal Solution of the Maximum All Request Path Grooming Problem[END_REF] there are no anomalies and so T (C 10 , n) = 10n -55. For n = 42, T (C 10 , 42) = 365. But for m = 365, Eq. ( 6) gives a value of 44.07 ≪ 55.

Lower bounds in branch-and-bound algorithms can be computed quickly by using C * (m, n) (or a good approximation) or the bounds of Eq. (6) or Eq. (5). We can also use the better bound of Eq. (7) but it needs the computation of Mad(G) which is polynomial but long in practice. We can also use an improvement of Eq. (8) by noting that cw(G) ≥ cw(H) for any subgraph H of G and so cw(G) ≥ max{C * (m H , n H ) | H subgraph of G} (9)

In particular, we can compute the bound only for a subgraph H 0 such that Ad(H 0 ) = Mad(G) and so cw(G) ≥ C * (m H 0 , n H 0 ). By Proposition 3, this bound is better than that of Eq. (7).

In conclusion, it appears that the bounds given in this section are better than the bounds based on degrees. Our next step will be to design fast algorithms for computing the bounds of Eq. (8) and Eq. (9).

† This work has been supported by IDEX UCA JEDI (ANR-15-IDEX-01) and the ANR project MULTIMOD (ANR-17-CE22-0016).


CARTAPANIS

Commentaire :

Le 20 décembre 2023, la Commission européenne a accepté les engagements proposés par Amazon et qui faisaient suite à deux procédures formelles ouvertes à l'encontre du géant de la vente en ligne. Deux comportements distincts étaient en cause.

Le premier comportement était lié à l'utilisation, par Amazon, des données non publiques qu'elle récoltait sur les vendeurs actifs sur sa place de marché. L'on sait en effet que la plateforme a une double casquette : elle vend ses produits sur son site internet, et propose en parallèle une place de marché sur laquelle les vendeurs indépendants peuvent vendre des produits directement aux consommateurs. Or, selon la Commission, Amazon s'appuyait sur les données des vendeurs pour ajuster ses offres de vente au détail, ce qui pouvait fausser la concurrence sur la plateforme.

Quant au second comportement, la Commission craignait que la place de marché ne mette en oeuvre des pratiques d'auto-préférence susceptibles d'être analysées comme une discrimination de 2e rang en favorisant ses propres offres et celles de vendeurs ayant recours à ses services logistiques et de livraison dans l'accès à sa Buy Box et à son programme Prime, qui assurent une meilleure visibilité des offres et ont tendance à générer plus de ventes (sur ces questions, v. not. M. Malaurie-Vignal, Droit de la concurrence et algorithmes, JurisClasseur Concurrence -Consommation, n°139). Afin de mettre un terme à ces préoccupations de concurrence, Amazon a proposé trois types d'engagements. D'abord, et s'agissant des données non publiques relatives aux activités des vendeurs indépendants actifs sur sa place de marché, Amazon s'est engagé à ne pas les utiliser, tant par un système automatisé ou par ses employés, pour ses activités de vente au détail en concurrence avec ces vendeurs, et pour la vente de produits de marque ou pour la vente de produits de sa propre marque.

Ensuite, et en ce qui concerne la Buy Box, Amazon a proposé de mettre en place un traitement égal à tous les vendeurs lors du classement de leurs offres aux fins de la sélection du gagnant de la Buy Box, et d'afficher une seconde Buy Box concurrente de celle du gagnant. Enfin, et s'agissant de son offre Prime, l'entreprise s'est engagée : 1) à respecter un principe d'égalité de traitement pour l'éligibilité des vendeurs actifs sur la place de marché et des offres à ce programme ; 2) de permettre aux vendeurs qui bénéficieraient de ce programme le libre choix des transporteurs ; et 3) d'ouvrir le marché de la logistique en s'engageant à ne pas utiliser, pour ses propres services logistiques, d'informations obtenues grâce à Prime sur les conditions et les performances des transporteurs tiers.

Outre le recours à la procédure d'engagements, cette procédure invitera sans doute le juriste à s'interroger sur l'articulation future entre l'article 102 TFUE, la mise en oeuvre de l'article 9 du règlement 1/2003, et le Digital Market Act qui prohibe, rappelons-le, les pratiques d'autopréférence. À suivre donc… M. C

Chronique Pratiques unilatérales -Concurrences 2/2023 Comm. UE., Communiqué de presse, La Commission accepte les engagements offerts par Amazon l'empêchant d'utiliser les données des vendeurs actifs sur sa place de marché et garantissant l'égalité d'accès à la Buy Box (boîte d'achat) et au programme Prime, IP/22/7777, 20 décembre 2022

  La Commission européenne accepte les engagements proposés par une plateforme pour mettre fin à une pratique présumée d'auto-préférence (Amazon) Comm. UE., Communiqué de presse, La Commission accepte les engagements offerts par Amazon l'empêchant d'utiliser les données des vendeurs actifs sur sa place de marché et garantissant l'égalité d'accès à la Buy Box (boîte d'achat) et au programme Prime, IP/22/7777, 20 décembre 2022 Comm. Eur., 20 déc. 2022, Amazon, COMP/AT.40462 Comm. Eur., 20 déc.. 2022, Amazon, COMP/AT.40703 Commission accepts commitments by Amazon barring it from using marketplace seller data, and ensuring equal access to Buy Box and Prime, IP/22/7777 Comm. Eur., 20 déc. 2022, Amazon, COMP/AT.40462

	Marie
	Maître de conférences
	Aix-Marseille Université
	The European Commission accepts commitments offered by a platform to end an alleged self-
	preference practice (Amazon)
	Eur. Comm., press release,


domain: info stat

text:
Emmanuel Ledinot
email: emmanuel.ledinot@thalesgroup.com

Mekki-Mokhtar Amina
email: amina.mekkimokhtar@ansys.com

Gassino Jean
email: jean.gassino@irsn.fr

Philippe Quere
email: philippe.quere@stellantis.com

Ricque Bertrand
email: bertrand.ricque@safrangroup.com

Serratrice Franck
email: franck.serratrice@renault.com

A Geometric Perspective on ML Safety Assurance

Keywords: machine learning, ML reliability, safety assurance, ML assurance, latent manifold, extensional coverage analysis, Topological Data Analysis (TDA)

Some people claim AI-ML suffers from a reliability glass ceiling effect, around ~10 -2 /inference, that makes it incompatible with safety-criticality by several orders of magnitude. Others advocate that safety nets and development assurance will overcome this gap so that there is no real concern indeed. We propose an explanation to the reliability plateauing phenomenon based on geometry of approximant adjustment, and on ML verification practices. We advocate the need for a new field we coined as HR ML (Highly Reliable) and UHR ML (Ultra Highly Reliable). Relying on Topological Data Analysis in high dimensions, its aim is to supplement data-science pointbased verification with volume-based verification in order to meet the needed 10 -5 / inf. error rates (and beyond). We argue that process-based ML assurance and safety monitors alone will not overcome the reliability barrier. Our HR-ML concept for safety-related applications is a research proposition at the confluence of ML assurance and system assurance.

I. INTRODUCTION

Data analysis and statistics developed over centuries to extract synthetic information from population data as insights on complex phenomena. Inferential statistics focused on explanatory models of past observations, then used as predictors. Accuracy and consistency of estimators were the guarantees mathematics had to lay down. Never, until recently, had statistics to address safety-sensitive 'control'. We use 'control' in the broad sense of OODA loops (Observation, Orientation, Decision, Action), or any part thereof, where physics is involved with life, goods or environment exposition.

Machine Learning, especially Deep Learning (DL), opened a new era: unprecedented performances in machine vision and problem solving in higher dimensions, while being plagued by severe brittleness issues. Could DL, however, if supplemented with development assurance and faulttolerance, meet the requirements of safety-sensitive 'control'? We investigate this question. We consider safetysensitiveness (low to medium severity) and safety-criticality (catastrophic consequences). Our focus is limited to ML reliability, ML verification coverage, and to safety assurance of ML-dependent systems.

To our knowledge [START_REF] Alecu | Can we reconcile safety objectives with machine learning performances?[END_REF], the best image classification score obtained by ML on the MNIST benchmark is 3.10 -3 . From a safety assurance perspective, this reliability score is poor. To cope with this matter of fact, [START_REF] Alecu | Can we reconcile safety objectives with machine learning performances?[END_REF] screened the techniques amenable to improve ML reliability. They questioned the feasibility of reaching the levels required by the higher assurance levels and concluded negatively. After some scoping and terminological preliminaries, we summarize this survey. Then we propose geometric reasons to explain why the reliability enhancement methods uniformly failed (sections II, III, IV).

Are there any solution to this problem? We explain why software assurance will have no impact on it (section V), and why fault-tolerant architectures solve only the easy cases (section VI). At this stage, we conclude that for true MLdependent safety-sensitiveness and safety-criticality, there is no escape from improving ML reliability by orders of magnitude (3 to 5). Is it possible? From a geometric perspective, the complexity of the task is so high that there are many reasons to be hopeless. However, thanks to recent advances in Topological Data Analysis (TDA) in higher dimensions we propose to control sampling and adjustment more tightly. We coin 'HR-ML' (Highly Reliable) and 'UHR-ML' (Ultra Highly Reliable) this TDA-augmented and dependability-oriented variant of Machine Learning. As of writing this paper, we have no evidence to back the feasibility of our (U)HR-ML proposal. It is our best constructive and research perspective to overcome the reliability glass ceiling phenomenon.

Contribution: we propose a diagnosis on the MLreliability plateau. We ground it at the confluence of data science, topological data analysis and system safety assurance. We propose orientations to supplement the classical point-based approach with a more progressive and volume-based approach to sampling coverage and adjustment verification.

Disclaimer:

The views expressed in this paper are those of the authors as members of the Embedded France Working Group on safety assurance standards [START_REF]Embedded France Groupe de travail -NSL Normes pour la Sûreté de fonctionnement Logiciel et système -Embedded France[END_REF]. They do not reflect the opinion of their affiliations.

II. SCOPING ML-DEPENDENT SAFETY

A. System Perimeter

We address safety-sensitive and safety-critical embedded systems. Our prototypical use case in automotive is pedestrian detection systems coupled to automatic-braking systems. In aeronautics, autonomous flying cabs and drones are the MLdependent examples we have in mind. More generally, we consider ML-dependent vehicle control, formation control, product health monitoring (PHM), and all kinds of operational technologies (OT). We question the possibility of transitioning from ML-dependent advisory mode to MLdependent full-authority mode, by relying only on assurance and safety monitors to overcome the ML-reliability gap.

B. ML Perimeter

We consider off-line supervised learning in high to very high input-space dimension (e.g. the pixel count of the image feed to ML-classifiers, i.e. typically 10 4 to 10 6 and beyond). We exclude continuous learning. We exclude ML developments like ChatGPT. Regarding the ML-safety survey [START_REF] Hendriecks | Unsolved Problems in ML Safety[END_REF], we only address Robustness and Monitoring. Transformers, Q&A systems, representation learning, ethics, or Alignment are important issues out of scope of this paper.

III. TERMINOLOGICAL PRELIMINARIES

We recall a few definitions used in the sequel.

A. Machine learning

 Approximant, any function ℝ n → ℝ p , estimator of an underlying function specified by texts and datasets. We use 'ML-model' (after adjustment) as synonymous of fitted approximant.

 Inference, and generalization, are used as synonymous: activation of the approximant on an input vector not seen during the training, validation and testing.

 Ambient space, also named embedding space: the space where spread the vectors (or points) of the datasets. Depending on the context, we use "ambient space" for input only (nD), input-output ((n+p)D) or output only (pD) space.

 Latent space or latent manifold, the regions of ambient spaces where the sample points concentrate. Latent space has its own dimension named latent dimension.

 Dimension reduction. The classical interpretation is the process of identifying the input space features that are salient in conditioning the form of the output latent manifold (i.e. sensitivity analysis). It is used to select the prominent ones (e.g. PCA). We never use this meaning. We only consider ambient to latent dimensionality reduction, if any …, by shifting from external view of the latent manifold, to internal and intrinsic view of it.

B. Logics

 Extensional, qualifies extension as defined in "Extension Theory" [START_REF] Grassmann | Extension Theory[END_REF], i.e. vector encoding of magnitudes for geometric and algebraic calculation. Two approximants are extensionally equivalent when 1 Depending on this choice TDA uses different types of point to point-set distances: off-sets in the deterministic case, distributional (KL-divergence, Wasserstein, earth-move) in the statistical case.

they have the same external ("black-box") behavior, i.e. they form the same output space when exercised over their common input domain.

 Intensional, qualifies objects or sets defined by indicator functions. Intensional equality is Leibnitz equality : "no discriminative property". Intensional equality is 'white box' and implies extensional equality. The converse is false.

IV. ML-RELIABILITY GLASS CEILING

A. Reliability augmentation techniques

In [START_REF] Alecu | Can we reconcile safety objectives with machine learning performances?[END_REF], researchers investigated the means to improve ML reliability. Though ML made major progress over the last decade (1 to 2 orders of magnitude in accuracy), 10 -3 /inference is poor from safety perspective. The paper reviews quantitative results obtained by model diversification, monitoring (ODD, robustness, I/O consistency), by robustness enhancement techniques (model stability and training stability), by selective classification, conformal prediction, and temporal redundancy on sequences. The main conclusion is the following: all the methods that tried to increase reliability by redundancy of "independent" models, i.e. by independent hyper-parameters, independent datasets and independent optimization processes, succeeded marginally. Reliability stayed in the range of 10 -2 / inference instead of the expected 10 -4 = 10 -2 * 10 -2 or 10 -6 = 10 -2 * 10 -2 * 10 -2 . Moreover, all the listed techniques improved the reliability performance marginally at the expense of availability losses.

B. Common Cause Analysis

Strong correlation of inference errors between independently developed ML-models is an experimental fact evidenced by the studies reported in [START_REF] Alecu | Can we reconcile safety objectives with machine learning performances?[END_REF]. What could be the explanation? Our working hypothesis is that the complexity of the latent manifolds' forms to be fitted is the common mode between the so-called "independent" redundancies. Depending on the specific nature of the ML application to be developed, the adjustment problem and its associated assurance policy may be addressed in a deterministic geometric setting (smooth latent manifold) or 1 in a noisy aleatoric setting (statistical latent manifolds). We use this form as an example of regions hard to fit (surrounded by dotted-ellipses) and likely to cause poor inference reliability. This adjustment difficulty is (far) higher in higher dimensions. The MLmodel redundancies are intensionally independent. Our interpretation of the marginal gain is that the redundant approximants are extensionally correlated by the 'shape of the problem' to solve, i.e by the shape of the latent IO-manifold to adjust with. Fig. 2. 1D latent manifolds in 3D ambient space. Limiting generalization errors to extremelly small quantities (10 -k k ≥ 5).requires controlling regularization with extreme precision, first locally, and then globally.

Notice the impact of fitting variability on the projected curves (picture is courtesy of [START_REF] Giannelli | A local C2 Hermite interpolation scheme with PH quintic splines for 3D data streams[END_REF]).

When the approximant space is defined by the solution to (n -1) polynomial equations (n-variable-polynomials) the ambient space is nD, and the latent space is 1D. Given k points in the nD space, the existence of an interpolation curve linking these k points is still an open mathematical problem. By 2022, a proof of existence was published on the Web and is under peer-review [START_REF] Laurens | Un vieux problème de courbes enfin bouclé[END_REF]. In case of confirmation, more than a century will have been necessary to solve the (1-latent, n-ambient) case for an intensively investigated approximant space: the algebraic curves.

This example substantiates the complexity of function fitting in high dimension. Collision avoidance or drone control, or any real life ML application requires solving even more complex adjustment problems. We suggest that high reliability of adjustment necessitates tighter control of the complex geometric solving process than with current blackbox optimizers.

D. Zero-measure verification

Figure 2 visually suggests the difficulty of point-cloud fitting when only a few points are available. Information contained in dataset specifications is poor. Meeting failure rates as low as 10 -k /inference, k ≥ 5, is highly demanding. Sample-oriented by nature, statistical estimation of functions naturally relies on point-based verification. Verification coverage of an estimated continuous function (regressor or separator) by means of some N-sample-dataset is N*0=0 in volume. At the opposite, the nD volume over which the estimated function has to generalize with high reliability is gigantic. Even worse, the definition domain of approximant is … undefined. There is a great discrepancy between the limited control of adjustment, the absence of formal input-domain definition, and the inference reliability levels required by safety.

E. 'One-shot' global adjustment

Complexity of ML is high and may be compared to that of non-linear control. Shape complexity of phase spaces (differential geometry and differential topology) compels control engineers to start by designing local control laws (dynamic regimes), and to progressively 'glue' them by scheduling and switching up to covering the global reachable state space. Our guess is that ML ensuring high levels of inference reliability can't afford monolithic, "one-model-fitsall" global trade-off over a gigantic domain. Like for nonlinear control, (U)HR-ML is likely to necessitate a local-toglobal approach: the global model would be a scheduler of precisely fitted local models. Because of varying curvature, varying dimensionality, and complex varying topologies as illustrated on fig. 1, fitting reliably a single approximant, even over-parameterized and with high capacity, might be illusory. Possibly, for a situation like that of fig. 1, 10 -1 is reachable with a single ML-model, whereas one would need to schedule five local ML-models to meet a global 10 -4 target: three models for the three difficult twistetd and entangled regions, plus one model for each of the two remaining 'easy' parts.

V.

ML-RELIABILITY GAP FILLING BY SOFTWARE ASSURANCE?

Some people advocate that reliability of 10 -2 / inf. at ML model level could become 10 -5 / inf. after implementation, provided the software is developed under DAL A assurance. The reason would be that "DAL A development delivers high integrity software" and "high integrity software is 10 -k /h reliable".

The goal of software assurance is to ensure fidelity of the transformation process that converts a specification such as an ML-model (e.g. TensorFlow mathematical equations) into binary code instructions. Fidelity, also named compliance, means ensuring extensional equivalence between the MLmodel and its executable object code. In other words, regarding reliability of inference, DAL A ensures high trust on reliability invariance i.e. "garbage in, garbage out", not magic reliability augmentation during the translation flow.

Notice that explaining why there is no reliability augmentation with assured software is not bringing discredit on the value of software assurance. One may found more information on the link between qualitative and quantitative aspects of development assurance in [START_REF] Blanquart | Software safety assessment and probabilities[END_REF].

VI. ML RELIABILITY GAP FILLING WITH FAULT TOLERANCE?

We claim that safety nets can handle only the easy cases of ML-dependent unreliability in safety-sensitive or safetycritical systems. In other words, the cases where risk does not depend on the performance premium uniquely provided by ML techniques, especially Deep Learning.

Let us consider our pedestrian collision avoidance or GPSdenied drone landing examples. Deep Learning systems have by far outperformed any other classical certifiable approach in machine vision. If some classical and underperforming vision monitor is sufficient to ensure controllability, then the DLdependent channel provides just perception performance bonus (advisory mode, no true ML-dependent criticality). Otherwise, i.e. when ML-capability is mandatory to reach the required performance level, the monitor must have equivalent or just slightly lower performance, and thus cannot be implemented with classical underperforming machine vision. And in this case we face the above-mentioned issue that combining two independent ML models may not significantly improve reliability. Safety nets alone are not a solution to circumvent the reliability glass ceiling problem when one needs COM+MON dependence on ML's distinctive (but brittle) performance superiority.

VII. TDA-ENABLED (U)HR ML PROPOSAL

Let us recap where we are at this stage. We have proposed an explanation of the ML reliability gap (10 -2 /inference .vs. 10 -5 /inference or better): adjustment failure on higher dimensional difficult topological regions that correlate any number of so-called "independent" approximants. We have justified why reliability of generalization must improve to meet ML-dependent dependability requirements in the difficult cases. We are facing a single point of failure that cannot be prevented by development assurance, nor be passivated by monitors in the true ML-dependency cases. We advocate that improving ML reliability, i.e. shifting from ML to (U)HR-ML, is the only path to reach full-authority safetysensitive ML-dependent 'control' (DAL C and beyond).

Our last two sections are prospective. We propose means drawn from Computational Geometry (CG) and Topological Data Analysis (TDA) in higher dimensions [START_REF] Boissonnat | Geometric and Topological Inference[END_REF] to support High Reliability Machine Learning. In case of success, UHR-ML would follow along similar lines, but with ever-tighter sampling and adjustment control. Better awareness of adjustment's geometric (local) and topological (global) complexity is to our opinion the 'missing link' to meet the needed higher reliability levels on point-cloud generalization.

A. Semantics of emptiness

High dimensional void is the ambient space of training and test datasets. Emptiness around samples may result from principled design choices or from loopholes. Emptiness may be full of missing information that prevents from meeting the reliability target. We distinguish four types of voids:

1) Causal impossibility

Physics, scene or environment evolution laws, operational concepts or ODD constraints may prevent the generation of samples in definite regions of the input space. It leads to distant clusters i.e. to disconnected sums of sub-manifolds in topological language.

2) Sample incompleteness

The sampling plan or data-collection process, compliant with the ODD and with the ML-model's textual specification, may overlook some input space regions. Depending on local regularity and on approximation sparsity, these sampling lacuna may or may not constitute potential sources of inference errors.

3) Designed separability

In classification, separation and separators (i.e. intended void regions) may be looked after and engineered (e.g. SVMs).

4) Designed sparsity

When variance is assumed bounded (e.g. Lipchitz) and regularity is well understood, sampling and approximant structure may be sparse. Computation tractability and energy saving are the intended benefits of extensional and intensional sparsity. In that case, the intended voids are not sampling lacuna, there is no missing information.

In summary, regarding sampling coverage analysis, our TDA-enabled (U)HR-ML proposal deals with exploration of point-cloud forms to identify the shape of the higher dimensional voids (see fig. 5). In other words, it would consist in detecting the unintended informational lacunas as potential inference unreliability sources, or adjustment complexity sources. 2 In Distribution -Out of Distribution

B. Design of sample-interpretation hypotheses

TDA offers a portfolio of algorithms to analyze point clouds in 2D, 3D, and higher dimensions. We focus on persistence homology (PH) which plays a central role in TDA. In our context, Persistent Homology may be seen as a means to mesh the latent manifolds. It is used in ML for clustering and for feature engineering (e.g. [START_REF] Aditi | Machine learning with persistent homology and chemical word embeddings improves prediction accuracy and interpretability in metal-organic frameworks[END_REF], [START_REF] Lexter | Persistent homology classification algorithm[END_REF]). We propose a new application of PH to machine learning, in order to overcome the low reliability barrier: sampling coverage analysis and adjustment verification coverage analysis.

Roughly, PH computes a growing sequence of balls centered on each point of the dataset. For each ball radius of the sequence, named filtration, it computes the ball intersections and creates edges between the centers of intersecting balls (see the four filtration steps of fig. 5). These edges constitute a mathematically well-founded nested mesh (simplicial complex) that enables reasoning on a discrete approximation of point cloud shapes, i.e of latent manifolds. In particular, PH focuses on the creation of cycles, of cavities and holes, and disappearance thereof as ball radius grows during the filtration process. It ends when the radius is so large that all balls intersect and no inner void is left within the point cloud. Figure 5 shows an example of a 2D point cloud. We propose to use PH filtration as a (U)HR-ML data engineering practice to design the best ODD-compliant interpretation of the training point cloud. Output of this task would be the ID-OoD 2 oracle of the approximant. For computational tractability, latent dimension must be far lower than ambient dimension. Geometrical Deep Learning [START_REF] Michael | Geometric Deep Learning Grids, Groups, Graphs, Geodesics and Gauges[END_REF] is pivotal here: latent dimension may collapse in datasets only if sampling is performed for the quotiented latent I-manifold by the ODDcompliant symmetries [START_REF] Martin | On the benefits of SO(3)-Equivariant Neural Networks for Spherical Image Processing[END_REF], [START_REF] Mallat | Cours 3 : Malédiction de la grande dimension[END_REF].

C. Formal definition of domains or supports

To our opinion, HR-ML's approximants will require formal and executable definition of their domain (i.e. of their precondition in formal method language). PH offers means to define ID-OoD oracles in a way that does not depend on distributional assumptions or ML techniques like VAEs, GANs etc. [START_REF] Salehi | A Unified Survey on Anomaly, Novelty, Open-Set and Out-of-Distribution Detection: Solutions and Future Challenges[END_REF].

D. Extensional verification coverage analysis

We envision PH-based construction of latent space meshes as means to guide scrutiny of generalization reliability. Datasets augmented with a few "interpretation meshes" (Fig. 5) selected from the filtration could support verification coverage criteria. We name extensional coverage analysis this (hyper-) volume-based verification activity. It would be the extensional counterpart of structural coverage analysis in software (e.g. DC, MC/DC criteria). Such latent-space oriented verification coverage ideas are being explored in [START_REF] Byun | Manifolf for Machine Learning Assurance[END_REF]. within which approximants could be massively tested or formaly proved when possible (e.g. Reluplex). This would be principled extensional verification approach to mastery of complexity [START_REF] Simon | The Architecture of Complexity: Hierarchical Systems[END_REF].

E. Dependent directional statistics in higher dimensions

Entanglement of deterministic and stochastic processes generate the samples of ML applications. The deterministic part of sample dependences invalidate the pivotal i.i.d hypothesis of probability and statistics. ML and (U)HR-ML require sophisticated statistics on manifolds [START_REF] Wainwright | High dimensional statistics -A Non-Asymptotic Viewpoint[END_REF], [START_REF] Kanti | Directional Statistics[END_REF], [START_REF] Barbaresco | Geometric Structures of Statistical Physics, Information Geometry, and Learning[END_REF]. Our proposed use of topological inference to support awareness of adjustment complexity is also intended to support high-dimensional non-asymptotic statistics (e.g. by aggregating empirical concentration information during the filtration process).

VIII. (U)HR-ML ASSURANCE

Our orientation is risk-based and product-based assurance, as possibly contributing process-based [START_REF]EASA Concept Paper : First usable guidance for level 1 & 2 machine learning applications[END_REF] and property-based assurance [START_REF] Adedjouma | Engineering Dependable AI Systems[END_REF].

A. Geometric perspective on ML risks

On basis of our preceding diagnoses and proposals, our top 3 risks on ML-dependent 'control' programs are:

1) Information shortage at specification stage

Dataset-specifications ensure that almost nowhere we have information on the program's intended behavior. Almost everywhere, the unreliability risk is looming. This specification information shortage is an essential difference with classical software engineering. It is specific to machine learning. It could invalidate the assurance concept of potentially realizable "perfect development" that prevails in software assurance. This concept grounds the Fault Elimination policy in development (Dev). Known bugs that may be fixed should be fixed (no hidden defects).

2) Undefined inference domains

In high dimensions, explicit definition of distribution supports and of approximants' ID-OoD oracles are still open problems. It is a barrier to HR and UHR ML. We propose a PH-based approach to try overcoming this problem.

3) Adjustment complexity

Defined in VII.D, we proposed volume-based extensional verification activities as mitigation means.

B. Assurance policy on known residual faults by end of development

For high criticalities, if Authorities decide that a fault-free development should exist and should be approached as far as reasonably possible (ALARP), like for software for instance, then DAL A ML-models transitioning from Dev to Ops should be free of known faults (Eliminative assurance policy). Under this policy, exposing life and goods to failures originating from remaining known and fixable faults is unacceptable. On the contrary, if the remaining known faults are unavoidable, i.e. there is no notion of possible "perfect" development; Quantitative ML assurance policy is acceptable. Because of the information shortage problem specific to ML, Eliminative policy could be inapplicable and Quantitative policy on MLsoftware might become acceptable (i.e. sufficient rareness of failure occurrences). Such a decision seems under way in aeronautics as assurance concept [START_REF]EASA Concept Paper : First usable guidance for level 1 & 2 machine learning applications[END_REF].

The quantitative policy assumes existence of engineering capabilities to predict the future Ops-failure rates from the failure rates observed at Dev-time. It also assumes in-service data logging and mining. In a continuous development / continuous assurance setting (e.g. [START_REF]EASA Concept Paper : First usable guidance for level 1 & 2 machine learning applications[END_REF]), the Dev-failure events and Ops-failure events are altogether continuously managed. For high criticality levels, and from a "classical software" assurance perspective, introducing reliability quantification on software-implemented ML-models is a significant paradigm shift. Figure 5 proposes a SWOT analysis of this shift.

IX. OPEN SCIENCE EXPLORATION

Accessibility of foundational principles, availability of mature and affordable tools, and availability of skills are the prerequisites for acceptance of new engineering practices and assurance rationales in certification. Our next steps are oriented toward meeting some of these requirements. Shortto mid-term actions are development of a few use cases to test the feasibility of (U)HR-ML in "low-higher dimensions" (latent-D < 100). The first milestone is 10 -4 on MNIST.

X. CONCLUSION Our starting point was the following question: in spite of ML-reliability plateauing performance, could current ML best practices, supplemented with safety monitoring and ML assurance, altogether meet the reliability requirements of MLdependent safety? We proposed a group of reasons, centered on geometric complexity of approximant adjustment in higher dimensions, to explain the ML reliability glass ceiling, and the insufficient effectiveness of independent redundancies. Pointcloud forms may be too complex to fit, dataset geometric information too poor, and goodness-of-fit too loosely verified to meet the required 10 -k levels. Safety nets and ML assurance alone are unable to overcome this intrinsic and experimentally established barrier when no impact on function's availability is required. Our answer to our initial question is "no"; something is missing.

We argued that optimizer-synthesis of safety-sensitive 'control' programs from datasets requires more than pure data-science and statistics. We coined (U)HR-ML our proposal of ML augmentated engineering. We put forward computational geometric and topological inference in higher dimensions as our privileged supplement. We focused on application of persistence homology in TDA to formally define the approximants' inference domains, and to tightly control sampling and adjustment quality.

Finally, we discussed the two possible assurance policies applicable to (U)HR-ML: Eliminative and Quantitative. We analyzed elimination at development-time, and MLfailure quantification at operation-time. Considering the DevOps, MLOps and continuous assurance trends, we advocated flexible mixes of the two assurance policies.

Fig. 1 .

 1 Fig. 1. 2D smooth manifold reconstruction (green surface), in 3D ambientspace from red sample points. The picture is based on courtesy of[START_REF] Liang | Robust and Efficient Implicit Surface Reconstruction for Point Clouds Based on Convexified Image Segmentation[END_REF]. We use this form as an example of regions hard to fit (surrounded by dotted-ellipses) and likely to cause poor inference reliability. This adjustment difficulty is (far) higher in higher dimensions. The MLmodel redundancies are intensionally independent. Our interpretation of the marginal gain is that the redundant approximants are extensionally correlated by the 'shape of the problem' to solve, i.e by the shape of the latent IO-manifold to adjust with.

Fig. 3 .

 3 Fig. 3. This figure illustrates a process that would be distinctive of (U)HR-ML: design of a "meaning" to point clouds. Four steps of persitence homology filtration are represented. In the upper part of the figure are examples of typical questions to interpret the filtration step (the green 2Dballs centered on the sample-points). At bottom we wrote examples of interpration decisions that could lead to select this step. PH does not compute a model, it computes a sequence of models. The selection of an interpretation would start the task of explicit definition of the approximant's domain.

Fig. 4 .

 4 Fig. 4. Filling the ML reliability gap by better verification coverage techniques. Extensional verification should ensure non-zero measure coverage. PH's simplicial complexes are volumes (hyper-tetrahedrons)within which approximants could be massively tested or formaly proved when possible (e.g. Reluplex). This would be principled extensional verification approach to mastery of complexity[START_REF] Simon | The Architecture of Complexity: Hierarchical Systems[END_REF].

Fig. 5 .

 5 Fig. 5. SWOT of the "pan-statistical" option in ML assurance. Difficulty to get valid risk quantifications and possible regressive enforcement of fault elimination policy are its drawbacks.

ACKNOWLEDGMENT

The authors pay tribute to the members of Embedded France's Working Group on safety standards (NSL) for their peer review of this paper, especially to Hugues Bonnin who initiated this work, and to Jean Paul Blanquart who was pivotal in analyzing the rationales of development assurances. E. Ledinot is indebted to Stephane Mallat [21], Marc Mezard [14], Stephane Herbin and Jérôme Lacaille [20] from BNAé 's VAML WG, and to Pierre-Yves Lagrave [16] for their insightful perspectives on Machine Learning.


CARTAPANIS

The Court of Justice of the European Union rejects the Bronner test when the abusive conduct manifests itself in the dismantling of a railway infrastructure (Lietuvos geležinkeliai) EUCJ, 12 Jan. 2023, C 42/21 P, Lietuvos geležinkeliai AB/Orlen Lietuva AB / Unilateral practices -Rail -Abuse -Essential facilities -Refusal to contract -Abuse (notion)

Commentaire :

Le 12 janvier 2023, la Cour de justice de l'Union européenne a rendu un arrêt par lequel elle réduit le domaine d'application des conditions de l'arrêt Bronner et retient une forme autonome d'abus de position dominante.

L'affaire concernait l'entreprise Lietuvos geležinkeliai (« LG »), la société nationale des chemins de fer de Lituanie, à la fois gestionnaire des infrastructures ferroviaires et fournisseur de services de transport ferroviaire. Prétextant une déformation de la voie ferrée sur quelques dizaines de mètres sur l'itinéraire menant de la Lituanie à la Lettonie, l'entreprise avait suspendu le trafic sur un tronçon lituanien de 19 km, puis avait procédé au démantèlement complet de la voie ferrée, empêchant, par là même, une entreprise lettone, la société LDZ, d'y déployer ses activités.

Dans une décision du 2 octobre 2017, l'entreprise LG avait été condamnée à une amende de près de 28 millions d'euros par la Commission européenne, qui avait considéré que le démantèlement du tronçon ferroviaire constituait un abus de position dominante. (Comm. eur., 2 octobre 2017, AT. 398113, Baltic Rail ; F. Marty, « Infrastructure essentielle : La Commission européenne sanctionne l'opérateur historique des chemins de fer lituanien pour un abus d'éviction reposant sur un démantèlement d'une infrastructure essentielle (la société des chemins de fer lituaniens -Baltic Rail) », Concurrences N° 1-2018, Art. N° 86076, p. 93). La Commission avait donc enjoint l'entreprise à reconstruire le tronçon. Or, cette exigence, équivalente à une obligation d'accès, impliquait, selon l'entreprise, la mise en oeuvre de la théorie des infrastructures essentielles et la réunion des conditions posées par l'arrêt Bronner (CJCE, 28 nov. 1998, C-7/97, Oscar Bronner)

  geležinkeliai AB/Orlen Lietuva AB La Cour de justice de l'Union européenne écarte le test Bronner lorsque le comportement abusif se manifeste par le démantèlement d'une infrastructure ferroviaire (Lietuvos geležinkeliai) CJUE, 12 janv. 2023, C-42/21 P, Lietuvos geležinkeliai AB/Orlen Lietuva AB / Pratiques unilatérales -Ferroviaire -Abus de position dominante -Théorie des infrastructures essentielles -Refus de contracter -Notion d'abus

  . Saisi d'un recours, le Tribunal de l'Union européenne avait confirmé la décision de la Commission (Trib. UE, 28 nov. 2020, T-814/17, Lietuvos ; F. Marty, « Barrières à l'entrée : Le Tribunal de l'Union européenne confirme la décision de la Commission européenne dans l'affaire du démantèlement d'une portion de voie de chemin de fer en Lituanie pour faire obstacle à l'entrée d'un concurrent (Lietuvos geležinkeliai) »,Concurrences N° 1-2021, Art. N° 98745, pp. 131-134). Partant, c'est devant la Cour de justice de l'Union européenne que l'entreprise, en introduisant une demande d'annulation, entendait remettre en cause cette condamnation. Google). Ce test s'appliquait-il lorsque qu'une entreprise publique, soumise à des obligations d'accès en vertu du cadre réglementaire, démantèle un tronçon ferroviaire ? Si la réponse apportée, à savoir une réponse doublement négative, n'étonne guère, le recours était l'occasion, pour la Cour, de poursuivre son oeuvre de clarification de la portée de la jurisprudence Bronner. L'arrêt apporte ainsi des éléments utiles tant sur l'autonomie du comportement reproché (I) que sur la question de l'applicabilité du test (II).Si la Cour ne qualifie pas expressément la pratique en cause de pratique de prédation, elle met toutefois en oeuvre le test du sacrifice, en considérant que « la destruction d'une infrastructure implique le sacrifice d'un actif, moyennant, le cas échéant, des coûts liés à cette destruction. Du fait de la destruction, l'infrastructure devient inévitablement inutilisable non seulement par les concurrents, mais également par l'entreprise dominante elle-même ». Or, comme l'avait souligné l'avocat général Rantos, LG a choisi d'abandonner un actif de valeur, à savoir une voie ferrée, en sacrifiant son exploitation, et donc des revenus. Dans ce contexte, la seule explication rationnelle à un tel sacrifice est l'exclusion de son concurrent : la pratique induisait une perte à court terme, qui n'était rationnelle que parce qu'elle était guidée par la perspective d'un profit à plus long terme. Les affaires de refus d'accès se caractérisent en revanche davantage par une logique de profit immédiat.Les effets anticoncurrentiels révélés par la Commission européenne confirment d'ailleurs cette analyse : d'abord, la suppression de la voie ferrée était susceptible d'empêcher LDZ d'entrer sur le marché du fret ferroviaire lituanien ou, à tout le moins, avait rendu beaucoup plus difficile son accès à ce marché. Ensuite, avec la suppression de la voie ferrée, tout transport ferroviaire de la raffinerie vers un terminal maritime letton devait emprunter un itinéraire beaucoup plus long. LDZ aurait donc, de ce fait, été contrainte de mener ses activités loin de sa base logistique en Lettonie et aurait été tributaire des services de gestion des infrastructures de son concurrent, à savoir LG. dans deux situations : soit lorsque le cadre réglementaire applicable à l'affaire imposait déjà une obligation de fourniture à l'entreprise dominante ; soit lorsque la position dominante découlait d'un monopole légal. Dans ces circonstances, en effet, il ne peut y avoir de réduction de l'incitation initiale de l'entreprise à investir dans de telles infrastructures. C'est donc sans commettre d'erreur de droit que le Tribunal a jugé que les critères Bronner n'ont pas vocation à s'appliquer lorsque l'entreprise dominante est soumise à une obligation d'accès à son infrastructure.Ensuite, la Cour rappelle que le test Bronner s'applique au refus de contracter parce qu'il suppose une mise en balance entre la libre concurrence et le respect de la propriété et de la liberté contractuelle, ce qui justifie le standard juridique particulièrement élevé. Or, en l'espèce, l'entreprise n'était pas propriétaire de l'infrastructure, laquelle n'avait pas été financée par des investissements propres à l'entreprise dominante, mais par des fonds publics.Par ailleurs, un refus d'accès est susceptible de constituer un abus de position dominante à condition, non seulement que ce refus ait été de nature à éliminer toute concurrence sur le marché en cause de la part du demandeur d'accès et n'ait pu être objectivement justifié, mais également que l'infrastructure en elle-même ait été indispensable à l'exercice de l'activité de celui-ci, dès lors qu'il n'aurait existé aucun substitut réel ou potentiel à cette infrastructure. Dans l'affaire Bronner, en effet, l'imposition de ces conditions était justifiée par les circonstances propres à l'affaire et qui consistaient en un refus par une entreprise dominante de donner à un concurrent accès à une infrastructure qu'elle avait développée pour les besoins de sa propre activité.En l'espèce, la pratique en cause, à savoir le démantèlement du tronçon ferroviaire, était-elle comparable ? La Cour répond par la négative, et s'inscrit par là même dans la continuité de sa jurisprudence récente en limitant la portée du test Bronner, parce « qu'imposer une obligation d'accès au propriétaire d'une infrastructure est particulièrement attentatoire à la liberté contractuelle et au droit de propriété ». Rien de comparable, donc, en l'espèce.Bien au contraire, LG, en tant qu'entreprise publique, était soumise à une obligation d'accorder l'accès au réseau ferroviaire lituanien. Or, le cadre réglementaire en vigueur ne limite pas l'application de l'article 102 TFUE. Il constitue, au contraire, un élément à prendre en considération pour apprécier le caractère abusif du comportement d'une entreprise en position dominante, puisqu'il contribue à déterminer les conditions de concurrence dans lesquelles celle-ci opère(CJUE, 25 mars 2021, aff. C-165/19, Slovak Telekom). En d'autres termes, et « indépendamment des objectifs visés, le contrôle ex post du droit de la concurrence complète le cadre réglementaire ex ante (en ce sens, Concl. Avocat gén. Rantos, Aff. C-42/21, 7 juillet 2022, pt 86). réserve l'usage en vue d'un profit immédiat. En effet, détruire une infrastructure implique un sacrifice, non seulement parce que la destruction a un coût, mais également parce que l'infrastructure devient inutilisable par les concurrents mais également par l'entreprise dominante. L'arrêt précise donc les obligations qui pèsent sur les opérateurs historiques. En restreignant la portée de l'infraction de « refus d'accès », et en écartant les conditions de l'arrêt Bronner, la Cour de justice allège la charge de la preuve de l'article 102 TFUE, ce qui n'est pas sans faire écho à l'affaire Google Shopping dans laquelle le Tribunal avait certes reconnu que la page de résultats d'une requête sur Google « présente des caractéristiques qui la rapprochent d'une facilité essentielle », mais s'en distingue « dans leurs éléments constitutifs du refus de fourniture en cause dans l'affaire ayant donné lieu à l'arrêt Bronner ». En somme, toute problématique d'accès n'implique pas nécessairement l'application des conditions énoncées dans l'arrêt Bronner, afférentes aux refus de fourniture (Trib. UE, 10 nov. 2021, aff. T-612/17, Google, pt 230). Au regard des circonstances de l'espèce, il faut s'en réjouir.

	L'on sait à ce sujet que la jurisprudence Bronner avait déjà posé question en 2021, le juge européen
	ayant fortement restreint son champ d'application (CJUE, 25 mars 2021, aff. C-152/19, Deutsche
	Telekom AG c/ Commission, CJUE, 25 mars 2021, aff. C-165/19, Slovak Telekom ; Trib. UE,
	10 nov. 2021, aff. T-612/17, I.
	II.	Le test Bronner inapplicable
	La reconnaissance de l'autonomie du comportement emportait, en second lieu, l'inapplicabilité du
	Partant, la Cour rejoint les conclusions de l'avocat général, pour qui l'hypothèse d'une destruction test Bronner. LG reprochait en effet au Tribunal d'avoir commis des erreurs de droit en refusant, Sans surprise, le montant de l'amende est également confirmé. LG reprochait au Tribunal d'avoir
	d'une infrastructure, par une entreprise dominante, doit être distinguée de celle d'un refus d'accès, à tort, d'appliquer le test Bronner pour déterminer l'existence de la pratique. accordé une place prépondérante à l'intention de l'entreprise dans le calcul de l'amende, mais n'a
	au sens de la jurisprudence Bronner (Concl. Avocat gén. Rantos, Aff. C-42/21, 7 juillet 2022, pts apporté aucun élément de nature à prouver que le niveau de l'amende, déjà réduite par le Tribunal,
	78 à 82). En effet, le démantèlement d'une voie ferrée relève d'une destruction indépendante était inapproprié et disproportionné. Le moyen est donc rejeté.

L'autonomie de l'abus par démantèlement C'est, en premier lieu, sur la nature du comportement en cause que l'arrêt apporte des éléments utiles puisque la Cour confirme que l'on est en présence d'une forme autonome d'abus qui s'apparente à une pratique de prédation (v. eg en ce sens L. Idot, Notion d'abus et démantèlement d'une infrastructure, Europe n° 3, Mars 2023, comm. 106). Plusieurs raisons expliquent cette solution.

D'abord, le Tribunal avait montré que LG savait que l'un de ses clients allait se tourner vers les services de l'entreprise LDZ et avait, en représailles, supprimé la voie en toute hâte, sans s'assurer du financement nécessaire et sans prendre aucune des mesures préparatoires normales pour sa reconstruction. Elle avait donc eu recours à des méthodes autres que celles qui régissent une concurrence par les mérites. Le Tribunal avait en effet constaté qu'il incombait à LG, parce qu'elle était gestionnaire d'infrastructures ferroviaires, une triple obligation réglementaire de garantir la sécurité du trafic, de minimiser les perturbations et d'améliorer les performances du réseau ferroviaire. Mais qu'il lui incombait également, en tant qu'entreprise dominante sur le marché, une responsabilité particulière de ne pas porter atteinte, par son comportement, à une concurrence effective et non faussée. d'infrastructures, qui empêche l'usage, non seulement aux concurrents, tels que LDZ, mais également à LG. Ce cas se différencie donc nettement des affaires de refus d'accès, où l'entreprise dominante ne subit aucune perte d'infrastructures. Dans ces circonstances, d'un point de vue ex ante, LDZ était exposée à d'importants risques commerciaux. Dès lors, le moyen visant à contester les appréciations de la Commission, selon lesquelles la suppression de la voie ferrée produisait des effets anticoncurrentiels, est écarté dans son intégralité.

La Cour estime que « la présente affaire ne soulevait pas, contrairement aux allégations de LG, un « problème d'accès » à une infrastructure au sens de la jurisprudence issue de l'arrêt ». Cette réduction du domaine du refus d'accès avait déjà été amorcée avec l'autonomie du test applicable aux compressions de marges

(CJUE, 17 févr. 2011

, aff. C-52/09, TeliaSonera, pt 55 s.). Plus récemment, la Cour indiquait que « lorsqu'une entreprise dominante donne accès à son infrastructure mais soumet cet accès (…) à des conditions inéquitables, les conditions énoncées par la Cour dans l'arrêt Bronner ne s'appliquent pas (CJUE, 25 mars 2021, aff. C-152/19, Deutsche Telekom CJUE, 25 mars 2021, aff. C-165/19, Slovak Telekom). L'arrêt du 12 janvier 2023 s'insère donc dans la droite ligne de ces jurisprudences. D'abord, la Cour rappelle que les critères Bronner ne s'appliquent que s'il y a une nécessité de protéger l'incitation d'une entreprise dominante à investir dans la réalisation d'infrastructures essentielles. Il s'agit ici de protéger la concurrence, car une obligation d'accès affecte l'incitation initiale de cette entreprise à investir dans une telle infrastructure. Toutefois, en l'espèce, l'argument n'était pas pertinent. Le Tribunal avait en effet déduit, et à bon droit, que le test ne pouvait pas s'appliquer En conclusion, il faudra retenir de cet arrêt que la Cour distingue désormais nettement l'hypothèse d'une destruction d'une infrastructure et celle d'un refus d'accès. Cela signifie que la mise en oeuvre du test Bronner implique nécessairement le maintien d'une infrastructure dont l'entreprise dominante se M. C


Fatma Abdelhédi
email: fatma.abdelhedi@irit.fr

Gilles Zurfluh
email: gilles.zurfluh@irit.fr

User Support System for Designing Decisional Database

Keywords: Multidimensional model, design process, decisional Data-base, decision-makers' requirements, datasource I

The design of a multidimensional schema is usually performed by a specialist (computer scientist). According to data-driven, requirement-driven or hybriddriven approaches, he determines the facts and axis of analysis. Such an approach assumes that the decision maker expresses, more or less formally, analysis needs and communicate them to the computer scientist. We propose multidimensional schema designing by the decision maker himself following a hybrid-driven approach. Through a process of assistance successively viewing intermediate schemas from sources, the decision maker gradually built his multidimensional schema. As what determined the measures studied, the analysis dimensions and hierarchies within dimensions. A software tool named SelfStar based on this principle has been developed and validated with decision makers.

INTRODUCTION

Decisional Data Base (DDB) allows decision maker to analyze data structured according to a multidimensional schema (star or constellation). Multidimensional schema design has motivated numerous works which can be derived from data-driven, requirement-driven or hybriddriven approaches [START_REF] Ravat | Personalization and OLAP databases[END_REF][2] [START_REF] Romero | Automatic validation of requirements to support multidimensional design[END_REF]. These approaches, to perform as well as they are, all involve a designer who is only able to design a multidimensional schema from decision makers' requirements or data source schema. The development of such a schema is a cumbersome process because it requires decision makers to articulate their needs to a designer and that it captures well the need to translate them to a adapted schema form. Decision makers do not generally mastered formalisms and IT (Information Technology) tools but are experts in their field work. The SelfStar project fits into this fact and aims to define the data warehouse process dedicated to casual users (decision makers). It propose an approach and a software tool allowing to the decision-maker to design himself his DDBs incrementally, according to his requirements, and this without recourse to an expert designer. This paper focuses on the constellation schema [START_REF] Kimball | The data warehouse toolkit : Practical Techniques for Building Dimensional Data Warehouses[END_REF] design.

This paper focuses on the incremental design of a constellation schema from the relational schema of a data source. This work is part SelfStar project developed by our team and aimed to decision-makers to design their data-warehouses.

The paper is structured as following. In Section 2, we present briefly several approaches to design a multidimensional schema. The justification of SelfStar system is provided in Section 3. In Section 4, the input and the output of the system are successively defined. Section 5 is devoted to a presentation of multidimensional schema process. Section 6 describes the architecture of a case tool allowing to experiment these mechanisms.

II. RELATED WORK

Many studies have been devoted to the multidimensional schema approach. These approaches can be classified into 3 categories: data-driven, requirementdriven, and hybrid-driven approaches. Data-driven approach [START_REF] Ravat | Personalization and OLAP databases[END_REF][5] uses database source to generate a set of candidate multidimensional schemas and presents the drawback of not taking into account decision makers' requirements, consequently, going towards a possible failure of expectations of decision maker. Requirementdriven approach [START_REF] Prat | A UML-based data warehouse design method[END_REF][6] takes into the needs of decision makers, but the sources are ignored at first. After that, multidimensional schema has to be mapped on the data sources. So, the designer can discover that the requirements do not correspond to sources.

Hybrid-driven approaches [3][7] combines and integrate the benefits of these two previous approaches. In fact, this approach designs on the one hand candidate schemas from the data (data-driven approach) and on the other hand multidimensional schema from decision makers' requirements (requirement-driven approach). A designer must map these two types of schemas to obtain a consistent multidimensional schema. Romero and Abelló [START_REF] Romero | Automatic validation of requirements to support multidimensional design[END_REF] propose an automatic method Multidimensional Design by Examples (MDBE) following a hybrid-driven approach. To generate multidimensional schemas, this method takes as input, on one hand, the decision makers' requirements expressed as SQL queries, and on the other hand, the relational data source. Source analysis is provided by SQL queries and knowledge of relational source schema. Therefore, the multidimensional schema design requires an expert (a computer scientist) to formulate SQL [15] query and analyze data source. Pinet and Schneider [START_REF] Pinet | A unified object constraint model for designing and implementing multidimensional systems[END_REF] propose to generate a multidimensional schema from a conceptual schema using UML notations. This approach represents source classes with a directed acyclic graph. The user chooses a node from this graph to design a fact. All connected nodes to this chosen fact represent the potential dimensions of this fact. However, in our opinion, this representation of multidimensional schema is complex for the decision maker because of the number of generated nodes to represent the dimension hierarchies. However, interactions with the decision maker choices are limited to the facts.

To our knowledge, few works [START_REF] Giorgini | Goal-oriented requirement analysis for data warehouse design[END_REF] try to allow users to participate in the process of multidimensional schema.

III. JUSTIFICATION OF SELFSTAR PROJECT

In the current approach, the decision makers should ask the specialists of the data management (administrators, computer scientist) each time they wish to get a new decisional database or to evolve the deprecated multidimensional schemas. This is related primarily to the complexity of: principles of designing of a decisional database ETL Processes ensuring the periodic load of the decisional database from there [START_REF] Vassiliadis | A survey of Extract-transform-Load technology[END_REF] [START_REF] Atigui | Using OCL for Automatically Producing Multidimensional Models and ETLProcesses[END_REF].

SelfStar project aims to propose a full approach and a software environment to allow to the decision maker to design a constellation schema. The design process of the schema is based on a hybrid approach: it starts from the database schema (class diagram CD) and the decision makers' requirements. This process is incremental: the decision maker integrates progressively the analysis needs in 3 successive intermediate schemas.

The advantage of such process is twofold:

The decision maker becomes independent to express his decisional requirements, The process automatically controls the correspondence between analysis requirements and sources.

However, the decision maker, even if he knows his needs, is obviously confronted with a double complexity: Data source organization (Relational, Entity-Association or UML diagram), Process of the star or constellation schema design (fact(s), dimensions, hierarchy).

SelfStar project aims to propose formalized mechanisms to palliate this complexity.

IV. INPUT AND OUTPUT OF SELFSTAR

SelfStar system allows constellation schemas design from a data source and the decision-maker's requirements. In order to illustrate the input/output of the design process, we present successively an example of source schema, an expression of analysis needs and finally the decisional base schema resulting from the process.

A. Data source: Input of SelfStar

Data source is described by UML language. The choice of this formalism is justified by the semantic richness of the data model [START_REF] Prat | A UML-based data warehouse design method[END_REF] and also by the correspondence between this language with the models entity-association and relational. Figure 2 gives the example of a classes diagram (CD) describing a management of the sales. The CD not being easily exploitable in the state, it is the subject thus of a reprocessing. This principle was already proposed in [START_REF] Song | SAMSTAR: An automatic tool for generating star schemas from an entity-relationship diagram[END_REF] for the Entity-Association model and in [START_REF] Giorgini | Goal-oriented requirement analysis for data warehouse design[END_REF] for the UML CD. According to this principle, the conceptual schema is transformed into a simplified schema containing only object classes and binary links of type 1..N between these classes. The transformation of a DCL into an exploitable schema is carried out as follows: The exploitable schema obtained is an oriented acyclic graph.

B. Requirements: Input of SelfStar

When a decision maker wants to analyze the data of a source, it can express his requirements:

Either in the form of SQL request [START_REF] Ravat | Graphical querying of multidimensional databases[END_REF] ; but this proves to be difficult for decision maker except IT, especially when these requests make use of clauses Group By and Having;

Or in the dashboards forms corresponding to the expected analysis results.

In SelfStar, the decision maker integrates his requirements by himself through a graphic interface and this without formalizing them beforehand.

C. Data-mart: output of SelfStar

From a data source and analysis needs, SelfStar system visualizes a decisional database on which the decision maker can apply its queries. The schema of Figure3 describe a decisional database allowing the decision maker to analyze the number of Orders (Orders_Nb measure) and the delivered quantity accumulated (Orders Amount measure) according to Products and Dates dimensions. Each dimension is associated to a set of organized parameters into hierarchies.

A. Multidimensional schema design

The proposed process in SelfStar (Figure 3) has a starting point the data source schema (CD) and the decision-makers' requirements (informal). It contains four successive steps in which the decision maker will interact with the system to integrate progressively his requirements. Each step produces a new schema more comprehensive than the previous one. The 4th schema corresponds to that of the decisional database, i.e. the desired result (Figure 3). The decisional schema design is performed incrementally.

First step consists to display a set of candidates facts in the intermediate schema number 1 (noted IS1). InIS1, the decision maker chooses the fact that he wants to analyze with the measures and their aggregations functions.

Second step generates automatically the intermediate schema number 2 (IS2); it proposes all possible associated dimensions with the selected fact. InIS2, the decision maker will be able to indicate dimensions according to which they wish to analyze the fact.

Third step generates an intermediate schema number3 (IS3) containing the constellation schema (fact(s) + dimensions) with all the possible hierarchies. In IS3, the decision maker will choose each responding hierarchies to their requirements.

Fourth step produces the multidimensional schema data-mart. At this level SelfStar will record the personalization metadata which later will allow the decision maker to elaborate the newest multidimensional schemas. All algorithms related to the different phases of the process are presented in [START_REF] Abdelhédi | Computer-Aided Data-Mart Design[END_REF].

B. Personnalization meta-data

Industrial experience of our team [START_REF] Annoni | Towards multidimensional requirement design[END_REF] showed that (1) a data source (sales or production BD) contains frequently from 30 to 60 objects classes and many links and (2) the analyzes carried by the same decision maker are usually very similar in terms of facts and dimensions.

According to (1), we consider that the decision maker isn't able to choose the fact directly from the conceptual source schema because this schema is considered complex for any person (except computer scientist). We have decided to show for the decision maker a simplified presentation of the source (noted IS1) that is extracted automatically from the source schema. The second point noted (2), led us to define a personalization mechanism on the IS1; this mechanism can extract, from the CD of source, the most significant classes for helping the decision maker.

The simplification of a source is based on the extraction of classes which must be analyzed by the decision maker (candidates facts). This extraction method is based on the personalization technical developed in our team and which inspired from the work of [START_REF] Ravat | Graphical querying of multidimensional databases[END_REF]. SelfStar record the personalization metadata whenever a decision maker develops a decisional schema. It is based on the scheduling of the candidate facts when the same decision maker will design a new multidimensional schema. Figure5 presents the algorithm that producing the personalization metadata.

A. Experimentation

SelfStar project was implanted in order to experiment all the proposed mechanisms. Figure 6 presents the software architecture. JAVA was used to develop this software. We used JAXP (Java API for XML Processing) that is a set of API including the SAX, DOM, XSLT (eXtensible Stylesheet Language Transformations) and XPath. The set of schemas used by SelfStar are with XML. We use JAXP tools to transform them. To view all XML schemas (intermediate schemas), we have developed a visualization module. It allows also the interaction between the system and the decision maker via the interface. This module uses the JGraph library. Soon activation, the software demands to the decision maker identifier of relational database (source). CD source is transformed into an exploitable schema through the XSLT API (XSLT generator). The DOM generator creates then intermediate schema 1 (IS1) through by analyzing exploitable schema and using basic metadata (calculated weight). IS1 is displayed and the decision maker can choose directly on the screen fact(s) to analyze. This process is repeated to integrate choice of dimensions and attributes in the following intermediate schemas (IS2 and IS3).

Finally, the multidimensional schema will be displayed and personalization metadata are generated. They will subsequently be used to guide the decision maker in developing new multidimensional schemas. It should be noted that during the first analysis of the source, only the basic metadata are available. With each new analysis of this source, the metadata is enriched and will better define the profile of the decision maker.

B. Validation

To validate our approach and our tool, we used marks management application at University of Toulouse. The database source is composed of extracted data from the management education package (APOGEE [START_REF][END_REF] available in most french universities). We chose three decision makers of staff responsible for managing marks and awarding degrees.

The source is a relational database containing training descriptions, students and results. Figure 7 shows an extract from the schema describing the database source. We asked three employees of the University, having similar activities but independent create their own decisional databases using the database sources for analysis. It is noted that these decision makers use Business Object [START_REF]SAP France -SAP BusinessObjects -Solutions de Business Intelligence (BI) et de gestion de la performance[END_REF], occasionally.

(1) An official school: analyzes the students' absenteeism in the exams; observes the dates of issuance of marks of exams, etc.

(2) A training manager: defines the rate of exam success by students, analyzes the evolution of result per scholar year, etc.

(3) An academic manager of an academic year: examines student grades per subject per teacher (average, standard deviation, etc.), analyzes the results per subject, etc After a brief training regarding the using of SelfStar, these three decision-makers showed certain affluence to quickly design new data-marts and manipulate them with Business-Object. The scheduling of the candidate facts was realized through the mechanism of personalization.

VII. CONCLUSION AND FUTURE WORK

This paper provided an approach to design a multidimensional schema from the data sources schema to be analyzed; the decision makers' requirements are integrated progressively throughout the process. This approach is original in the measurement that it allows for the decision maker to design progressively his multidimensional schema without resorting to a database specialist (computer scientist). It is distinct clearly from the others data-driven, requirement-driven or hybriddriven approaches in which the user is not directly involved.

Figure 1 .

 1 Figure 1. UML Class Diagram of products sales ans stock management

Figure 2 .

 2 Figure 2. Our design process that allows a decision-maker to build a data-mart schema

  An object's classes or association's classes of the source becomes a class in the exploitable schema, A binary association links type 1..N is deferred in the state, A binary association links type M..N is transformed into a class bound by 2 links 1..N,A link of aggregation or composition is processed as an association links (these type of links are not meaningful in the multidimensional schema), A link of heritage disappears; the subclass of the source becomes a class and it will be on the same level as the super-class by inheriting its attributes and links (it preserves the semantics of the data).

Figure 3 .

 3 Figure 3. Data-mart schema V. PERSONNALIZATION PROCESS

Figure 4 .

 4 Figure 4. The transformation from data-source and decision makers' requirements to data-mart schema

Figure 5 .

 5 Figure 5. Generation personalization metadata

Figure 6 .

 6 Figure 6. Software architecture of SelfStar This paper does not deal ETL process. But, SelfStar has a module for loading data warehouse from sources. This module is automatically generated by SelfStar after the development of multidimensional schema.

Figure 7 .

 7 Figure 7. CD extract of Database source

Figure 8 .Figure 9 .Figure 10 .

 8910 Figure 8. Intermedite schema n°1


Florian Laurence

Xavier Bonnet

Sylvain Ursenbacher

Gaëtan Guiller

Gopal Billy

Guy Naulleau

Nicolas Vidal

Diet variations across remote populations of a widely distributed snake species, the Asp viper (Vipera aspis aspis; Linnaeus 1758)

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Diet variations across remote populations of a widely distributed snake species, the Asp viper (Vipera aspis aspis; Linnaeus 1758) Vipera aspis is a common species extending from west France to Switzerland, south Italy and north Spain. This snake inhabits a great variability of habitats, including plains nearby the Atlantic Ocean, Mediterranean habitats or mountainous alpine meadows. Diet may vary across habitats (e.g., plains, scrublands, mountains). Conversely, Vipera aspis may select a narrow spectrum of prey. We addressed this issue in the subspecies Vipera aspis aspis. Combining fieldwork and Museum specimens, we examined 1,680 vipers and collected 605 prey' observations. We compared five areas encompassing contrasted habitats (map below).

Florian LAURENCE 1 , Xavier BONNET 2 , Sylvain URSENBACHER 3,4 , Gaetan GUILLER 5 , Gopal BILLY 2 , Guy NAULLEAU 6 , and Nicolas VIDAL 1 How to better explain collected data?

➢ ACP to combine environmental variables, individual characteristics and diet.

We also observed (and thus confirmed) the ontogenetic shift (juveniles consume more reptiles), less pronounced with altitude.

Data are separated by habitat (linked with altitude) and primary type of prey (X axis), secondary type of prey and age (Y axis).