一句话：研究合取查询及其扩展中，选取 k 个答案达到给定多样性水平 d 的判定与计算问题。
枚举问题要求无重复输出给定实例的全部解，但解集过大时完整输出代价过高，因此更希望输出规模小且足够多样的解子集。本文针对合取查询及其扩展的查询回答问题，研究其 Diverse 版本：给定多样性水平 d，判断能否通过选取 k 个答案达到该多样性；若可以，则进一步计算这 k 个答案。论文对这一问题进行形式化研究，关注其可判定性与求解，属于数据库理论与逻辑查询回答中的多样性枚举方向。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{MerklPS23,
title = {Diversity of Answers to Conjunctive Queries},
author = {Timo Camillo Merkl and Reinhard Pichler and Sebastian Skritek},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:9)2025}
}