Merkl, T. C., Pichler, R., & Skritek, S. (2023). Diversity of Answers to Conjunctive Queries. In F. Geerts & B. Vandevoort (Eds.), 26th International Conference on Database Theory (pp. 10:1-10:19). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPICS.ICDT.2023.10
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Published in:
26th International Conference on Database Theory
-
ISBN:
978-3-95977-270-9
-
Volume:
255
-
Date (published):
2023
-
Event name:
26th ICDT - International Conference on Database Theory (ICDT 2023)
en
Event date:
28-Mar-2023 - 31-Mar-2023
-
Event place:
Ioannina, Greece
-
Number of Pages:
19
-
Publisher:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, Saarbrücken/Wadern, Germany
-
Peer reviewed:
Yes
-
Keywords:
Query Answering; Diversity of Solutions; Complexity; Algorithms; Conjunctive Queries; Analyze; data complexity
en
Abstract:
Enumeration problems aim at outputting, without repetition, the set of solutions to a given problem instance. However, outputting the entire solution set may be prohibitively expensive if it is too big. In this case, outputting a small, sufficiently diverse subset of the solutions would be preferable. This leads to the Diverse-version of the original enumeration problem, where the goal is to achieve a certain level d of diversity by selecting k solutions. In this paper, we look at the Diverse-version of the query answering problem for Conjunctive Queries and extensions thereof. That is, we study the problem if it is possible to achieve a certain level d of diversity by selecting k answers to the given query and, in the positive case, to actually compute such k answers.
en
Project title:
HyperTrac: hypergraph Decompositions and Tractability: P30930-N35 (FWF - Österr. Wissenschaftsfonds)
CC BY 4.0
