Timo Camillo Merkl ; Reinhard Pichler ; Sebastian Skritek - Diversity of Answers to Conjunctive Queries

lmcs:12493 - Logical Methods in Computer Science, January 28, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:9)2025
Diversity of Answers to Conjunctive QueriesArticle

Authors: Timo Camillo Merkl ; Reinhard Pichler ; Sebastian Skritek

    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.


    Volume: Volume 21, Issue 1
    Published on: January 28, 2025
    Accepted on: December 10, 2024
    Submitted on: November 1, 2023
    Keywords: Computer Science - Databases,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 136 times.
    This article's PDF has been downloaded 46 times.