ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 20/5 - 2015  - pp.9-26  - doi:10.3166/isi.20.5.9-26
TITRE
Dépendances fonctionnelles et requêtes skyline multidimensionnelles

TITLE
Functional dependencies and skyline queries

RÉSUMÉ
Soit la table T(Id, D1, . . . , Dd), le skycube de T est l’ensemble de tous les skylines qu’on peut obtenir à partir de T en considérant chacun des sous-ensembles de dimensions (sous-espaces) de {D1, . . . , Dd}. Afin d’optimiser les requêtes skyline multidimensionnelles, les solutions proposées dans la littérature consistent (i) à calculer et matérialiser tous les skylines, i.e., matérialiser le skycube ou bien (ii) à proposer des techniques de compression du skycube de sorte que la réponse aux requêtes skyline soit immédiate. Clairement, (i) stocker tout le skycube est infaisable en pratique quand d est grand car le nombre de skylines est exponentiel en fonction de d et (ii) comme nous le montrons expérimentalement, les techniques de compression n’arrivent pas à passer à l’échelle dès lors que d devient assez grand (à partir de 10 dimensions). Dans cet article nous montrons que le concept classique des dépendances fonctionnelles (DF) peut aider à optimiser les requêtes skyline multidimensionnelles. Celles-ci permettent d’identifier des situations où l’on a des inclusions entre skyline. Nous exploitons cette propriété dans deux cas de figure : soit l’utilisateur veut matérialiser tout le skycube, soit une matérialisation partielle est requise. Nous présentons quelques résultats expérimentaux montrant la supériorité de notre approche par rapport à des solutions de l’état de l’art.


ABSTRACT
Given a table T(Id, D1, . . . , Dd), the skycube of T is the set of skylines w.r.t. every subsets of dimensions (subspace) {D1, . . . , Dd}. In order to optimize these skyline queries, the solutions proposed so far in the literature either (i) precompute all the skylines or (ii) they propose compression techniques so as the derivation of every skyline is performed with little effort. Clearly, solutions (i) do not scale when d is large because of the exponential number of skylines. Solutions (ii) are appealing in terms of skyline derivation but they too suffer from a high computation complexity making them unfeasible in practice. In this paper, we propose a new formalization of the optimization problem: find a minimal set of skylines sufficient to answer every remaining skyline queries while avoiding to access the possibly large underlying data. Our solution can be seen as a trade off between valuation, computational cost for finding what to materialize and the memory space usage. To solve this problem, we need to know if the skyline wrt some dimension set X is included into that w.r.t. Y provided X is included into Y . Because Ingénierie des systèmes d’information – no 5/2015, 9-26 10 ISI. Volume 20 – no 5/2015 of the non-monotonic nature of skylines, it is hard to establish this relationship. By exploiting the classical concept of functional dependencies, we identify cases where the inclusion holds. Equipped with this information, we show how to find the smallest set of skylines to materialize. We conduct a thorough experimental study showing that with the help of a small number of materialized skylines, we drastically reduce the execution time of the remaining skyline queries. We also propose an algorithm for the full materialization of skycubes and compare it to state of the art solutions. We show that our proposal outperforms previous work both on real and synthetic data especially with large dimensionality and/or data size. Finally, we compare our proposal to the closed skycube technique and we show empirically that in general our solution uses less storage space and more importantly, it is orders of magnitude faster to obtain when the number of dimensions increases.


AUTEUR(S)
Nicolas HANUSSE, Patrick KAMNANG WANKO, Sofian MAABOUT, Carlos ORDONEZ

MOTS-CLÉS
Skyline, optimisation, dépendances fonctionnelles.

KEYWORDS
Skyline, functional dependencies, optimization.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (313 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier