Converging to the chase - A tool for finite controllability

详细信息    查看全文

• 作者：Tomasz Gogacz ; ^{gogo@cs.uni.wroc.pl" class="auth_mail" title="E-mail the corresponding author} ; Jerzy Marcinkowski ; ^{jma@cs.uni.wroc.pl" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Tuple generating dependencies ; Sticky Logic ; Finite controllability ; Bounded Derivation Depth Property
• 刊名：Journal of Computer and System Sciences
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：83
• 期：1
• 页码：180-206
• 全文大小：767 K

文摘

We solve a problem, stated in [5], showing that Sticky Datalog^∃, defined in the cited paper as an element of the Datalog^± project, has the Finite Controllability property, which means that whenever a query Ψ is not logically implied by a set of atoms class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si1.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=a7510d5a1b0a95eaa232911b39c2df78" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$\mathbb{D}$ and a Sticky Datalog^∃ theory class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si10.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=1d642b8cc9df888cb9e36617103090ac" title="Click to view the MathML source">Tclass="mathContainer hidden">class="mathCode">$\mathcal{T}$ a finite structure M   can be found such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si3.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=ef342a1a4656ee89c945766739b0fb73" title="Click to view the MathML source">M⊨D,Tclass="mathContainer hidden">class="mathCode">$M\models \mathbb{D},\mathcal{T}$, but class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si4.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=32bae2b52d30ab4f9df480d75fcf5e1d" title="Click to view the MathML source">M⊭Ψclass="mathContainer hidden">class="mathCode">$M⊭\mathrm{\Psi }$. In order to do that, we develop a technique, which we believe can have further applications, of approximating class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si5.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=fb2697e9259f22489dc4fdee25a63902" title="Click to view the MathML source">Chase(T,D)class="mathContainer hidden">class="mathCode">$Chase(\mathcal{T},\mathbb{D})$, for a database instance class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si1.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=a7510d5a1b0a95eaa232911b39c2df78" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$\mathbb{D}$ and a set of tuple generating dependencies and Datalog rules class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si10.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=1d642b8cc9df888cb9e36617103090ac" title="Click to view the MathML source">Tclass="mathContainer hidden">class="mathCode">$\mathcal{T}$, by an infinite sequence of finite structures, all of them being models of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si10.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=1d642b8cc9df888cb9e36617103090ac" title="Click to view the MathML source">Tclass="mathContainer hidden">class="mathCode">$\mathcal{T}$ and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0022000016300617&_mathId=si1.gif&_user=111111111&_pii=S0022000016300617&_rdoc=1&_issn=00220000&md5=a7510d5a1b0a95eaa232911b39c2df78" title="Click to view the MathML source">Dclass="mathContainer hidden">class="mathCode">$\mathbb{D}$.