Computing and compressing the negative skycube

Tableau 1. Les hôtels

Les requêtes skyline  sont un cas particulier de requêtes de préférence dont l’objec- tif est de retrouver  un sous-ensemble de tuples qui ne sont pas moins bons que d’autres. Ce résultat s’appelle également Optimum au sens de Pareto.  Dans un contexte mul- tidimensionnel, l’utilisateur  peut choisir un sous-ensemble d’attributs  au regard des- quels les tuples sont comparés. L’ensemble des requêtes skyline est appelé le skycube. En raison du nombre exponentiel de requêtes skyline,  la matérialisation du skycube est chronophage et requiert beaucoup d’espace. Pour cette raison, deux directions de recherche ont été suivies depuis lors : d’une part, des algorithmes complexes pour ac- célerer le calcul du skycube ont été proposés, d’autre part, des techniques de compres- sion (réduction  de la taille) du skycube ont été définies pour réduire l’espace requis tout en conservant le temps de calcul acceptable. Considérant la réduction  de taille, certains algorithmes supposent le skycube comme faisant partie de l’entrée tandis que d’autres présentent des procédures de compression partant de l’ensemble des données brutes.

Le présent travail se base sur l’observation suivante : affirmer qu’un tuple t fait par- tie du skyline nécessite qu’il soit comparé à l’ensemble des autres points. Cependant, la comparaison de t à un autre tuple t′ nous permet de déduire un ensemble de sous- espaces pour lesquels t n’appartient  pas au skyline.  Partant de là, notre hypothèse de départ est alors que rechercher les sous-espaces au regard desquels t n’appartient  pas au skyline  peut se faire plus rapidement que le travail complémentaire. Une fois que cet ensemble de sous-espaces est déterminé, retrouver l’ensemble complémentaire est évident.

Sauvegarder pour chaque tuple t, l’ensemble  des sous-espaces pour lesquels t n’appartient  pas au skyline peut être impossible en pratique en raison de la grande quantité de mémoire qui doit être requise. C’est pourquoi, nous proposons une tech- nique permettant de résumer cette information.  L’exemple  ci-dessous illustre notre approche.

EXEMPLE 1. — Considérons la liste d’hôtels  présentée dans le tableau 1.

Nous avons une préférence pour les hôtels les moins coûteux, les plus près de la mer, présentant les chambres les plus grandes et disposant du Wifi. L’utilisateur  a la possibilité de demander le skyline au regard de n’importe laquelle des 2⁴ − 1 requêtes correspondant aux sous-ensembles non vides de l’espace {P, D, A, W}. En comparant les hôtels h₂ et h₁ , nous déduisons que h₂  domine h₁ en chacun des sous-espaces subspaces₂= {P, W, PW, AP, AW, APW}¹ . Cependant, après cette comparaison, nous n’avons aucune information  concernant les sous-espaces pour lesquels h₁ fait partie du skyline. Pour cela nous avons également besoin de comparer h₁ et h₃ . Une fois la comparaison effectuée, nous déterminons un nouvel ensemble de sous-espaces dans lesquels h₁ est dominé c’est-à-dire subspaces₃={A, W, AW, AD, DW, AP, ADP, PW, ADW, APW, DPW, ADPW}. subspaces₂ ∪ subspaces₃  est l’ensemble des sous-espaces dans lesquels h₁ est dominé. Son complémentaire est l’ensemble  des sous-espaces pour lesquels h₁ fait partie du skyline c’est-à-dire {D, DP}. En pratique, le nombre  de sous-espaces associés à un tuple peut être très grand. Nous proposons donc une technique permettant de résumer cet ensemble tout en conservant l’efficacité des requêtes.

Nos contributions peuvent être résumées comme suit : (i) étant donné l’ensemble des sous-espaces au regard desquels un tuple n’appartient  pas au skyline,  nous pré- sentons une structure  de données appelée NSC qui résume le skycube négatif. (ii) Nous proposons une procédure prenant en entrée la table T et retourne le NSC cor- respondant. Enfin, (iii) nous présentons un ensemble de résultats d’expérimentations montrant  les avantages et les limites  de nos approches par rapport aux algorithmes  de l’état de l’art.

Après une brève présentation  des travaux  se rapportant à cette problématique  (sec- tion Travaux relatifs),  nous définissons les principaux concepts et notations utilisés tout le long de cet article. Ensuite, nous présentons (section 3) la problématique du résumé du skyline négatif, nous élaborons les algorithmes  permettant de résoudre ce problème. Enfin,  quelques résultats d’expériences  sont présentés (section 4).

1. Nous verrons plus tard qu’il est facile d’obtenir cette information  sans avoir à effectuer  la comparaison au regard de chacun des sous-espaces

Notations

Soient T (I d, D₁ , . . . , D_d ) une table et D = {D₁ , . . . , D_d } l’ensemble  des dimen- sions de la table T . Chaque sous-ensemble non vide de D est un sous-espace (soit X un sous-ensemble de D). Pour chaque dimension Di , nous supposons établi un ordre total <i au sein de ses valeurs. Soient v, v′ ∈ D_i , nous disons que v est préféré  à v′ ssi v <i v′. Soient t et t′ deux tuples de la table T , on dit que t est dominé par t′ au regard du sous-espace X , noté t′ ≺X  t, ssi t′[D_i ] ≤i  t[D_i ] pour chaque D_i ∈ X et il existe D_j ∈ X tel que t′[D_j ] <j  t[D_j ]. Le skyline de T au regard du sous-espace X , noté SkyT (X ) ou simplement Sky(X ), est l’ensemble  des tuples de T qui ne sont pas dominés au regard de X . Le skycube de T est l’ensemble  {Sky(X )|X  ∈ 2D et X  = ∅}. Par conséquent, le skycube est composé de 2^d − 1 skylines. Nous notons n le nombre de tuples appartenant à la table T (la taille de T ).

