Adding Metalogic Features to Knowledge Representation Languages

• Autorzy: Costantini Stefania , Formisano Andrea

Identyfikatory

DOI

10.3233/FI-2021-2051

• Języki publikacji: EN

Abstrakty

EN

In this paper we present a methodology for introducing customizable metalogic features in logic-based knowledge representation and reasoning languages. The proposed approach is based on concepts of introspection and reflection previously introduced and discussed by various authors in relevant literature. This allows a knowledge engineer to specify enhanced reasoning engines by defining properties and meta-properties of relations as expressible for instance in OWL. We employ meta-level axiom schemata based upon a naming (reification) device. We propose general principles for extending the semantics of “host” formalisms accordingly. Consequently, suitable pre-defined libraries of properties can be made available, while user-defined new schemata are also allowed. We make the specific cases of Answer Set Programming (ASP) and Datalog±, where such features may be part of software engineering toolkits for these programming paradigms. On the one hand, concerning ASP, we extend the programming principles and practice to accommodate the proposed methodology, so as to perform meta-reasoning within the plain ASP semantics. The computational complexity of the resulting framework does not change. On the other hand, we show how metalogic features can significantly enrich Datalog± with minor changes to its operational semantics (provided in terms of “chase”) and, also in this case, no additional complexity burden.

Słowa kluczowe

EN

meta-reasoning; answer set programming; Datalog+; web-ontologies

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 181, nr 1
• Strony: 71--98
• Opis fizyczny: Bibliogr. 69 poz.

Twórcy

autor

Costantini Stefania

• DISIM — Università di L’Aquila, via Vetoio Loc. Coppito, I-67010 L’Aquila, Italy

autor

Formisano Andrea

• DMIF — Università di Udine, via delle Scienze 206, I-33100 Udine, Italy

Bibliografia

