论文标题
独特的钥匙号角功能
Unique key Horn functions
论文作者
论文摘要
给定一个关系数据库，一个密钥是一组属性，使得对此集的值分配唯一地确定了所有其他属性的值。数据库唯一定义了纯喇叭函数$ h $，代表功能依赖性。如果集合$ a $中属性值的知识确定属性$ v $的值，则$ a \ rightarrow v $的含义是$ h $。如果$ k $是数据库的关键，则$ k \ rightarrow v $对所有属性$ v $的含义是$ h $。 小规模的钥匙在各种问题中起着至关重要的作用。我们在纯喇叭函数的最小键中呈现结构和复杂性结果。我们表征了Sperner HyperGraphs，其中具有独特的纯喇叭功能，并具有给定的超图作为一组最小键。此外，我们表明，当每个Hypereedge的尺寸为两个时，识别此类超图已经是共同完成的。从积极的一面来看，我们确定了几类图表，可以在多项式时间内确定识别问题。 我们还提出了一种算法，该算法以多项式延迟生成纯喇叭函数的最小键。通过在键和目标集之间建立连接，我们的方法可用于在阈值被常数界定时以多项式延迟生成所有最小目标集。作为副产品，我们的证明表明，最小关键问题至少与有界阈值的最小目标设定选择问题一样困难。
Given a relational database, a key is a set of attributes such that a value assignment to this set uniquely determines the values of all other attributes. The database uniquely defines a pure Horn function $h$, representing the functional dependencies. If the knowledge of the attribute values in set $A$ determines the value for attribute $v$, then $A\rightarrow v$ is an implicate of $h$. If $K$ is a key of the database, then $K\rightarrow v$ is an implicate of $h$ for all attributes $v$. Keys of small sizes play a crucial role in various problems. We present structural and complexity results on the set of minimal keys of pure Horn functions. We characterize Sperner hypergraphs for which there is a unique pure Horn function with the given hypergraph as the set of minimal keys. Furthermore, we show that recognizing such hypergraphs is co-NP-complete already when every hyperedge has size two. On the positive side, we identify several classes of graphs for which the recognition problem can be decided in polynomial time. We also present an algorithm that generates the minimal keys of a pure Horn function with polynomial delay. By establishing a connection between keys and target sets, our approach can be used to generate all minimal target sets with polynomial delay when the thresholds are bounded by a constant. As a byproduct, our proof shows that the Minimum Key problem is at least as hard as the Minimum Target Set Selection problem with bounded thresholds.
