论文标题
结合疑问的极端拟合问题
Extremal Fitting Problems for Conjunctive Queries
论文作者
论文摘要
连接查询（CQS）的拟合问题是构造适合一组标记的数据示例的CQ的问题。当存在拟合CQ时，它通常不是唯一的。这使我们提出了拟合CQ概念的自然改进，例如大多数拟合CQ，最特定的拟合CQ和独特的拟合CQ。我们根据（适当的）同态二元性，边界和直接产物对这些概念进行结构特征，从而使精制拟合CQ在存在时构建。我们还指出了相关存在和验证问题的复杂性，并确定拟合CQ的大小。我们研究了UCQ和更受限制的树CQ类别的问题。
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not unique. This leads us to proposing natural refinements of the notion of a fitting CQ, such as most-general fitting CQ, most-specific fitting CQ, and unique fitting CQ. We give structural characterizations of these notions in terms of (suitable refinements of) homomorphism dualities, frontiers, and direct products, which enable the construction of the refined fitting CQs when they exist. We also pinpoint the complexity of the associated existence and verification problems, and determine the size of fitting CQs. We study the same problems for UCQs and for the more restricted class of tree CQs.