• [1] Costantini S, Formisano A. Augmenting Knowledge Representation and Reasoning Languages with Customizable Metalogic Features. In: Proc. of CILC’19, volume 2396 of CEUR Workshop Proc. CEUR-WS.org, 2019 pp. 14-29. http://ceur-ws.org/Vol-2396/.
• [2] Costantini S, Formisano A. Augmenting Datalog+ with Customizable Metalogic Features for Powerful Ontological Reasoning. In: Alviano M, Greco G, Scarcello F (eds.), Proc. of AIIA’19, volume 11946 of LNCS. Springer, 2019 pp. 30-45. doi:10.1007/978-3-030-35166-3_3.
• [3] Horrocks I, Patel-Schneider PF, van Harmelen F. From SHIQ and RDF to OWL: the making of a Web Ontology Language. J. Web Sem., 2003. 1(1):7-26. doi:10.1016/j.websem.2003.07.001.
• [4] Antoniou G, van Harmelen F. Web Ontology Language: OWL. In: Handbook on Ontologies, International Handbooks on Information Systems, pp. 91-110. Springer, 2009. doi:10.1007/978-3-540-92673-3_4.
• [5] Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge Univ. Press, 2003. ISBN:0-521-78176-0.
• [6] Konolige K. Reasoning by Introspection. In: Meta-Level Architectures and Reflection, pp. 61-74. North-Holland, 1988. ISBN:0444703438.
• [7] van Harmelen F, Wielinga B, Bredeweg B, Schreiber G, Karbach W, Reinders M, Voss A, Akkermans H, Bartsch-Spörl B, Vinkhuyzen E. Knowledge-Level Reflection. In: Enhancing the Knowledge Engineering Process - Contributions from ESPRIT, pp. 175-204. Elsevier Science, 1992. ISBN:044489893X.
• [8] Costantini S, Lanzarone GA. A metalogic programming approach: language, semantics and applications. J. Exp. Theor. Artif. Intell., 1994. 6(3):239-287. doi:10.1080/09528139408953789.
• [9] Barklund J, Costantini S, Dell’Acqua P, Lanzarone GA. Reflection Principles in Computational Logic. Journal of Logic and Computation, 2000. 10(6):743-786. doi:10.1093/logcom/10.6.743.
• [10] Costantini S. Meta-reasoning: A Survey. In: Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II, volume 2408 of LNCS. Springer, 2002. doi:10.1007/3-540-45632-5_11.
• [11] Lloyd JW. Foundations of Logic Programming, Second Edition. Springer, Berlin, 1987. doi:10.1007/978-3-642-83189-8.
• [12] Bowen KA, Kowalski RA. Amalgamating language and metalanguage in logic programming. In: Logic Programming, pp. 153-172. Academic Press, 1982. ISBN:0121755207.
• [13] Carlucci Aiello L, Levi G. The uses of metaknowledge in AI systems. In: Meta-Level Architectures and Reflection, pp. 243-254. North-Holland, 1988. ISBN:0444703438.
• [14] Bonatti P. Model theoretic semantics for demo. In: Meta-Programming in Logic, volume 649 of LNCS. Springer, Berlin, 1992 pp. 220-234. doi:10.1007/3-540-56282-6_15.
• [15] Hill PM, Lloyd JW. The Gödel Programming Language. MIT Press, 1994. ISBN:978-0-262-08229-7.
• [16] Grosof BN, Kifer M, Fodor P. Rulelog: Highly Expressive Semantic Rules with Scalable Deep Reasoning. In: Proc. of the Doctoral Consortium, Challenge, Industry Track, Tutorials and Posters @ RuleML+RR 2017 hosted by RuleML+RR 2017, volume 1875 of CEUR Workshop Proc. CEUR-WS.org, 2017. http://ceur-ws.org/Vol-1875.
• [17] Chen W, Kifer M, Warren DS. HILOG: A Foundation for Higher-Order Logic Programming. J. Log. Program., 1993. 15(3):187-230. doi:10.1016/0743-1066(93)90039-J.
• [18] Bordini RH, Braubach L, Dastani M, El Fallah-Seghrouchni A, Gomez-Sanz J, Leite J, O’Hare G, Pokahr A, Ricci A. A survey of programming languages and platforms for multi-agent systems. Informatica (Slovenia), 2006. 30(1). http://www.informatica.si/index.php/informatica/article/view/71.
• [19] Brewka G, Eiter T, Truszczynski M. Answer set programming at a glance. Commun. ACM, 2011. 54(12):92-103. doi:10.1145/2043174.2043195.
• [20] Calì A, Gottlob G, Lukasiewicz T, Pieris A. Datalog+/-: A Family of Languages for Ontology Querying. volume 6702 of LNCS. Springer, 2010 pp. 351-368. doi:10.1007/978-3-642-24206-9_20.
• [21] Calì A, Gottlob G, Lukasiewicz T. A general Datalog-based framework for tractable query answering over ontologies. J. Web Semant., 2012. 14:57-83. doi:10.1016/j.websem.2012.03.001.
• [22] Calì A, Gottlob G, Kifer M. Taming the Infinite Chase: Query Answering under Expressive Relational Constraints. J. Artif. Intell. Res., 2013. 48:115-174. doi:10.1613/jair.3873.
• [23] Ceri S, Gottlob G, Tanca L. Logic Programming and Databases. Surveys in computer science. Springer, 1990. ISBN:3-540-51728-6.
• [24] Dovier A, Formisano A, Pontelli E. Parallel Answer Set Programming. In: Hamadi Y, Sais L (eds.), Handbook of Parallel Constraint Reasoning, chapter 7, pp. 237-282. Springer, 2018. doi:10.1007/978-3-319-63516-3_7.
• [25] ASP. Answer Set Programming Solvers (incomplete list), 2018. DLV: www.dlvsystem.com.WASP: www.mat.unical.it/DLV2/wasp.clingo:potassco.org.lparse+smodels: www.tcs.hut.fi/Software/smodels.
• [26] Gebser M, Kaminski R, Kaufmann B, Lindauer M, Ostrowski M, Romero J, Schaub T, Thiele S, Wanko P. Potassco User Guide, v.2.2.0, 2019. potassco.org.
• [27] Costantini S, Formisano A. Weight Constraints with Preferences in ASP. In: Delgrande JP, Faber W (eds.), Proc. of LPNMR’11, volume 6645 of LNCS. Springer, 2011 pp. 229-235. doi:10.1007/978-3-642-20895-9_24.
• [28] Costantini S, Formisano A. Augmenting Weight Constraints with Complex Preferences. In: AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning. AAAI, 2011. Technical Report SS-11-06. https://www.aaai.org/ocs/index.php/SSS/SSS11/paper/view/2433.
• [29] Costantini S, Formisano A. Nested Weight Constraints in ASP. Fundamenta Informaticae, 2013. 124(4):449-464. doi:10.3233/FI-2013-843.
• [30] Costantini S, Formisano A. Negation as a Resource: a Novel View on Answer Set Semantics. Fundamenta Informaticae, 2015. 140(3-4):279-305. doi:10.3233/FI-2015-1255.
• [31] Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. DL-Lite: Tractable Description Logics for Ontologies. In: Veloso MM, Kambhampati S (eds.), Proc. of AAAI’06. AAAI Press, 2005 pp. 602-607. ISBN:1-57735-236-X.
• [32] Artale A, Calvanese D, Kontchakov R, Zakharyaschev M. The DL-Lite Family and Relations. J. Artif. Intell. Res., 2009. 36:1-69. doi:10.1613/jair.2820.
• [33] Bellomarini L, Gottlob G, Pieris A, Sallinger E. Swift Logic for Big Data and Knowledge Graphs. In: Sierra C (ed.), Proc. of IJCAI’17. ijcai.org, 2017 pp. 2-10. doi:10.1007/978-3-319-73117-9_1.
• [34] Bellomarini L, Sallinger E, Gottlob G. The Vadalog System: Datalog-based Reasoning for Knowledge Graphs. PVLDB, 2018. 11(9):975-987. doi:10.14778/3213880.3213888.
• [35] Gottlob G, Pieris A, Sallinger E. Vadalog: Recent Advances and Applications. In: Calimeri F, Leone N, Manna M (eds.), Proc. of JELIA’19, volume 11468 of LNCS. Springer, 2019 pp. 21-37. doi:10.1007/978-3-030-19570-0_2.
• [36] Konstantinou N, Abel E, Bellomarini L, Bogatu A, Civili C, Irfanie E, Koehler M, Mazilu L, Sallinger E, Fernandes AAA, Gottlob G, Keane JA, Paton NW. VADA: an architecture for end user informed data preparation. J. Big Data, 2019. 6:74. doi:10.1186/s40537-019-0237-9.
• [37] Bellomarini L, Fakhoury D, Gottlob G, Sallinger E. Knowledge Graphs and Enterprise AI: The Promise of an Enabling Technology. In: Proc. of ICDE’19. IEEE, 2019 pp. 26-37. doi:10.1109/ICDE.2019.00011.
• [38] Bellomarini L, Gottlob G, Sallinger E. Datalog-based Reasoning for Knowledge Graphs. In: Hogan A, Milo T (eds.), Proceedings of the 13th Alberto Mendelzon International Workshop on Foundations of Data Management, volume 2369 of CEUR Workshop Proc.. CEUR-WS.org, 2019. http://ceur-ws.org/Vol-2369.
• [39] Gottlob G, Manna M, Pieris A. Polynomial Rewritings for Linear Existential Rules. In: Yang Q, Wooldridge MJ (eds.), Proc. of IJCAI’15. AAAI Press, 2015 pp. 2992-2998. ISBN:978-157735738-4.
• [40] Costantini S, Lanzarone GA. A Metalogic Programming Language. In: Levi G (ed.), ICLP, Proceedings of the 6th International Conference on Logic Programming.MIT Press, 1989. ISBN:ISBN 0-262-62065-0.
• [41] Costantini S. Semantics of a Metalogic Programming Language. Int. J. Found. Comput. Sci., 1990. 1(3):233-248. doi:10.1142/S0129054190000175.
• [42] Costantini S, Lanzarone GA. Metalevel Negation in Non-Monotonic Reasoning. In: LPNMR, Proceedings of the Workshop on Logic Programming and Non-Monotonic Logic at ICLP 1990. 1990 pp. 19-26.
• [43] Costantini S, Dell’Acqua P, Lanzarone GA. Extending Horn Clause Theories by Reflection Principles. In: MacNish C, Pearce D, Pereira LM (eds.), Proc. of JELIA’94, volume 838 of LNCS. Springer, 1994. doi:10.1007/bfb0021987.
• [44] Barklund J, Dell’Acqua P, Costantini S, Lanzarone GA. SLD-Resolution with Reflection. In: Bruynooghe M (ed.), Logic Programming, Proceedings of the 1994 International Symposium. MIT Press, 1994. ISBN:0-262-52191-1.
• [45] Barklund J, Dell’Acqua P, Costantini S, Lanzarone GA. Semantical Properties of SLD-Resolution with Reflection. In: Sterling L (ed.), Logic Programming, Proceedings of ICLP’95. MIT Press, 1995. ISBN:0-262-69177-9.
• [46] van Harmelen F. Definable Naming Relations in Meta-level Systems. In: Meta-Programming in Logic, volume 649 of LNCS. Springer, Berlin, 1992 pp. 89-104. doi:10.1007/3-540-56282-6_6.
• [47] Hill PM, Lloyd JW. Analysis of metaprograms. In: Meta-Programming in Logic Programming. MIT Press, 1988 pp. 23-51. ISBN:0-262-51047-2.
• [48] Barklund J. What is a Meta-Variable in Prolog? In: Meta-Programming in Logic Programming, pp. 383-98. MIT Press, 1989. ISBN:0-262-51047-2.
• [49] Barklund J, Costantini S, Dell’Acqua P, Lanzarone GA. Semantical properties of encodings in logic programming. In: Logic Programming - Proc. 1995 Intl. Symp. MIT Press, 1995 pp. 288-302. ISBN:0-262-62099-5.
• [50] Hill P, Gallagher J. Meta-Programming in Logic Programming. In: Gabbay DM, Hogger C, Robinson JA (eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, pp. 421-497. Oxford Science Publications, Oxford University Press, 1998. doi:10.1093/oso/9780198537922.001.0001.
• [51] Dix J. A Classification Theory of Semantics of Normal Logic Programs: I. Strong Properties. Fundamenta Informaticae, 1995. 22(3):227-255. doi:10.3233/FI-1995-2233.
• [52] Feferman S. Transfinite recursive progressions of axiomatic theories. Journal of Symbolic Logic, 1962. 27:259-316. doi:10.2307/2964649.
• [53] Krötzsch M, Rudolph S, Schmitt PH. A closer look at the semantic relationship between Datalog and description logics. Semantic Web, 2015. 6(1):63-79. doi:10.3233/SW-130126.
• [54] Gottlob G, Pieris A. Beyond SPARQL under OWL 2 QL Entailment Regime: Rules to the Rescue. In: Yang Q, Wooldridge MJ (eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015. AAAI Press, 2015 pp. 2999-3007. ISBN:978-157735738-4.
• [55] Arenas M, Gottlob G, Pieris A. Expressive Languages for Querying the Semantic Web. ACM Trans. Database Syst., 2018. 43(3):13:1-13:45. doi:10.1145/3238304.
• [56] Marple K, Gupta G. Dynamic Consistency Checking in Goal-Directed Answer Set Programming. Theory Pract. Log. Program., 2014. 14(4-5):415-427. doi:10.1017/S1471068414000118.
• [57] Costantini S, Formisano A. Query answering in resource-based answer set semantics. TPLP, 2016. 16(5-6):619-635. doi:10.1017/S1471068416000478.
• [58] Apt KR, Bol RN. Logic Programming and Negation: A Survey. J. Log. Program., 1994. 19/20:9-71. doi:10.1016/0743-1066(94)90024-8.
• [59] Calimeri F, Ianni G, Ielpa G, Pietramala A, Santoro MC. A System with Template Answer Set Programs. In: Logics in Artificial Intelligence, 9th European Conference, JELIA 2004, Proc., volume 3229 of LNCS. Springer, 2004 pp. 693-697. doi:10.1007/978-3-540-30227-8_59.
• [60] Baral C, Dzifcak J, Takahashi H. Macros, Macro Calls and Use of Ensembles in Modular Answer Set Programming. In: Proc. of ICLP’06, volume 4079 of LNCS. Springer, 2006 pp. 376-390. doi:10.1007/11799573_28.
• [61] Krennwallner T. Promoting Modular Nonmonotonic Logic Programs. In: Tech. Comm. of ICLP’11, volume 11 of LIPIcs. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2011 pp. 274-279. https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=11006.
• [62] Eiter T, Fink M, Ianni G, Krennwallner T, Redl C, Schüller P. A model building framework for answer set programming with external computations. TPLP, 2016. 16(4):418-464. doi:10.1017/S1471068415000113.
• [63] Eiter T, Kaminski T, Redl C, Schüller P, Weinzierl A. Answer Set Programming with External Source Access. In: Reasoning Web. Semantic Interoperability on the Web - 13th Int. Summer School 2017, Tutorial Lectures, volume 10370 of LNCS. Springer, 2017 pp. 204-275. doi:10.1007/978-3-319-61033-7_7.
• [64] Ianni G, Martello A, Panetta C, Terracina G. Efficiently Querying RDF(S) Ontologies with Answer Set Programming. J. Log. Comput., 2009. 19(4):671-695. doi:10.1093/logcom/exn043.
• [65] Eiter T, Germano S, Ianni G, Kaminski T, Redl C, Schüller P, Weinzierl A. The DLVHEX System. KI, 2018. 32(2-3):187-189. 10.1007/s13218-018-0535-y.
• [66] Bajraktari L, Ortiz M, Šimkus M. Combining Rules and Ontologies into Clopen Knowledge Bases. In: McIlraith SA, Weinberger KQ (eds.), Proc. of AAAI-18. 2018 pp. 1728-1735. ISBN:978-157735800-8.
• [67] 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. doi:10.1016/j.artint.2008.04.002.
• [68] Motik B, Rosati R. Reconciling description logics and rules. J. ACM, 2010. 57(5):1-62. doi:10.1145/1754399.1754403.
• [69] McCarthy J. Elaboration tolerance. In: Proceedings of Common Sense’98. 1998. URL www-formal.stanford.edu/jmc/elaboration.html.