论文标题
一致性，无环和阳性半肌
Consistency, Acyclicity, and Positive Semirings
论文作者
论文摘要
在几种不同的环境中，一个情况下，研究对象在本地一致但全球不一致。 Vorob'ev（1962）以及Beeri，Fagin，Maier，Yannakakis（1983）的较早有关概率分布的工作以及有关局部一致性始终意味着全球一致性的特征。为了对这些结果进行共同的概括，我们认为K-Ryations（即，关系中的关系之间的关系都与关系中的每个元组相关联，与任意但固定的积极半级K的元素相关联。我们介绍了K-Realation的预测概念，两个K-RESINCES的一致性以及K-Relection的全球一致性；这些概念是关于概率分布和数据库关系的相应概念的自然扩展。然后，我们表明，一组属性集的集合具有以下属性，即当且仅当属性集形成一个acyclic HyperGraph时，每个属性上的每个k-resations在这些属性上的集合在全球范围内都是一致的。这概括了Vorob'ev和Beeri等人的上述结果，并证明了k-Ryations of to-nemirings k-Ryations构成了研究局部和全球一致性之间相互作用的自然框架。在证据的过程中，我们介绍了两个K-Ryations的联接概念，并认为这是两个数据库关系的联接的“正确”概括。此外，为了表明非囊泡超图产生了全球不一致的成对一致的K-Remations，我们将Tseitin（1968）（1968）的结构推广到他对命题逻辑中难以培养的重二仪的研究中。
In several different settings, one comes across situations in which the objects of study are locally consistent but globally inconsistent. Earlier work about probability distributions by Vorob'ev (1962) and about database relations by Beeri, Fagin, Maier, Yannakakis (1983) produced characterizations of when local consistency always implies global consistency. Towards a common generalization of these results, we consider K-relations, that is, relations over a set of attributes such that each tuple in the relation is associated with an element from an arbitrary, but fixed, positive semiring K. We introduce the notions of projection of a K-relation, consistency of two K-relations, and global consistency of a collection of K-relations; these notions are natural extensions of the corresponding notions about probability distributions and database relations. We then show that a collection of sets of attributes has the property that every pairwise consistent collection of K-relations over those attributes is globally consistent if and only if the sets of attributes form an acyclic hypergraph. This generalizes the aforementioned results by Vorob'ev and by Beeri et al., and demonstrates that K-relations over positive semirings constitute a natural framework for the study of the interplay between local and global consistency. In the course of the proof, we introduce a notion of join of two K-relations and argue that it is the "right" generalization of the join of two database relations. Furthermore, to show that non-acyclic hypergraphs yield pairwise consistent K-relations that are globally inconsistent, we generalize a construction by Tseitin (1968) in his study of hard-to-prove tautologies in propositional logic.
