×

Finite model reasoning over existential rules. (English) Zbl 1422.68060

Summary: Ontology-based query answering asks whether a Boolean conjunctive query is satisfied by all models of a logical theory consisting of a relational database paired with an ontology. The introduction of existential rules (i.e., Datalog rules extended with existential quantifiers in rule heads) as a means to specify the ontology gave birth to Datalog\(+/-\), a framework that has received increasing attention in the last decade, with focus also on decidability and finite controllability to support effective reasoning. Five basic decidable fragments have been singled out: linear, weakly acyclic, guarded, sticky, and shy. Moreover, for all these fragments, except shy, the important property of finite controllability has been proved, ensuring that a query is satisfied by all models of the theory iff it is satisfied by all its finite models. In this paper, we complete the picture by demonstrating that finite controllability of ontology-based query answering holds also for shy ontologies, and it therefore applies to all basic decidable Datalog\(+/-\) classes. To make the demonstration, we devise a general technique to facilitate the process of (dis)proving finite controllability of an arbitrary ontological fragment.

MSC:

68P15 Database theory
03B70 Logic in computer science
68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] BaaderF., CalvaneseD., McGuinnessD. L., NardiD. and Patel-SchneiderP. F., Eds. 2003. The Description Logic Handbook: Theory, Implementation, and Applications. CUP. · Zbl 1058.68107
[2] BagetJ., LeclèreM. and MugnierM.2010. Walking the decidability line for rules with existential variables. In Proc. of KR’10.
[3] BagetJ., LeclèreM., MugnierM. and SalvatE.2009. Extending decidable cases for rules with existential variables. In Proc. of IJCAI’09, 677-682.
[4] BagetJ., LeclèreM., MugnierM. and SalvatE.2011. On rules with existential variables: Walking the decidability line. Artificial Intelligence Journal175, 9-10, 1620-1654.10.1016/j.artint.2011.03.002 · Zbl 1225.68247 · doi:10.1016/j.artint.2011.03.002
[5] BárányV., GottlobG. and OttoM.2014. Querying the guarded fragment. Logical Methods in Computer Science10, 2, 1-35. · Zbl 1314.68146
[6] BienvenuM., ten CateB., LutzC. and WolterF.2014. Ontology-based data access: A study through disjunctive datalog, csp, and MMSNP. ACM TODS39, 4, 33:1-33:44.
[7] BourhisP., MannaM., MorakM. and PierisA.2016. Guarded-based disjunctive tuple-generating dependencies. ACM TODS41, 4, 27:1-27:45.
[8] CalìA., GottlobG. and KiferM.2013. Taming the infinite chase: Query answering under expressive relational constraints. Journal of Artificial Intelligence Research (JAIR)48, 115-174. · Zbl 1361.68221
[9] CalìA., GottlobG. and LukasiewiczT.2009a. Datalog^±: A unified approach to ontologies and integrity constraints. In Proc. of ICDT’09, 14-30.
[10] CalìA., GottlobG. and LukasiewiczT.2009b. Tractable query answering over ontologies with datalog+/-. In Proc. of DL’09.
[11] CalìA., GottlobG. and LukasiewiczT.2012. A general datalog-based framework for tractable query answering over ontologies. Journal of Web Semantics14, 57-83.10.1016/j.websem.2012.03.001 · doi:10.1016/j.websem.2012.03.001
[12] CalìA., GottlobG. and PierisA.2010. Advanced processing for ontological queries. PVLDB3, 1, 554-565.
[13] CalìA., GottlobG. and PierisA.2012. Towards more expressive ontology languages: The query answering problem. Artificial Intelligence Journal193, 87-128.10.1016/j.artint.2012.08.002 · Zbl 1270.68293 · doi:10.1016/j.artint.2012.08.002
[14] CiviliC. and RosatiR.2012. A broad class of first-order rewritable tuple-generating dependencies. In Proc. of Datalog 2.0, 68-80.
[15] DeutschA., NashA. and RemmelJ. B.2008. The chase revisited. In Proc. of PODS’08, 149-158.
[16] EbbinghausH.-D. and FlumJ.1995. Satisfiability in the Finite. Springer, Berlin Heidelberg, 95-103.
[17] FagesF.1991. A new fixpoint semantics for general logic programs compared with the well-founded and the stable model semantics. New Generation Computing9, 3/4, 425-444.10.1007/BF03037172 · Zbl 0737.68014 · doi:10.1007/BF03037172
[18] FaginR., KolaitisP. G., MillerR. J. and PopaL.2005. Data exchange: Semantics and query answering. Theoretical Computer Science336, 1, 89-124.10.1016/j.tcs.2004.10.033 · Zbl 1080.68019 · doi:10.1016/j.tcs.2004.10.033
[19] GogaczT. and MarcinkowskiJ.2013. Converging to the chase - A tool for finite controllability. In Proc. of LICS’13, 540-549.
[20] GogaczT. and MarcinkowskiJ.2017. Converging to the chase - A tool for finite controllability. Journal of Computer and System Sciences83, 1, 180-206.10.1016/j.jcss.2016.08.001 · Zbl 1350.68056 · doi:10.1016/j.jcss.2016.08.001
[21] GottlobG., KikotS., KontchakovR., PodolskiiV. V., SchwentickT. and ZakharyaschevM.2014. The price of query rewriting in ontology-based data access. Artificial Intelligence Journal213, 42-59.10.1016/j.artint.2014.04.004 · Zbl 1390.68246 · doi:10.1016/j.artint.2014.04.004
[22] GottlobG., MannaM. and PierisA.2013. Combining decidability paradigms for existential rules. Theory and Practice of Logic Programming13, 4-5, 877-892.10.1017/S1471068413000550S1471068413000550 · Zbl 1286.68044 · doi:10.1017/S1471068413000550
[23] GottlobG., OrsiG. and PierisA.2014. Query rewriting and optimization for ontological databases. ACM TODS39, 3, 25:1-25:46.
[24] GottlobG., PierisA. and TenderaL.2013. Querying the guarded fragment with transitivity. In Proc. of ICALP’13, 287-298.
[25] JohnsonD. S. and KlugA. C.1984. Testing containment of conjunctive queries under functional and inclusion dependencies. Journal of Computer and System Sciences28, 1, 167-189.10.1016/0022-0000(84)90081-3 · Zbl 0563.68081 · doi:10.1016/0022-0000(84)90081-3
[26] KrötzschM. and RudolphS.2011. Extending decidable existential rules by joining acyclicity and guardedness. In Proc. of IJCAI’11, 963-968.
[27] LeoneN., MannaM., TerracinaG. and VeltriP.2012. Efficiently computable datalog^∃ programs. In Proc. of KR’12.
[28] RosatiR.2006. On the decidability and finite controllability of query processing in databases with incomplete information. In Proc. of PODS’06.
[29] RosatiR.2007. The limits of querying ontologies. In Proc. of ICDT’07, 164-178.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.