| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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.
Cited literature [25 references]
https://hal.inria.fr/hal-01570603
Contributor : Pierre Senellart <>
Submitted on : Monday, July 31, 2017 - 12:20:05 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:36 PM
Contributor : Pierre Senellart <>
Submitted on : Monday, July 31, 2017 - 12:20:05 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:36 PM
File
1707.07222.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License