Le tableau 2 résume les différents notations utilisées tout le long de cet article.

Tableau 2. Notations

EXEMPLE 2. — Le tableau 3 sert d’exemple tout le long de cet article. Dans cet exemple, l’utilisateur pourrait demander les meilleurs  tuples au regard de chaque combinaison de dimensions {A, B, C, D}.  Par exemple,  Sky(AB)   = {t₁ , t₂} et Sky(ABC D) = {t₂ , t₃ , t₄ }.

Tableau 3. Une table de données T

Notre contribution  se résume en la proposition d’une structure de données qui, pour chaque tuple t appartenant  à la table T , résume l’ensemble des sous-espaces X tels que t n’appartient pas à Sky(X). Ceci est motivé par l’observation suivante : pour un tuple t, alors qu’il est nécessaire de le comparer à tous les autres tuples pour savoir s’il appartient à un skyline Sky(X), le comparer à un seul autre tuple t′ permet déjà de déterminer  une partie de l’ensemble  des sous-espaces dans lesquels t est dominé, c’est-à-dire, des sous-espaces pour lesquels il n’appartient  pas aux skyline respectifs. Nous commençons par présenter quelques définitions  préliminaires.

DÉFINITION 3 (Sous-espaces de dominance).  —  Soit t ∈ T et X  ⊆ D. X  est un espace de dominance  pour t ssi $t \notin S k y(X)$.

DÉFINITION 4 (Skycube Négatif). —  Soit t ∈ T et soit DomSubspaces(t) l’en- semble des sous-espaces de dominance  de t. Le skycube négatif de T est l’ensemble {DomSubspaces(t) | t ∈ T }.

En d’autres termes, le skycube négatif maintient pour chaque tuple t, les sous- espaces dans lesquels t n’appartient  pas à leur skyline respectif.

EXEMPLE 5. — À   partir   du   tableau  3,   il    est    facile   de   vérifier   que DomSubspaces(t₁)  = {ABC D,  ABC,  AC D,  BC D,  AC,  BC,  C D,  C,  D}.

Clairement, si le skycube négatif de T est disponible, alors le calcul de tout skyline Sky(X ) est évident : pour chaque tuple t, t ∈ Sky(X ) ssi X  ∈ DomSubspaces(t). Donc, le skycube négatif de T apparaît comme le complémentaire  de son skycube (positif).

À présent, nous montrons que le skycube négatif peut être calculé plus efficace- ment que la solution naïve consistant à calculer d’abord le skycube positif et ensuite de dériver le kycube négatif. Nous commençons par montrer que la comparaison de t et t′ permet d’obtenir un ensemble de sous-espaces appartenant à DomSubspaces(t).

La définition suivante part de l’idée selon laquelle une seule comparaison pourrait permettre de déterminer un certain nombre d’espaces dans lesquels un tuple est do- miné. Par exemple, si à partir  du tableau 3, nous comparons t₂ à t₅ , nous observons que t₂ domine t₅ pour chacune des dimensions A, B et C . De ce fait, nous pouvons conjecturer  que t₅  n’appartient  à aucun skyline Sky(X ) tel que X  ⊆ ABC . par conséquent, cette unique comparaison nous a permis de déterminer le statut skyline de t5 par rapport aux sept sous-espaces non vides de ABC . Dans la suite, nous formali- sons cette intuition en commençant par définir ce que signifie comparer deux tuples.

DÉFINITION 6. — Soient t, t′  ∈  T . Nous définissons la fonction de comparaison COMP ARE comme suit : COMP ARE (t, t′) =  X |Y    tel que X est l’ensemble des dimensions Dj  telles que t′[Dj ] < t[Dj ] et Y  est l’ensemble  des dimensions  Dk pour lesquelles t et t′ sont égaux² . Alors, t[Dℓ ] < t′[Dℓ ] pour tout Dℓ ∈ D \ X ∪ Y .

Pour simplifier la notation, nous utilisons  COMP ARE (t) pour désigner l’en- semble ∪t′ ∈T {COMP ARE (t, t′)}.

EXEMPLE 7. — Du tableau 3, nous avons COMP ARE (t₅ , t₆ )  =  BC |D   parce que t₆ [B] < t₅ [B] (3 vs. 4), t₆ [C ] < t₅ [C ] (4 vs. 5) et les deux tuples sont égaux sur la dimension D (2). Nous avons COMP ARE (t₆ , t₅ ) = A|D .

2. Des paires similaires  sont définies dans (Bøgh et al., 2014) mais ne sont pas utilisées de la même façon.

Évidemment, si COMP ARE (t, t′) =$\langle X | Y\rangle$ alors X ∩ Y  = ∅.

DÉFINITION 8 (Couverture). —  Soit $\langle X | Y\rangle$  une paire d’espaces disjoints  et soit Z un espace. On dit que la paire$\langle X | Y\rangle$couvre Z ssi Z ⊆ X Y  et Z ∩ X = ∅.

EXEMPLE 9. — p = $\langle A C | B\rangle$ couvre  les espaces A, AB, C, AC, BC  et ABC . B n’est pas couvert par p car malgré le fait que B ⊆ AC B, on a B ∩ AC = ∅.

La proposition  suivante montre que les espaces couverts par la paire obtenue en comparant t à t′ sont précisemment les espaces dans lesquels t′ domine t.

