Reasoning on Datalog± Ontologies with Abductive Logic Programming

• Autorzy: Gavanelli M. , Lamma E. , Riguzzi F. , Bellodi E. , Zese R. , Cota G.

Identyfikatory

DOI

10.3233/FI-2018-1658

• Konferencja: Convegno Italiano di Logica Computazionale : CILC 2015 (30th; 01-03.07.2015; University of Genoa, Italy)
• Języki publikacji: EN

Abstrakty

EN

Ontologies form the basis of the Semantic Web. Description Logics (DLs) are often the languages of choice for modeling ontologies. Integration of DLs with rules and rule-based reasoning is crucial in the so-called Semantic Web stack vision - a complete stack of recommendations and languages each based on and/or exploiting the underlying layers - which adds new features to the standards used in the Web. The growing importance of the integration between DLs and rules is proved by the definition of the profile OWL 2 RL¹ and the definition of languages such as RIF² and SWRL³. Datalog^± is an extension of Datalog which can be used for representing lightweight ontologies and expressing some languages of the DL-Lite family, with tractable query answering under certain language restrictions. In particular, it is able to express the DL-Lite version defined in OWL. In this work, we show that Abductive Logic Programming (ALP) can be used to represent Datalog^± ontologies, supporting query answering through an abductive proof procedure, and smoothly achieving the integration of ontologies and rule-based reasoning. Often, reasoning with DLs means finding explanations for the truth of queries, that are useful when debugging ontologies and to understand answers given by the reasoning process. We show that reasoning under existential rules can be expressed by ALP languages and we present a solving system, which is experimentally proved to be competitive with DL reasoning systems. In particular, we consider an ALP framework named SCIFF derived from the IFF abductive framework. Forward and backward reasoning is naturally supported in this ALP framework. The SCIFF language smoothly supports the integration of rules, expressed in a Logic Programming language, with Datalog^± ontologies, mapped into SCIFF (forward) integrity constraints. The main advantage is that this integration is achieved within a single language, grounded on abduction in computational logic, and able to model existential rules.

Słowa kluczowe

EN

logic programming; datalog; computer program language; ontology; constraint satisfaction; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 159, nr 1/2
• Strony: 65--93
• Opis fizyczny: Bibliogr. 56 poz., wykr.

Twórcy

autor

Gavanelli M.

• Dipartimento di Ingegneria, University of Ferrara, Italy

autor

Lamma E.

• Dipartimento di Ingegneria, University of Ferrara, Italy

autor

Riguzzi F.

• Dipartimento di Matematica e Informatica, University of Ferrara, Italy

autor

Bellodi E.

• Dipartimento di Ingegneria, University of Ferrara, Italy

autor

Zese R.

• Dipartimento di Ingegneria, University of Ferrara, Italy

autor

Cota G.

• Dipartimento di Ingegneria, University of Ferrara, Italy

Bibliografia

