查找描述一组实体中的引用对象的最小属性集

Question

我想知道是否有人可以帮我指点解决这个问题。算法链接很棒，但指向论文/信息的指针也很好。

问题如下。假设我有一组实体E={car1, car2, bicycle}和一组属性P ={red, blue, small}。我还有一个知识库，以便red(bicycle), blue(car1), blue(car2), small(car2)。假设我还有一个属于r的引用E。

问题在于找到最小的属性集P' \subseteq P，以便明确地从car2中选择P'={small}。因此，如果<=>是<=>，那么<=>。

有什么想法吗？我想像集合覆盖问题或功能依赖性（如在DB理论中）可能提供一些见解，但我想在进入该文献之前我会问。另一种可能性是构建图形并找到子图同构的算法......也许。

感谢。

Answer 1

首先找到r拥有的所有属性的集合。将其称为S.对于S中的每个属性p，找到e（p），所有具有属性p的实体。对于S中的每个p，e（p）包含r是清楚的。现在对于S中的每个p取e（p）的交点。如果交集包含多个实体，则没有解，我们结束算法。

因此，我们有一组唯一确定实体r的属性。现在我们需要找到唯一确定r的S的最小子集。我们可以从S中删除任何在S中存在属性q的属性p，使得e（p）是e（q）的超集。如果你做到这一点，你最终会得到一组减少的属性T，这样T中所有p的e（p）的交点仍然是{r}，但是T中不能再删除其他属性。这个集合T是最小的。

我没有想过要找到一个属性，你可以删除任何比仅仅尝试所有组合更有效的属性，但在我看来应该有一些方法。

Answer 2

您正在寻找集合E \ {r}的最小集合封面 r所属的那些属性的否定（补语）（属性可以被视为E的子集）。

由于这些集合可以是任何集合，因此这是NP难的。

更确切地说：

设置一个封面实例（U，S），其中s1是您需要覆盖的集合，s2 = {sn，E，...，r是覆盖集的一族，你可以构造你的问题的一个实例，以便它的解决方案在原始问题中提供一个集合掩盖：

P = p1 \ union {p2}，其中pn是指示对象，e不属于i。 属性集pi = {si，S*，...，<=>}由<=>构成，以便每个<=> in <=>，每个<=>，使得1 <！> lt; = <=> <！> lt; = n我们有<=>（<=>）iff <=>不在<=>中。此外，每个属性都适用于<=>。换句话说，当限制为<=>时，属性是原始集的补充，<=>具有所有属性。

现在很明显，选择<=>的每组属性都是原始问题的集合覆盖 - 如果<=>由属性集<=>选择，则所有其他元素（即所有这些元素）在<=>中，<=>中至少有一个属性失败，因此<=>的每个元素都属于至少一个原始集（来自属性的构造作为集的补充）。这意味着<=>是构建<=>中的属性的那些集合的联合。

相反也是如此 - <=>中的集合封面转换为<=> - 在<=>中选择集合。

上述减少显然是多项式的，所以问题是NP难。