@inproceedings{04acd999bccc40e0bd2720ae01a24a89,
title = "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.",
keywords = "Certain answer, Partial order, Possible answer, Uncertain data",
author = "Antoine Amarilli and Ba, \{Mouhamadou Lamine\} and Daniel Deutch and Pierre Senellart",
year = "2017",
month = oct,
day = "1",
doi = "10.4230/LIPIcs.TIME.2017.4",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Sven Schewe and Jef Wijsen and Thomas Schneider",
booktitle = "24th International Symposium on Temporal Representation and Reasoning, TIME 2017",
note = "24th International Symposium on Temporal Representation and Reasoning, TIME 2017 ; Conference date: 16-10-2017 Through 18-10-2017",
}