• [1] Hitzler P, Krötzsch M, Rudolph S. Foundations of Semantic Web Technologies. CRCPress, 2009. ISBN:9781420090505 - CAT# C9050.
• [2] Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. J. Autom. Reasoning, 2007;39(3):385-429. URL https://doi.org/10.1007/s10817-007-9078-x.
• [3] Sirin E, Parsia B, Cuenca-Grau B, Kalyanpur A, Katz Y. Pellet: A practical OWL-DL reasoner. Journal of Web Semantics, 2007;5(2):51-53. doi:10.1016/j.websem.2007.03.004.
• [4] Haarslev V, Hidde K, Möller R, Wessel M. The RacerPro knowledge representation and reasoning system. Semantic Web, 2012;3(3):267-277. doi:10.3233/SW-2011-0032.
• [5] Glimm B, Horrocks I, Motik B, Stoilos G, Wang Z. Hermi T: An OWL 2 Reasoner. J. Autom. Reasoning, 2014;53(3):245-269. doi:10.1007/s10817-014-9305-1. URL http://dx.doi.org/10.1007/s10817-014-9305-1.
• [6] Schmidt-Schauß M, Smolka G. Attributive Concept Descriptions with Complements. Artificial Intelligence, 1991;48(1):1-26. URL https://doi.org/10.1016/0004-3702(91)90078-X.
• [7] Zese R, Bellodi E, Lamma E, Riguzzi F. A Description Logics Tableau Reasoner in Prolog. In: Cantone D, Nicolosi Asmundo M (eds.), CILC, volume 1068 of CEUR Workshop Proceedings. CEUR-WS.org, 2013 pp. 33-47.
• [8] Calì A, Gottlob G, Kifer M. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. Journal of Artificial Intelligence Research, 2013;48:115-174. doi:10.1613/jair.3873.
• [9] Calì A, Gottlob G, Lukasiewicz T. A general datalog-based framework for tractable query answering over ontologies. In: Symposium on Principles of Database Systems. ACM, 2009 pp. 77-86. doi:10.1145/1559795.1559809.
• [10] Calì A, Gottlob G, Lukasiewicz T. A general Datalog-based framework for tractable query answering over ontologies. Journal of Web Semantics, 2012;14:57-83. doi:10.1016/j.websem.2012.03.001. URL http://dx.doi.org/10.1016/j.websem.2012.03.001.
• [11] Calì A, Gottlob G, Lukasiewicz T, Marnette B, Pieris A. Datalog± : A Family of Logical Knowledge Representation and Query Languages for New Applications. In: IEEE Symposium on Logic in Computer Science. IEEE Computer Society, 2010 pp. 228-242. doi:10.1109/LICS.2010.27.
• [12] Zhou Y, Grau BC, Nenov Y, Kaminski M, Horrocks I. PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner. Journal of Artificial Intelligence Research, 2015;54:309-367. URL http://dl.acm.org/citation.cfm?id=2910557.2910566.
• [13] Kakas AC, Kowalski RA, Toni F. Abductive Logic Programming. Journal of Logic and Computation, 1993;2(6):719-770.
• [14] Fung TH, Kowalski RA. The IFF proof procedure for abductive logic programming. Journal of Logic Programming, 1997;33(2):151-165. URL https://doi.org/10.1016/S0743-1066(97)00026-5.
• [15] Alberti M, Chesani F, Gavanelli M, Lamma E, Mello P, Torroni P. Verifiable Agent Interaction in Abductive Logic Programming: the SCIFF framework. ACM Transactions on Computational Logic, 2008;9(4). doi:10.1145/1380572.1380578.
• [16] Jaffar J, Maher M. Constraint Logic Programming: a Survey. Journal of Logic Programming, 1994;19-20:503-582. doi:10.1016/0743-1066(94)90033-7.
• [17] Alberti M, Gavanelli M, Lamma E, Mello P, Sartor G, Torroni P. Mapping Deontic Operators to Abductive Expectations. Computational and Mathematical Organization Theory, 2006;12(2-3):205-225. doi:10.1007/s10588-006-9544-8.
• [18] Alberti M, Gavanelli M, Lamma E, Mello P, Torroni P. Specification and Verification of Agent Interactions using Social Integrity Constraints. Electronic Notes in Theoretical Computer Science, 2003;85(2):94-116. URL https://doi.org/10.1016/S1571-0661(05)82605-2.
• [19] Alberti M, Chesani F, Gavanelli M, Lamma E, Mello P, Montali M. An Abductive Framework for A-Priori Verification of Web Services. In: Maher M (ed.), Proceedings of the Eighth Symposium on Principles and Practice of Declarative Programming. ACM Press, New York, USA, 2006 pp. 39-50. ISBN: 1-59593-388-3.
• [20] Chesani F, Mello P, Montali M, Storari S, Torroni P. On the integration of declarative choreographies and Commitment-based agent societies into the SCIFF logic programming framework. Multiagent and Grid Systems, 2010;6(2):165-190. doi:10.3233/MGS-2010-0147. URL http://dx.doi.org/10.3233/MGS-2010-0147.
• [21] Calì A, Gottlob G, Kifer M. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. In: International Conference on Principles of Knowledge Representation and Reasoning. AAAI Press, 2008 pp. 70-80.
• [22] Gottlob G, Lukasiewicz T, Simari GI. Conjunctive Query Answering in Probabilistic Datalog+/- Ontologies. In: International Conference on Web Reasoning and Rule Systems, volume 6902 of LNCS. Springer, 2011 pp. 77-92. URL https://doi.org/10.1007/978-3-642-23580-1_7.
• [23] Lloyd JW. Foundations of Logic Programming. Springer-Verlag, 2nd extended edition, 1987. ISBN 3-540-18199-7.
• [24] Kunen K. Negation in logic programming. In: Journal of Logic Programming, volume 4. 1987 pp. 289-308.
• [25] Alberti M, Gavanelli M, Lamma E. The CHR-based Implementation of the SCIFF Abductive System. Fundamenta Informaticae, 2013;124(4):365-381. doi:10.3233/FI-2013-839.
• [26] Alberti M, Chesani F, Gavanelli M, Lamma E, Mello P, Torroni P. Security protocols verification in Abductive Logic Programming: a case study. In: Dikenelli O, Gleizes MP, Ricci A (eds.), ESAW 2005 Post-proceedings, number 3963 in LNAI. Springer-Verlag, Kusadasi, Aydin, Turkey, 2006 pp. 106-124.
• [27] Reiter R. A Theory of Diagnosis from First Principles. Artif. Intell., 1987;32(1):57-95.
• [28] Beckert B, Posegga J. leanTAP: Lean Tableau-based Deduction. J. Autom. Reasoning, 1995;15(3):339-358. URL https://doi.org/10.1007/BF00881804.
• [29] Posegga J, Schmitt P. Implementing Semantic Tableaux. In: D’Agostino M, Gabbay D, Hähnle R, Posegga J (eds.), Handbook of Tableau Methods, pp. 581-629. Springer Netherlands 1999. ISBN: 978-90-481-5184-4. doi:10.1007/978-94-017-1754-0n_10. URL http://dx.doi.org/10.1007/978-94-017-1754-0_10.
• [30] Hustadt U, Motik B, Sattler U. Deciding expressive description logics in the framework of resolution. Inf. Comput., 2008;206(5):579-601. URL https://doi.org/10.1016/j.ic.2007.11.006.
• [31] Lukácsy G, Szeredi P. Efficient description logic reasoning in Prolog: The DLog system. TPLP, 2009;9(3):343-414. doi:10.1017/S1471068409003792.
• [32] Straccia U, Lopes N, Lukacsy G, Polleres A. A General Framework for Representing and Reasoning with Annotated Semantic Web Data. In: Fox M, Poole D (eds.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010 pp. 1437-1442. URL http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1590.
• [33] Meissner A. An automated deduction system for description logic with ALCN language. Studia z Automatyki i Informatyki, 2004;28-29:91-110.
• [34] Meissner A. A simple distributed reasoning system for the connection calculus. Vietnam Journal of Computer Science, 2014;1(4):231-239. doi:10.1007/s40595-014-0023-8. URL http://dx.doi.org/10.1007/s40595-014-0023-8.
• [35] Herchenröder T. Lightweight Semantic Web Oriented Reasoning in Prolog: Tableaux Inference for Description Logics, 2006.
• [36] Faizi I. A Description Logic Prover in Prolog. Bachelor’s thesis, Informatics Mathematical Modelling, Technical University of Denmark, 2011.
• [37] Ricca F, Gallucci L, Schindlauer R, Dell’Armi T, Grasso G, Leone N. OntoDLV: An ASP-based System for Enterprise Ontologies. J. Log. Comput., 2009;19(4):643-670. URL https://doi.org/10.1093/logcom/exn042.
• [38] Leone N, Manna M, Terracina G, Veltri P. Efficiently Computable DatalogƎ Programs. In: Brewka G, Eiter T, McIlraith SA (eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012. AAAI Press, 2012. ISBN:978-1-57735-560-1.
• [39] Nenov Y, Piro R, Motik B, Horrocks I, Wu Z, Banerjee J. RDFox: A Highly-Scalable RDF Store. In: Arenas M, Corcho Ó , Simperl E, Strohmaier M, d’Aquin M, Srinivas K, Groth PT, Dumontier M, Heflin J, Thirunarayan K, Staab S (eds.), The Semantic Web - ISWC 2015 - 14th International Semantic Web Conference, Bethlehem, PA, USA, October 11-15, 2015, Proceedings, Part II, volume 9367 of Lecture Notes in Computer Science. Springer, 2015 pp. 3-20.
• [40] Zese R, Bellodi E, Lamma E, Riguzzi F, Aguiari F. Semantics and Inference for Probabilistic Description Logics. In: Bobillo F, Carvalho RN, da Costa PCG, d’Amato C, Fanizzi N, Laskey KB, Laskey KJ, Lukasiewicz T, Nickles M, Pool M (eds.), Uncertainty Reasoning for the Semantic Web III - ISWC International Workshops, URSW 2011-2013, Revised Selected Papers, volume 8816 of Lecture Notes in Computer Science. Springer 2014 pp. 79-99. ISBN 978-3-319-13412-3. doi:10.1007/978-3-319-13413-0\_5.
• [41] Motik B, Rosati R. Reconciling Description Logics and Rules. Journal of the ACM, 2010;57(5):30:1-30:62. doi:10.1145/1754399.1754403.
• [42] Alberti M, Lamma E, Riguzzi F, Zese R. Probabilistic Hybrid Knowledge Bases under the Distribution Semantics. In: Adorni G, Cagnoni S, Gori M, Maratea M (eds.), Proceedings of the 15th Conference of the Italian Association for Artificial Intelligence (AI*IA2016), Genova, Italy, 28 November - 1 December 2016, volume 10037 of Lecture Notes in Computer Science. Springer International Publishing, Heidelberg, Germany, 2016 pp. 364-376. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-49130-1_27.
• [43] Alberti M, Lamma E, Riguzzi F, Zese R. A Distribution Semantics for non-DL-Safe Probabilistic Hybrid Knowledge Bases. In: Theil Have C, Zese R (eds.), 4th International Workshop on Probabilistic logic programming, PLP 2017, volume 1916 of CEUR Workshop Proceedings. Sun SITE Central Europe, Aachen, Germany, 2017 pp. 40-50.
• [44] Eiter T, Ianni G, Lukasiewicz T, Schindlauer R, Tompits H. Combining answer set programming with description logics for the Semantic Web. Artif. Intell., 2008;172(12-13):1495-1539. URL https://doi.org/10.1016/j.artint.2008.04.002.
• [45] Alberti M, Cattafi M, Chesani F, Gavanelli M, Lamma E, Mello P, Montali M, Torroni P. A Computational Logic Application Framework for Service Discovery and Contracting. International Journal of Web Services Research, 2011;8(3):1-25. doi:10.4018/JWSR.2011070101.
• [46] Zese R, Bellodi E, Lamma E, Riguzzi F. Logic Programming Techniques for Reasoning with Probabilistic Ontologies. In: Papini O, Benferhat S, Garcia L, Mugnier M, Fermé EL, Meyer T, Wassermann R, Hahmann T, Baclawski K, Krisnadhi A, Klinov P, Borgo S, Kutz O, Porello D (eds.), Proceedings of the Joint Ontology Workshops 2015 Episode 1: The Argentine Winter of Ontology co-located with the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina, July 25-27, 2015., volume 1517 of CEUR Workshop Proceedings. CEUR-WS.org, 2015 URL http://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_3.pdf.
• [47] Wielemaker J, Schrijvers T, Triska M, Lager T. SWI-Prolog. Theory and Practice of Logic Programming, 2011. http://arxiv.org/abs/1011.5332.
• [48] Carlsson M, Mildner P. SICStus Prolog - The first 25 years. Theory and Practice of Logic Programming, 2012;12(1-2):35-66. doi:10.1017/S1471068411000482. URL http://dx.doi.org/10.1017/S1471068411000482.
• [49] Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF (eds.). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2003. ISBN: 0-521-78176-0.
• [50] Auer S, Bizer C, Kobilarov G, Lehmann J, Cyganiak R, Ives ZG. DBpedia: A Nucleus for a Web of Open Data. In: Aberer K, Choi K, Noy NF, Allemang D, Lee K, Nixon LJB, Golbeck J, Mika P, Maynard D, Mizoguchi R, Schreiber G, Cudré-Mauroux P (eds.), The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC 2007, Busan, Korea, November 11-15, 2007., volume 4825 of Lecture Notes in Computer Science. Springer, 2007 pp. 722-735. ISBN: 978-3-540-76297-3. doi:10.1007/978-3-540-76298-0\_52. URL http://dx.doi.org/10.1007/978-3-540-76298-0\_52.
• [51] Demir E, et al. The BioPAX community standard for pathway data sharing. Nature Biotech, 2010; 28(9):935-942. doi:10.1038/nbt.1666. URL http://dx.doi.org/10.1038/nbt.1666.
• [52] Nagypál G, Deswarte R, Oosthoek J. Applying the Semantic Web: The VICODI Experience in Creating Visual Contextualization for History. Literary and Linguistic Computing, 2005;20(3):327-349. doi:10.1093/llc/fqi037. http://llc.oxfordjournals.org/content/20/3/327.full.pdf+html, URL http://llc.oxfordjournals.org/content/20/3/327.abstract.
• [53] Frühwirth T. Theory and Practice of Constraint Handling Rules. Journal of Logic Programming, 1998;37(1-3):95-138. URL https://doi.org/10.1016/S0743-1066(98)10005-5.
• [54] Gottlob G, Lukasiewicz T, Pieris A. Datalog+/-: Questions and answers. In: Fourteenth International Conference on the Principles of Knowledge Representation and Reasoning. 2014.
• [55] Alberti M, Bellodi E, Cota G, Lamma E, Riguzzi F, Zese R. Probabilistic Constraint Logic Theories. In: Hommersom A, Abdallah SA (eds.), Proceedings of the 3rd International Workshop on Probabilistic Logic Programming co-located with 26th International Conference on Inductive Logic Programming (ILP 2016), London, UK, September 3, 2016., volume 1661 of CEUR Workshop Proceedings. CEUR-WS.org, 2016 pp. 15-28.
• [56] Nocedal J. Updating quasi-Newton matrices with limited storage. Mathematics of Computation, 1980;35(151):773-782. URL http://www.jstor.org/stable/2006193.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).