文摘
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"> 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"> 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">, 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">. 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">, 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"> 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">, 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"> 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">.