PROPOSITION 10. —  Soit t, t′  ∈  T et soit COMP ARE (t, t′) =  $\langle X | Y\rangle$ . Alors, d’une part, t′ domine t en chacun  des espaces Z couverts par $\langle X | Y\rangle$ , c’est-à-dire, $t \notin S k y(Z)$. D’autre part, t′ ne domine t qu’en ces espaces.

PREUVE 11. — Soit Z un sous-espace couvert par la paire$\langle X | Y\rangle$. Alors, il existe deux sous-espaces disjoints  Z₁ et Z₂ tels que Z₁ ∪ Z₂ = Z , Z₁ ⊆ X , Z₂ ⊆ Y et  Z₁ = ∅. Z₁ ⊆ X implique que $t^{\prime} \prec z_{1} t$ et $Z_{2} \subseteq Y$ implique que $t^{\prime}\left[Z_{2}\right]=t\left[Z_{2}\right]$ donc $t^{\prime} \prec z=Z_{1} \cup z_{2} t$.  

En fait, COMP ARE (t, t′) est un résumé de l’ensemble  des espaces pour lesquels t est dominé par t′. Par conséquent, c’est un résumé d’une partie de l’ensemble  des espaces pour lesquels t n’appartient  pas aux skyline respectifs.

DÉFINITION 12. — Soit E  un ensemble de paires d’espaces. On note COV E R(E) l’ensemble  de tous les espaces couverts par au moins une des paires appartenant à E.

EXEMPLE  13. — COV E R({ A|B  ,  AD|∅ }) = {A, AB, D, AD}

DÉFINITION 14. — DOM(t) dénote l’ensemble  des espaces Z tels qu’il existe t′ qui domine t au regard de l’espace Z .

En d’autres termes, DOM(t) est l’ensemble  de tous les sous-espaces de D pour lesquels t est dominé. Donc 2^D \ DOM(t, T ) est l’ensemble  des sous-espaces pour lesquels t appartient au skyline.

À ce niveau,  il est possible  de présenter un algorithme construisant le skycube négatif. Cette structure peut alors être utilisée pour répondre aux requêtes skyline.

L’algorithme 1 montre comment cette structure de données est construite.  Son idée principale  est simplement  de comparer chaque paire de tuples (t, t′) et d’ajou- ter COMP ARE (t, t′) à l’ensemble  associé à t.

Dans le cas où COMP ARE (t, t′) est égal à la paire$\langle\mathcal{D} | \emptyset\rangle$ (voir ligne 5), cela signifie que t′ domine t en toutes les dimensions.  Par conséquent, t n’appartient  à aucun skyline et l’ensemble qui lui est associé peut être réduit à une seule paire.

EXEMPLE  15. — Du tableau 3, la structure de données retournée par BUILDNSC est présentée dans la table 4. Notons que les paires $\langle X | Y\rangle$  pour lesquelles X = ∅ ne sont pas considérées parce qu’elles  ne couvrent  aucun espace (voir Proposition 10).

rqhsxttdjke94_ajpp.png

Tableau 4. NSC relatif à T

L’algorithme 2 montre comment la structure de données précédente peut être uti- lisée pour exécuter une requête skyline Sky(Z ). Pour chaque tuple t, il scanne l’en- semble des paires qui lui sont associées. Si une paire couvrant Z est rencontrée, alors t n’appartient  pas à Sky(Z ) sinon t est un point skyline de Z .

3.1. Réduction de la taille de NSC

Réduire la taille de NSC (de l’ordre de O(n ∗ min(n, 2^d))) permet non seulement de réduire la consommation de mémoire mais en plus d’améliorer le temps de réponse des requêtes skyline.  Alors,  le problème que nous abordons ici consiste à 1) supprimer les tuples fallacieux, c’est-à-dire ceux qui n’appartiennent  à aucun skyline et 2) pour chaque tuple restant, trouver un ensemble minimal  de paires couvrant exactement les espaces couverts  par COMP ARE (t). Afin de donner une intuition à propos  de ce procédé, considérons l’exemple suivant.

EXEMPLE  16. — Supposons   D|∅ ∈ COMP ARE (t). Puisque cette paire couvre tous les sous-espaces, nous concluons  que t n’appartient  à aucun skyline. Donc, t et l’ensemble de paires qui lui est associé peuvent être supprimés de NSC.

EXEMPLE  17. — Soit p = ∅|Y  une paire associée à t. Clairement, COV E R(p) = ∅. De ce fait, la paire p peut être retirée sans que cela n’affecte  le résultat des requêtes skyline.

zd7sxa3u439iexf5on5.png

