Abstract
An important issue for the Semantic Web is how to combine open-world ontology languages with closed-world (non-monotonic) rule paradigms. Several proposals for hybrid languages allow concepts to be simultaneously defined by an ontology and rules, where rules may refer to concepts in the ontology and the ontology may also refer to predicates defined by the rules. Hybrid MKNF knowledge bases are one such proposal, for which both a stable and a well-founded semantics have been defined. The definition of Hybrid MKNF knowledge bases is parametric on the ontology language, in the sense that non-monotonic rules can extend any decidable ontology language. In this paper we define a query-driven procedure for Hybrid MKNF knowledge bases that is sound with respect to the original stable model-based semantics, and is correct with respect to the well-founded semantics. This procedure is able to answer conjunctive queries, and is parametric on an inference engine for reasoning in the on- tology language. Our procedure is based on an extension of a tabled rule evaluation to capture reasoning within an ontology by modeling it as an interaction with an external oracle and, with some assumptions on the complexity of the oracle compared to the complexity of the ontology language, maintains the data complexity of the well-founded semantics for hybrid MKNF knowledge bases.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications, 2nd edn. Cambridge University Press, Cambridge (2007)
Chen, W., Warren, D.S.: Tabled Evaluation with Delaying for General Logic Programs. J. ACM 43(1), 20–74 (1996)
Drabent, W., Małuszynski, J.: Well-founded semantics for hybrid rules. In: Marchiori, M., Pan, J.Z., de Marie, C.S. (eds.) RR 2007. LNCS, vol. 4524, pp. 1–15. Springer, Heidelberg (2007)
Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: Effective integration of declarative rules with external evaluations for semantic web reasoning. In: Sure, Y., Domingue, J. (eds.) ESWC 2006. LNCS, vol. 4011, pp. 273–287. Springer, Heidelberg (2006)
Eiter, T., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Well-founded semantics for description logic programs in the semantic web. In: Antoniou, G., Boley, H. (eds.) RuleML 2004. LNCS, vol. 3323, pp. 81–97. Springer, Heidelberg (2004)
Gelfond, M., Lifschitz, V.: Logic programs with classical negation. In: Warren, Szeredi (eds.) ICLP 1990. MIT Press, Cambridge (1990)
Glimm, B., Horrocks, I., Lutz, C., Sattler, U.: Conjunctive query answering for the description logic SHIQ. J. of Artificial Intelligence Research 31, 151–198 (2008)
Gomes, A.S.: Derivation methods for hybrid knowledge bases with rules and ontologies. Master’s thesis, Univ. Nova de Lisboa (2009)
Knorr, M., Alferes, J.J., Hitzler, P.: A coherent well-founded model for hybrid MKNF knowledge bases. In: Ghallab, M., Spyropoulos, C.D., Fakotakis, N., Avouris, N. (eds.) Proceedings of the 18th European Conference on Artificial Intelligence, ECAI2008, pp. 99–103. IOS Press, Amsterdam (2008)
Lifschitz, V.: Nonmonotonic databases and epistemic queries. In: International Joint Conferences on Artifical Intelligence, IJCAI 1991, pp. 381–386 (1991)
Lloyd, J.W.: Foundations of Logic Programming. Springer, Berlin (1984)
Motik, B., Rosati, R.: A faithful integration of description logics with logic programming. In: 20th Int. Joint Conf on Artificial Intelligence (IJCAI), Hyderabad, India, January 6–12 2007, pp. 477–482. AAAI Press, Menlo Park (2007)
Pearce, D., Wagner, G.: Reasoning with negative information I: Strong negation in logic programs. In: Haaparanta, L., Kusch, M., Niiniluoto, I. (eds.) Language, Knowledge and Intentionality, Acta Philosophica Fennica, vol. 49, pp. 430–453 (1990)
Pereira, L.M., Alferes, J.J.: Well founded semantics for logic programs with explicit negation. In: European Conference on Artifical Intelligence, ECAI, pp. 102–106 (1992)
Rosati, R.: On conjunctive query answering in EL. In: DL 2007.CEUR Electronic Workshop Proceedings (2007)
Sagonas, K., Swift, T., Warren, D.S.: The limits of fixed-order computation. Theoretical Computer Science 254(1-2), 465–499 (2000)
Swift, T., Pinto, A., Pereira, L.: Incremental answer completion. In: Hill, P.A., Warren, D.S. (eds.) ICLP 2009. LNCS, vol. 5649, pp. 519–524. Springer, Heidelberg (2009)
van Gelder, A.: The alternating fixpoint of logic programs with negation. In: Principles of Database Systems, pp. 1–10. ACM Press, New York (1989)
van Gelder, A., Ross, K.A., Schlipf, J.S.: Unfounded sets and well-founded semantics for general logic programs. Journal of the ACM 38(3), 620–650 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alferes, J.J., Knorr, M., Swift, T. (2009). Queries to Hybrid MKNF Knowledge Bases through Oracular Tabling. In: Bernstein, A., et al. The Semantic Web - ISWC 2009. ISWC 2009. Lecture Notes in Computer Science, vol 5823. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04930-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-04930-9_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04929-3
Online ISBN: 978-3-642-04930-9
eBook Packages: Computer ScienceComputer Science (R0)