Possible and Certain Answers for Queries over Order-Incomplete Data

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 :
Pré-publication, Document de travail
55 pages, 5 figures, 1 table, 44 references. Accepted at TIME'17. This paper is the full version .. 2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01614571
Contributeur : Pierre Senellart <>
Soumis le : mercredi 11 octobre 2017 - 10:37:28
Dernière modification le : jeudi 11 janvier 2018 - 06:21:19

Identifiants

Citation

Antoine Amarilli, Mouhamadou Lamine Ba, Daniel Deutch, Pierre Senellart. Possible and Certain Answers for Queries over Order-Incomplete Data. 55 pages, 5 figures, 1 table, 44 references. Accepted at TIME'17. This paper is the full version .. 2017. 〈hal-01614571〉

Partager

Métriques

Consultations de la notice

103