Requêtes sur des données à ordre incomplet

Résumé :

Combiner des données ordonnées qui proviennent de différentes sources exige de recourir à un formalisme de données à ordre incomplet qui puisse représenter l’incertitude sur les différents ordres possibles. Des exemples d’application sont des listes d’établissements, tels des hôtels ou des restaurants, triés suivant une fonction inconnue représentant leur pertinence pour une requête, ou leur évaluation par des clients ; des documents édités de façon concurrente avec plusieurs manières possibles d’ordonner les contributions individuelles ; des résultats d’intégration de séquences d’événements comme des données de capteurs ou des entrées de fichiers journaux. Le présent travail étend l’algèbre relationnelle positive aux données ordonées et aux données à ordre incomplet, et introduit un ensemble d’axiomes pour guider la conception d’une sémantique multiensembliste pour le langage. Nous introduisons deux telles sémantiques, et montrons que l’une d’entre elles est la plus générale possible pour notre ensemble d’axiomes. Nous construisons ensuite un système de représentation au sens fort pour ces sémantiques, qui s’appuie sur des ordres partiels interprétés suivant une sémantique des mondes possibles. Nous étudions l’expressivité de notre langage de requêtes, en le rattachant à des mesures de complexité sur les ordres partiels. Nous introduisons un opérateur de top-k pour extraire les k premiers éléments de l’ordre, et étudions la complexité de l’évaluation de requêtes, au sens des réponses possibles et des réponses certaines. Nous complétons finalement le langage avec un opérateur qui permet d’éliminer les doublons, et investiguons l’impact de cette modification sur nos résultats.

Document type :
Conference papers
Complete list of metadatas

https://hal.telecom-paristech.fr/hal-02288441
Contributor : Telecomparis Hal <>
Submitted on : Saturday, September 14, 2019 - 6:49:12 PM
Last modification on : Thursday, October 17, 2019 - 12:36:59 PM

Identifiers

  • HAL Id : hal-02288441, version 1

Citation

Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch, Pierre Senellart. Requêtes sur des données à ordre incomplet. BDA, Sep 2015, Porquerolles, France. ⟨hal-02288441⟩

Share

Metrics

Record views

12