论文标题
连接的查询，量化的方程式系统和有限替代系统
Conjunctive Queries, Existentially Quantified Systems of Equations and Finite Substitutions
论文作者
论文摘要
本报告提出了一个基本的统一统一理论理论。正面查询是使用命题常数，方程式和原子构建的公式，使用连词$ \ wedge $和存在的量词$ \存在$。特别是，空查询对应于存在量化的方程式系统 - 称为$ \ cal e $ -formulas。我们提供了一种算法，该算法将任何连词查询转换为解决形式。我们证明了查询的一些晶格理论特性。特别是，在等价关系下的$ \ cal e $ formulas的商集形成了一个完整的晶格。然后，我们提出另一个晶格 - 有限取代的晶格。我们证明两个晶格都是同构。最后，我们介绍了替代方案的应用概念，并澄清了其与$ \ cal e $ formulas的关系。该理论可以视为逻辑编程替代介绍的基础。
This report presents an elementary theory of unification for positive conjunctive queries. A positive conjunctive query is a formula constructed from propositional constants, equations and atoms using the conjunction $\wedge$ and the existential quantifier $\exists$. In particular, empty queries correspond to existentially quantified systems of equations -- called $\cal E$-formulas. We provide an algorithm which transforms any conjunctive query into a solved form. We prove some lattice-theoretic properties of queries. In particular, the quotient set of $\cal E$-formulas under an equivalence relation forms a complete lattice. Then we present another lattice -- a lattice of finite substitutions. We prove that the both lattices are isomorphic. Finally, we introduce the notion of application of substitutions to formulas and clarify its relationship to $\cal E$-formulas. This theory can be regarded as a basis for alternative presentation of logic programming.
