Possible and Certain Answers for Queries over Order-Incomplete Data

Antoine Amarilli 1 Mouhamadou Lamine Ba 2 Daniel Deutch 3 Pierre Senellart 4, 5
1 DBWeb
LTCI - Laboratoire Traitement et Communication de l'Information
5 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : To combine and query ordered data from multiple sources, one needs to handle uncertainty about the possible orderings. Examples of such “order-incomplete” data include integrated event sequences such as log entries; lists of properties (e.g., hotels and restaurants) ranked by an unknown function reflecting relevance or customer ratings; and documents edited concurrently with an uncertain order on edits. This paper introduces a query language for order-incomplete data, based on the positive relational algebra with order-aware accumulation. We use partial orders to represent order-incomplete data, and study possible and certain answers for queries in this context. We show that these problems are respectively NP-complete and coNP-complete, but identify many tractable cases depending on the query operators or input partial orders.
Type de document :
Communication dans un congrès
Sven Schewe; Thomas Schneider; Jef Wijsen. 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), Oct 2017, Mons, Belgium. Schloss Dagstuhl, Leibniz International Proceedings in Informatics, 90, pp.4:1-4:19, 〈http://informatique.umons.ac.be/time2017/〉. 〈10.4230/LIPIcs.TIME.2017.4〉
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01570603
Contributeur : Pierre Senellart <>
Soumis le : lundi 31 juillet 2017 - 12:20:05
Dernière modification le : mardi 19 juin 2018 - 10:44:02

Fichier

1707.07222.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch, Pierre Senellart. Possible and Certain Answers for Queries over Order-Incomplete Data. Sven Schewe; Thomas Schneider; Jef Wijsen. 24th International Symposium on Temporal Representation and Reasoning (TIME 2017), Oct 2017, Mons, Belgium. Schloss Dagstuhl, Leibniz International Proceedings in Informatics, 90, pp.4:1-4:19, 〈http://informatique.umons.ac.be/time2017/〉. 〈10.4230/LIPIcs.TIME.2017.4〉. 〈hal-01570603〉

Partager

Métriques

Consultations de la notice

304

Téléchargements de fichiers

35