EXEMPLE $18 .-$ Soient $p_{1}=\langle A | B C\rangle$ et $ p_{2}=\langle A B | C\rangle$ deux paires as- sociées à $ t .$ COV\mathcal{E} \mathcal { R } $\left(\left\{p_{1}\right\}\right)=\{A, A B, A B C, A C\}$ et $\mathcal{C O V E} \mathcal{R}\left(\left\{\left(p_{2}\right\}\right)=\right.$ $\{A, A B, A B C, A C, B, B C\} .$ En raison de l'inclusion, $p_{1}$ peut être supprimé sans que cela n'affecte le résultat des requêtes skyline.

Le test d’inclusion  entre les paires peut être réalisé sans avoir  besoin de générer l’ensemble des espaces que celles-ci  couvrent.  En effet, rappelons que le nombre de sous-espaces couverts  est exponentiel  avec la taille de la paire, ce qui rend le test d’inclusion  coûteux à réaliser.

LEMME $19 .-$ Soient $p_{1}=\left\langle X_{1} | Y_{1}\right\rangle$ et $ p_{2}=\left\langle X_{2} | Y_{2}\right\rangle .$ Alors $\mathcal{C O V E \mathcal { R }}\left(\left\{p_{1}\right\}\right) \subseteq$ $\mathcal{C O V E R}\left(\left\{p_{2}\right\}\right)$ ssi $(i) X_{1} Y_{1} \subseteq X_{2} Y_{2}$ et (ii) $X_{1} \subseteq X_{2}$

PREUVE $20 .-$ Si $X_{1} Y_{1} \nsubseteq X_{2} Y_{2}$ alors $p_{2}$ ne peut pas couvrir l'espace $X_{1} Y_{1}$ tandis que $p_{1}$ le couvre. Supposons à présent que la condition (i) est satisfaite mais pas la condition (ii). Alors, il existe une dimension $D_{j} \in X_{1} \backslash X_{2} .$ La paire $p_{1}$ couvre le sous-espace $Z=D_{j}$ alors que ce n'est pas le cas pour $p_{2} .$ Donc la condition (ii) est nécessaire. Ce qui conclut la preuve.

L’égalité  suivante est immédiate :

$\mathcal{D} \mathcal{O} \mathcal{M}(t, T)=\mathcal{C} \mathcal{O} \mathcal{V} \mathcal{E} \mathcal{R}\left(\bigcup_{t^{\prime} \in T} \mathcal{C} \mathcal{M} \mathcal{P} \mathcal{A} \mathcal{R} \mathcal{E}\left(t, t^{\prime}\right)\right)$

Ainsi, matérialiser l’ensemble des paires $\bigcup_{t^{\prime} \in T} \mathcal{C O M P A R E}\left(t, t^{\prime}\right)$ pour chaque tuple t nous permet de savoir si t appartient au skyline relatif à n’importe quel sous-espace Z ∈ 2^D.

L’inconvénient de matérialiser l’ensemble $\bigcup_{t^{\prime} \in T} \mathcal{C O M P A R E}\left(t, t^{\prime}\right)$ est le fait qu’il pourrait contenir de la redondance. Dans la section suivante, nous montrons comment réduire le nombre de paires tout en conservant les propriétés.

3.1.1. Approches pour la réduction de la taille de NSC

Le problème de compression de NSC consiste à trouver, pour chaque tuple t, un ensemble P de taille minimale tel que COV E R(P ) = COV E R(COMP ARE (t)).

Nous abordons ce problème selon deux approches :

– Nous considérons en entrée l’ensemble  des paires associées à t et essayons de trouver un sous-ensemble minimal  de COMP ARE (t).

– Nous considérons  en entrée les espaces dans lesquels t est dominé et détermi- nons un ensemble minimal  de paires couvrant  ces espaces.

Du point de vue résumé, la solution de la seconde approche est naturellement  préfé- rable puisqu’elle est de plus petite taille.  Notons cependant que l’entrée de la première approche est de taille plus petite que celle de la seconde : les paires contre les espaces couverts par ces paires.

Notre problème pourrait être formalisé comme suit : étant donné un tuple t et l’ensemble de paires qui lui est associé COMP ARE (t), comment déterminer un ensemble minimal  de paires E∗ tel que COV E R(E∗) = COV E R(COMP ARE (t))?

Ce problème peut également être reformulé  de deux manières :

(i) le problème sous contrainte de ressource : E∗ ⊆ COMP ARE (t);

(ii)  le problème  sans contrainte  : E∗  n’est pas forcement  un sous-ensemble de

COMP ARE (t).

La section suivante (section 3.1.2) aborde le problème sous-contrainte d’inclusion

(3.1.1) tandis que la section 3.1.3 aborde le problème  sans cette contrainte  (3.1.1).

3.1.2. Minimisation  de COMP ARE (t)

Soit E  un ensemble de paires, l’objectif de cette partie est de trouver un autre ensemble de paires E∗  ⊂ E dont la cardinalité  (nombre de paires) est la plus petite possible et tel que COV E R(E∗) = COV E R(E)

EXEMPLE  21. — Soit p1  =  AB|C  , p2  =  BC |A   et p3  =  AC |∅  trois paires associées au tuple t. Il est facile d’observer qu’il n’y a pas d’inclusion  entre les en- sembles d’espaces couverts par ces paires. Mais, la paire p3 peut être retirée. En effet, COV E R(p3 ) = {A, AC, C }. A et AC sont couverts par p1 tandis que C est couvert par p2 . Donc, la paire p3 est redondante.

Nous avons COV E R(E∗   = {P3 }) = COV E R(E), donc matérialiser E∗  est moins coûteux que de matérialiser E pour deux raisons :

– E∗ requiert moins d’espace que E;

– requêter E∗  (vérifier qu’un espace Z est couvert)  est plus rapide que requêter E.

Le problème abordé dans cette section peut alors être formalisé comme suit :

Le théorème suivant établit la difficulté du problème RSP.

THÉORÈME  22. — RSP est NP-Difficile.

PREUVE 23. — (esquisse) Évidemment,  ce problème  de minimisation   est NP. La preuve qu’il est NP-Difficile est basée sur la réduction à partir du problème de l’en- semble minimal couvrant (minimal set cover,  MSC). Étant donnée une instance de problème MSC, nous construisons une table T de tuples distincts t dans laquelle le nombre de dimensions d est égal au nombre d’éléments devant être couverts dans MSC et où le nombre de tuples n est égal au nombre initial d’ensembles dans MSC.

Nous établissons une correspondance entre E et les ensembles de MSC et mon- trons que toute solution de MSC est une solution de RSP.

Soit s = {s₁ , s₂ , . . . , s_n } l’ensemble d’ensembles d’éléments, entrée de l’instance du problème MSC. Soit t = (1, 1, . . . , 1) un tuple ayant d valeurs. Pour chaque en- semble s_j∈ MSC, nous ajoutons  à T un tuple t′ tel que t′[i] = 0 ssi i ∈ sj  sinon t′[i] = 1. Par conséquent, COMP ARE (t, t′) =  X |Y   ssi ∃s ∈ MSC tel que X = s.

Par exemple, soit s = {s₁  = {1, 2}; s₂  = {2, 3}; s₃  = {1, 3}} l’instance de MSC. Le nombre d’éléments à couvrir  est d = 3 et le nombre d’ensembles n = 3. Alors, nous obtenons la table T ayant n + 1 = 4 tuples (incluant t) et 3 dimensions. Ceci est illustré par le tableau suivant.

Il y a une correspondance entre les s_i ∈ s et les pi  = C ompare(t, ti ). Par exemple, Compare(t, t₁ ) =$\langle 12 | 3\rangle$  correspond  à s₁  = {1, 2}. De ce fait, il peut être prouvé qu’un ensemble si  appartient  à la solution de l’instance  de MSC ssi sa paire corres- pondante appartient à la solution du problème RSP.

vwfqmknfk0f2jp5tunm.png

Dans (Chvatal, 1979), un algorithme glouton approximatif  en temps polynomial a été proposé pour résoudre le problème MSC. Cet algorithme  choisit à chaque étape l’ensemble couvrant le plus grand nombre d’éléments non encore couverts par les ensembles précédemment choisis. L’adaptation  de cet algorithme pour résoudre le problème RSP est évidente et présentée à travers l’algorithme 3. Il s’agit dans notre cas de choisir,  à chaque itération  la paire couvrant le plus grand nombre d’espaces non encore couverts par les paires déjà choisies.

L’algorithme 4 montre comment créer une liste réduite  de paires associées à un tuple. Cet algorithme appelle la fonction ApproxMPC qui est une adaptation  de la proposition de (Chvatal, 1979) au problème RSP.

EXEMPLE  24. — Le résultat de la minimisation  du tableau 4 utilisant l’algorithme 4 est présenté dans le tableau 5. Notons que le nombre de paires est passé de 20 à 8.

Tableau 5. Liste des paires synthétisant les ensembles de dominance

3.1.3. Minimisation sans contrainte  d’inclusion

Il est important  de préciser que la solution exacte du problème RSP ne présente pas la garantie d’être le plus petit ensemble de paires codant l’ensemble  des espaces dans lesquels t est dominé.  Son idée maîtresse est juste de retirer  les paires redon- dantes. Une autre manière d’aborder ce problème de minimisation  est de considérer l’ensemble U des espaces couverts par l’ensemble  des paires P associées au tuple t et d’essayer de dériver un ensemble minimal  de paires Q qui couvre U . Notons que Q n’est pas forcement inclus dans P . Nous illustrons la différence entre les deux ap- proches à travers l’exemple  suivant.

EXEMPLE  25. — Soit P  = { AB|C  ,  BC |A  } l’ensemble  des paires associées à t. P est minimal dans ce sens qu’il est imposible  d’en retirer une paire quelconque tout en couvrant l’ensemble des espaces couverts  par P . Notons cependant que Q = { ABC |∅ } couvre  exactement les mêmes espaces que P et est de taille plus petite.

La difficulté que nous rencontrons à résoudre ce problème tient du fait que le sky- line n’est pas monotone,  c’est-à-dire$Y \subseteq X \not=S k y(Y) \subseteq S k y(X)$. La consé- quence de cette propriété  dans notre travail peut être présentée comme  suit : soit X  ∈ DOM(t). On pourrait être tenté de coder cette information  par la paire $\langle X | \emptyset\rangle$. Cependant, cette paire couvre tous les sous-espaces de X alors qu’il est possible qu’il existe un sous-espace Y   ⊆ X  tel que t ∈ Sky(Y ). Dans la suite, nous mettons en exergue quelques propriétés nous permettant d’accomplir  notre tâche consistant à ré-sumer cette information.

LEMME $26 .-$ Soit $t \in | T$ et soient $X, Y$ deux espaces. Si $t \notin S k y_{T}(X Y)$ et $t \in\operatorname{Sky}_{T}(X)$ alors $t \notin \operatorname{Sky}_{T}(Y)$

PREUVE 27 (par l'absurde). $-$ Supposons que $t \underbrace{t \in S k y_{T}(X)}_{(1)}, \underbrace{t \in S k y_{T}(Y)}_{(2)}$ et $\underbrace{t \notin S k y_{T}(X Y)}_{(3)}$

De $(1)$ et $(3),$ il existe $u \in S k y_{T}(X)$ tel que $\underbrace{u[X]=| t[X]}_{(4)}$ et $\underbrace{u \prec Y}_{(5)}$

De $(2)$ et $(3),$ il existe $v \in S k y_{T}(Y)$ tel que $\underbrace{v[Y]=t[Y]}_{(6)}$ et $\underbrace{v \prec x t}_{(7)}$

Nous obtenons une contradiction entre (1) et (7) car t est dominé au regard de X et t appartient au skyline de X. Nous obtenons également une contradiction entre (2) et (5) car t est dominé au regard de Y et t appartient au skyline de Y .

Ceci implique que, si $X \in \mathcal{D} \mathcal{O} \mathcal{M}(t)$ alors il existe au plus un fils $X_{1}$ de $X^{3}$ tel que $X_{1} \notin \mathcal{D} \mathcal{O} \mathcal{M}(t) .$

Ce résultat peut être expliqué par le fait que pour tous $X_{1}, X_{2},$ deux sous-espaces distincts tels que $\left|X_{1}\right|=\left|X_{2}\right|=|X|-1,$ nous avons $X_{1} \cup X_{2}=X .$ En appliquant la proposition $26,$ si $t \notin S k y_{T}(X)$ et $t \in S k y_{T}\left(X_{1}\right)$ alors $t \notin S k y_{T}\left(X_{2}\right) ;$ alors il existe au plus un fils $X_{1}$ de $X$ tel que $t \in S k y_{T}\left(X_{1}\right) .$

En allant plus loin, nous pouvons généraliser en établissant le résultat suivant. Intuitivement, il déclare qu'il existe au plus un plus grand sous-espace $Z$ de $X$ tel que $t \in S k y(Z)$ tandis que $t \notin S k y(X) .$ Formellement, Proposition $28 .-$ soit $X \in \mathcal{D O M}(t) .$ Alors l'ensemble $\underset{Z \subset X, Z \notin \mathcal{D} \mathcal{O} \mathcal{M}(t)}{\operatorname{Argmax}}|Z|$

contient au plus un element.

Ceci signifie que si $t \notin$ Sky $(X)$ alors il existe au plus un sous-espace $Z \subset X$ de taille maximale (en nombre d'attributs) tel que $t$ appartient au skyline de $Z .$

PREUVE $29 .-$ Supposons qu'il existe deux sous-espaces $X_{1}$ et $X_{2}$ de taille maxi- male tels que $X_{1} \notin \mathcal{D} \mathcal{M}(t)$ et $X_{2} \notin \mathcal{D} \mathcal{O} \mathcal{M}(t)$ alors $X_{1} \cup X_{2} \notin \mathcal{D} \mathcal{M}(t)$ $\text { (voir Proposition } 26) .$ De plus, puisque $X_{1} \cup X_{2} \subseteq X$ et $X_{1} \neq X_{2}$ alors $\left|X_{1} \cup X_{2}\right|>\max \left(\left|X_{1}\right|,\left|X_{2}\right|\right) .$ Il $\mathrm{y}$ a une contradiction car soit $X_{1} \cup X_{2}=X$ $\text { (mais } X \in \mathcal{D} \mathcal{O} \mathcal{M}(t)),$ soit $X_{1}$ et $X_{2}$ n'appartiennent pas à a la solution de (i).

De la proposition précédente, nous pouvons déduire le résultat suivant qui intui- tivement montre que si $Y$ est le plus grand sous-espace de $X$ tel que $t \notin$ Sky $(X)$ et $t \in S k y(Y)$ alors chaque $Z \subseteq X$ tel que $t \in S k y(Z)$ est nécessairement un sous-espace de $Y .$ Formellement, PROPOSITION $30 .-$ Soit $X \in \mathcal{D} \mathcal{O M}(t),$ Soit $Y=\underset{Z \subset X, Z \notin \mathcal{D} \mathcal{O} \mathcal{M}(t)}{\operatorname{Argmax}}|Z|$ alors $\forall Z \subset$ $X$ tel que $Z \notin \mathcal{D O M}(t)$ nous obtenons $Z \subseteq Y$

3. $X_{1}$ est un fils de $X$ ssi $X_{1} \subset X$ et $\left|X_{1}\right|=|X|-1$

PREUVE 31 (par l'absurde). - Soit $W \subset X$ tel que $X \notin \mathcal{D O M}(t)$ et $W \nsubseteq Y$ alors $W \cup Y \subseteq X$ et $W \cup Y \notin \mathcal{D O M}(t)$ (car $W$ et $Y$ n'appartiennent pas à $\mathcal{D O M}(t),$ voir Proposition 26), alors il y a une contradiction car $|W \cup Y|>|Y|$ $Y \neq \operatorname{Argmax}_{Z \subset X, Z \notin \mathcal{D} \mathcal{O} \mathcal{M}(t)}|Z| .$

Intuitivement, ce résultat établit que chaque sous-espace de $X \in \mathcal{D} \mathcal{M}(t)$ qui $\text { n' appartient pas à } \mathcal{D} \mathcal{O} \mathcal{M}(t) \text { est inclus dans un autre espace (noté } Y)$ pour lequel $t$ appartient au skyline. Alors, chaque sous-espace appartenant à $2^{X} \backslash 2^{Y}$ appartient à $\mathcal{D O M}(t),$ de ce fait, $\langle X \backslash Y | Y\rangle$ est la paire couvrant à la fois $X$ et le maximum de sous-espaces de $X$ inclus dans $\mathcal{D} \mathcal{O} \mathcal{M}(t) .$

La propriété précédente peut être exploitée pour résoudre le probleme MSP comme suit: soit $X \in \mathcal{D} \mathcal{O} \mathcal{M}(t) .$ Alors $X$ correspond à la paire $\langle X \backslash Y | Y\rangle$ telle que $Y$ est le plus grand sous-espace de $X$ tel que $t \in S k y(Y) .$ Si chaque $X \in \mathcal{D} \mathcal{O} \mathcal{M}(t)$ est remplacé comme décrit précédemment, alors nous obtenons un ensemble de paires dont la minimisation consiste simplement à supprimer les paires $p_{i}$ telles qu'il existe une paire $p_{j}$ qui la couvre. Cette procédure est décrite dans l'algorithme $5 .$

(1) nous montrons tout d'abord que OutputSet couvre tous les espaces apparte- nant à $\mathcal{D} \mathcal{O} \mathcal{M}(t)$ ; et ne couvre que ceux-ci (double inclusion).

(a) nous commençons par montrer que $\mathcal{C O V E R}(p) \subseteq \mathcal{D O M}(t), \forall p \in$ OutputSet. Soit $\langle W | T\rangle$ une paire appartenant à OutputSet, Test (par construction) le plus grand sous-espace de $W T$ qui n'appartient pO\mathcal{M} ( t ) . ~ A l o r s ~ $T$ inclut tout $\text { sous-espace de } W T \text { n'appartenant pas à } \mathcal{D} \mathcal{O} \mathcal{M}(t) \text { (voir Proposition } 30),$ alors $2^{W T}$ $2^{T}=\mathcal{C} \mathcal{O} \mathcal{V} \mathcal{E} \mathcal{R}(\langle W | T\rangle) \subseteq \mathcal{D} \mathcal{O} \mathcal{M}(t)$

(b) nous avons montré que pour chaque espace Z  appartenant  à DOM(t) il existe une paire de OutputSet qui couvre Z . Chaque itération (voir cinquième ligne) de l’algorithme ajoute à OutputSet une paire qui couvre un espace de DOM(t), non encore couvert par les paires ajoutées précédemment. Et l’algorithme a dans le pire cas une complexité  en temps de O(m²) où m est la taille de l’entrée. Alors, l’algorithme s’arrête après un temps fini, lorsque tous les espaces appartenant  à DOM(t) sont couverts par au moins une paire de OutputSet

(2) Ensuite, montrons que OutputSet est de taille minimale.  Supposons que lp soit une liste de paires couvrant  exactement  les espaces de DOM(t). Nous allons montrer qu’il existe une fonction injective f allant de OutputSet vers lp ce qui reviendrait  à dire que la taille de OutputSet est plus petite (ou égale à) la taille de tout lp. Pour f , nous choisissons la fonction qui associe à chaque paire $\langle X | Y\rangle$∈ OutputSet la paire $\langle x | y\rangle \in l p$ telle que $\langle x | y\rangle$ couvre $X Y(\text { s'il y a plusieurs paires satisfaisant cette }$ condition, alors nous choisissons la plus petite dans l'ordre lexicographique).

bbrn6wqm69tuj_hpjtah.png

(a) Montrons que la fonction $f$ est definie pour toute paire $\langle X | Y\rangle \in$ Outputset, $\forall\langle X | Y\rangle \in$ Output Set, l'espace $X Y$ appartient à $\mathcal{D} \mathcal{O} \mathcal{M}(t)$ donc il existe au moins une paire $p \in l p$ telle que $p$ couvre $X Y .$

(b) Montrons enfin que la fonction $f$ est injective; en d'autres termes, ceci est équivalent à montrer que pour tous $\left\langle X_{1} | Y_{1}\right\rangle$ et $\left\langle X_{2} | Y_{2}\right\rangle$ , deux paires appartenant à OutputSet, il n'existe pas de paire $\langle x | y\rangle \in$ lp couvrant à la fois $ X_{1} Y_{1}$ et $X_{2} Y_{2}$ . Par l'absurde, supposons qu'il existe une telle paire $\langle x | y\rangle \in l p ;$ alors $\underbrace{X_{1} Y_{1} \subseteq x y}_{\text {(1) }}$ (1) et $\underbrace{X_{1} Y_{1} \cap x \neq \emptyset}_{(2)}$ aussi bien que $\underbrace{X_{2} Y_{2} \subseteq x y}_{(3)}$ et $\underbrace{X_{2} Y_{2} \cap x \neq \emptyset}_{(4)}(1)$ et $(3)$ impliquent que $X_{1} Y_{1} \cup X_{2} Y_{2} \subseteq x y$ et $(2)$ et $(4)$ impliquent que $\left(X_{1} Y_{1} \cup X_{2} Y_{2}\right) \cap x y \neq \emptyset$ alors $X_{1} Y_{1} \cup$ $X_{2} Y_{2} \in \mathcal{D} \mathcal{O} \mathcal{M}(t) .$ Donc, il existe aussi une paire $\langle X | Y\rangle \in$ OutputSet couvrant $ X_{1} Y_{1} \cup X_{2} Y_{2}$ ce qui implique que $X \cap\left(X_{1} Y_{1} \cup X_{2} Y_{2}\right) \in \emptyset$ , en d'autres termes $X_{1} Y_{1} Y_{1} \neq \emptyset$ ou $X \cap X_{2} Y_{2} \neq \emptyset$ . Donc, $\langle X | Y\rangle$ couve $\left\langle X_{1} | Y_{1}\right\rangle$ ou $\left\langle X_{2} | Y_{2}\right\rangle$ ce qui est absurde car, par construction de l'algorithme, 5 ne peut pas ajouter à Output Set $\left.\text { la paire }\left\langle X_{1} | Y_{1}\right\rangle\left(\text { resp. }\left\langle X_{1} | Y_{1}\right\rangle\right) \text { si l'espace } X_{1} Y_{1} \text { (resp. } X_{2} Y_{2}\right)$ est déja couvert par une autre paire ajoutée $(\langle X | Y\rangle) .$

3.1.4. Comparer les tuples au Topmost suffit

Dans cette partie, nous montrons que pour construire notre structure de données, il suffit de comparer les tuples à ceux appartenant au em topmost skyline c'est-à dire $S k y(\mathcal{D}),$ au lieu de les comparer à l'ensemble des tuples de la table $T .$ Ceci est particulièrent intéressant lorsque la taille du topmost skyline est petite par rapport à $n$ .

THEOREME $34 .-$ Soit $E=\bigcup_{t^{\prime} \in S \text {ky}(\mathcal{D})} c \mathcal{M} \mathcal{P} \mathcal{A} \mathcal{E} \mathcal{E}\left(t, t^{\prime}\right)$ Alors $\mathcal{C O V E R}(E)=\mathcal{C O V E R}(\mathcal{C O M P A R E}(t))$ PREUVE $35 .-$ On sait que $\mathcal{C O M P A R E}(t)=\bigcup_{t^{\prime} \in T o p m o s t} \mathcal{C O M P A R E}\left(t, t^{\prime}\right) \cup \bigcup_{t^{\prime} \notin \text {Topmost}} \mathcal{C O M P A R E}\left(t, t^{\prime}\right)$ or $\quad \bigcup \quad \mathcal{C O M P A R E}\left(t, t^{\prime}\right)=E .$ En raison de la distributivité de l'opérateur $\mathcal{C} \mathcal{O} \mathcal{V} \mathcal{E} \mathcal{R}$ sur l'union nous pouvons écrire $\mathcal{C O V E R}(\mathcal{C O M P A R E}(t))=\mathcal{C O V E R}(E) \cup \mathcal{C O V E R}\left(\bigcup_{t^{\prime} \notin \text {Topmost}} \mathcal{C O M P A R E}\left(t, t^{\prime}\right)\right)$

Il suffit alors de prouver que$\operatorname{cov} \varepsilon \mathcal{R}\left(\underset{t^{\prime} \notin \text {Topmost}}{\bigcup} \operatorname{cod} \mathcal{P} \mathcal{A} \mathcal{R} \mathcal{E}\left(t, t^{\prime}\right)\right) \subset \operatorname{coveR}(E)$

En d'autres termes, on pourrait juste montrer que pour tout $t^{\prime} \notin$ Topmost,$\operatorname{cov} \varepsilon \mathcal{R}\left(\mathcal{C} \mathcal{O} \mathcal{M P} \mathcal{A} \mathcal{E} \mathcal{E}\left(t, t^{\prime}\right)\right) \subseteq \mathcal{C} \mathcal{O} \mathcal{V} \mathcal{E} \mathcal{R}(E)$

Soit $t^{\prime}$ un tuple de $T$ tel que $t^{\prime} \notin$ Topmost. par définition du skyline, il existe un tuple $u \in$ Topmost tel que $u$ domine $t^{\prime},$ c'est-à-dire, $u \prec \rho t^{\prime} .$ Soit $\left\langle X_{1} | Y_{1}\right\rangle=$ $\mathcal{C} \mathcal{O} \mathcal{M P} \mathcal{A} \mathcal{R} \mathcal{E}(t, u)$ et $\left\langle X_{2} | Y_{2}\right\rangle=\mathcal{C} \mathcal{O} \mathcal{M} \mathcal{P} \mathcal{A} \mathcal{R}\left(t, t^{\prime}\right) .$ Pour chaque sous-espace $Z$ couvert par $\left\langle X_{2} | Y_{2}\right\rangle,$ nous avons $(i) t^{\prime} \prec z$ t. De plus, $u \prec \mathcal{D} t^{\prime}$ implique que $(i i)$ $u \preceq z t^{\prime}(\operatorname{car} Z \subseteq \mathcal{D}) .$

De $(i)$ et (ii) on a $u \prec z t ;$ donc $Z$ est couvert par $\left\langle X_{1} | Y_{1}\right\rangle .$ Tout espace couvert par $\left\langle X_{2} | Y_{2}\right\rangle$ est aussi couvert par $\left\langle X_{1} | Y_{1}\right\rangle$

Par conséquent, pour tout $t^{\prime} \notin$ Topmost, la paire $\mathcal{C} \mathcal{M P} \mathcal{A} \mathcal{R} \mathcal{E}\left(t, t^{\prime}\right)$ est redon- dante dans la liste de paires associées au tuple $t .$

Tableau 6. Données réelles

EXEMPLE  36. — De notre exemple précédent, puisque le topmost skyline est consti- tué des tuples  t₂ , t₃  et t₄ , les tuples  seront  uniquement  comparés à ceux-ci. Par exemple, la liste de paires associée au tuple t1 est { C |ABD  ,  C D|∅ } dont la taille est 2 en considérant le T opmost au lieu d’un ensemble de 3 paires si on avait comparé t1 à l’ensemble  des tuples.

En plus du gain d’espace dû à la réduction du nombre de comparaisons pour chaque tuple, cette optimisation  rend l’algorithme glouton utilisé pour résoudre le problème RSP plus rapide en raison de la réduction de la taille de l’entrée.

Nous avons présenté la structure skycube négatif et fourni les algorithmes permet- tant de la réduire. L’idée maîtresse de cette structure est de stocker pour chaque tuple un résumé de l’ensemble  des sous-espaces pour lesquels il n’appartient  pas au sky- line. Ceci est en contradiction  avec les anciens travaux où l’objectif était de résumer l’ensemble des sous-espaces pour lesquels le tuple appartient au skyline. Nos expéri- mentations ont montré que NSC est particulièrement  efficace en termes de temps de construction, d’utilisation  de la mémoire et de temps de réponse. Dans les précédents travaux, soit les algorithmes  demandaient beaucoup de temps pour la construction, soit la structure de données produite était trop grande pour tenir en mémoire. Nos ex- périmentations montrent également que cette structure est plus rapide pour construire le skycube que les algorithmes de l’état de l’art spécialement conçus dans cet objectif.

Une autre propriété  intéressante est sa faculté à pouvoir  répondre efficacement  à une autre forme  de requête qui est la requête k-dominant  skyline. Dans les travaux futurs, nous prévoyons de proposer une solution  à la maintenance incrémentale de la structure NSC. Cette possibilité  est le principal avantage de la structure Compres- sed Skycube  (CSC) bien qu’elle souffre, comme nous l’avons vu, de l’inefficacité de l’exécution  des requêtes. Nous envisageons également d’adapter notre structure à la représentation binaire Hashcube. Ceci aura pour effet de réduire encore plus nos temps de réponse aux requêtes.