Abstract | ||
---|---|---|
To combine and query ordered data from multiple sources, one needs to handle uncertainty about the possible orderings. Examples of such 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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.4230/LIPIcs.TIME.2017.4 | TIME |
DocType | Volume | Citations |
Conference | abs/1707.07222 | 2 |
PageRank | References | Authors |
0.36 | 20 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Antoine Amarilli | 1 | 67 | 17.90 |
Mouhamadou Lamine Ba | 2 | 35 | 5.15 |
Daniel Deutch | 3 | 345 | 41.49 |
Pierre Senellart | 4 | 946 | 63.47 |