Query-Driven Procedures for Hybrid MKNF Knowledge Bases

Abstract

Hybrid MKNF knowledge bases are one of the most prominent tightly integrated combinations of open-world ontology languages with closed-world (nonmonotonic) rule paradigms. Based on the logic of minimal knowledge and negation as failure (MKNF), the definition of Hybrid MKNF is parametric on the description logic (DL) underlying the ontology language, in the sense that nonmonotonic rules can extend any decidable DL language. Two related semantics have been defined for Hybrid MKNF: one that is based on the Stable Model Semantics for logic programs and one on the Well-Founded Semantics (WFS). Under WFS, the definition of Hybrid MKNF relies on a bottom-up computation that has polynomial data complexity whenever the DL language is tractable. Here we define a general query-driven procedure for Hybrid MKNF that is sound with respect to the stable model-based semantics, and sound and complete with respect to its WFS variant. This procedure is able to answer a slightly restricted form of conjunctive queries, and is based on tabled rule evaluation extended with an external oracle that captures reasoning within the ontology. Such an (abstract) oracle receives as input a query along with knowledge already derived, and replies with a (possibly empty) set of atoms, defined in the rules, whose truth would suffice to prove the initial query. With appropriate assumptions on the complexity of the abstract oracle, the general procedure maintains the data complexity of the WFS for Hybrid MKNF knowledge bases.

To illustrate this approach, we provide a concrete oracle for EL⁺, a fragment of the lightweight DL EL⁺⁺. Such an oracle has practical use, as EL⁺⁺ is the language underlying OWL 2 EL, which is part of the W3C recommendations for the Semantic Web, and is tractable for reasoning tasks such as subsumption. We show that query-driven Hybrid MKNF preserves polynomial data complexity when using the EL⁺ oracle and WFS.

References

1. Alferes, J. J., Knorr, M., and Swift, T. 2009. Queries to hybrid MKNF knowledge bases through oracular tabling. In Proceedings of the 8th International Semantic Web Conference (ISWC’09). A. Bernstein, D. R. Karger, T. Heath, L. Feigenbaum, D. Maynard, E. Motta, and K. Thirunarayan Eds., Springer, 1--16.
2. Baader, F., Brandt, S., and Lutz, C. 2005. Pushing the EL envelope. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI’05). L. P. Kaelbing and A. Saffiotti Eds., Morgan Kaufmann, 364--369.
3. Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., and Patel-Schneider, P. F., Eds. 2007. The Description Logic Handbook: Theory, Implementation, and Applications 2nd Ed. Cambridge University Press.
4. Bienvenu, M. 2008. Complexity of abduction in the EL family of lightweight description logics. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR’08). 220--230.
5. Boley, H. and Kifer, M., Eds. 2010. RIF Overview. W3C Candidate Recommendation. http://www.w3.org/TR/rif-overview/.
6. Chen, W. and Warren, D. S. 1996. Tabled evaluation with delaying for general logic programs. J. ACM 43, 1, 20--74.
7. Drabent, W. and Małuszyński, J. 2007. Well-Founded semantics for hybrid rules. In Proceedings of the 1st International Conference on Web Reasoning and Rule Systems (RR’07). M. M. Marchiori, J. Z. Pan, and C. de Sainte Marie Eds., Springer, 1--15.
8. Eiter, T., Ianni, G., Schindlauer, R., and Tompits, H. 2006. Effective integration of declarative rules with external evaluations for semantic web reasoning. In Proceedings of the 3rd European Conference on Semantic Web (ESWC’06). Y. Sure and J. Domingue Eds., Springer, 273--287.
9. Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., and Tompits, H. 2008. Combining answer set programming with description logics for the Semantic Web. Artif. Intell. 172, 12--13, 1495--1539.
10. Eiter, T., Ianni, G., Lukasiewicz, T., and Schindlauer, R. 2011. Well-founded semantics for description logic programs in the Semantic Web. ACM Trans. Comput. Logic 12, 11:1--11:41.
11. Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 365--385.
12. Glimm, B., Lutz, C., Horrocks, I., and Sattler, U. 2008. Answering conjunctive queries in the SHIQ description logic. J. Artif. Intell. Res. 31, 150--197.
13. Gomes, A. S., Alferes, J. J., and Swift, T. 2010. Implementing query answering for hybrid MKNF knowledge bases. In Proceedings 12th International Symposium on Practical Aspects of Declarative Languages (PADL’01). M. Carro and R. Peña Eds., Springer, 25--39.
14. Grosof, B. N., Horrocks, I., Volz, R., and Decker, S. 2003. Description logic programs: Combining logic programs with description logics. In Proceedings of the World Wide Web Conference (WWW’03). ACM, 48--57.
15. Hitzler, P., Krötzsch, M., Parsia, B., Patel-Schneider, P. F., and Rudolph, S., Eds. 2009. OWL 2 Web Ontology Language: Primer. W3C Recommendation. http://www.w3.org/TR/owl2-primer/.
16. Knorr, M. and Alferes, J. J. 2010. Querying in EL + with nonmonotonic rules. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI’10). H. Coelho, R. Studer, and M. Wooldridge Eds., IOS Press, 1079--1080.
17. Knorr, M. and Alferes, J. J. 2011. Querying OWL 2 QL to hybrid MKNF and non-monotonic rules. In Proceedings of the 10th International Semantic Web Conference, Semantic Web (ISWC’11). Part I. L. Aroyo, C. Welty, H. Alani, J. Taylor, A. Bernstein, L. Kagal, N. F. Noy, and E. Blomqvist Eds., Springer, 338--353.
18. Knorr, M., Alferes, J. J., and Hitzler, P. 2008. A coherent well-founded model for hybrid MKNF knowledge bases. In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI’08). M. Ghallab, C. D. Spyropoulos, N. Fakotakis, and N. Avouris Eds., IOS Press, 99--103.
19. Knorr, M., Alferes, J. J., and Hitzler, P. 2011. Local closed world reasoning with description logics under the well-founded semantics. Artif. Intell. 175, 9--10, 1528--1554.
20. Krötzsch, M., Rudolph, S., and Hitzler, P. 2008. ELP: Tractable rules for OWL 2. In Proceedings of the 7th International Semantic Web Conference (ISWC’08). A. P. Sheth, S. Staab, M. Dean, M. Paolucci, D. Maynard, T. Finin, and K. Thirunarayan Eds., Springer, 649--664.
21. Krötzsch, M., Maier, F., Krisnadhi, A. A., and Hitzler, P. 2011. A better uncle for OWL: Nominal schemas for integrating rules and ontologies. In Proceedings of the 20th International World Wide Web Conference (WWW’11). ACM, 645--654.
22. Lifschitz, V. 1991. Nonmonotonic databases and epistemic queries. In Proceedings of the 12th International Joint Conferences on Artifical Intelligence (IJCAI’91). J. Mylopoulos and R. Reiter Eds., 381--386.
23. Lloyd, J. W. 1987. Foundations of Logic Programming 2nd Ed., Springer.
24. Lukasiewicz, T. 2010. A novel combination of answer set programming with description logics for the Semantic Web. IEEE Trans. Knowl. Data Eng. 22, 11, 1577--1592.
25. Lutz, C., Toman, D., and Wolter, F. 2009. Conjunctive query answering in the description logic el using a relational database system. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09). Morgan Kaufmann, 2070--2075.
26. Mei, J., Liu, S., Xie, G. T., Kalyanpur, A., and Fokoue, A. 2009. A practical approach for scalable conjunctive query answering on acyclic EL + knowledge base. In Proceedings of the 8th International Semantic Web Conference (ISWC’09). A. Bernstein, D. R. Karger, T. Heath, L. Feigenbaum, D. Maynard, E. Motta, and K. Thirunarayan Eds., Springer, 408--423.
27. Motik, B. and Rosati, R. 2007. A faithful integration of description logics with logic programming. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI’07). M. M. Veloso Ed., AAAI Press, 477--482.
28. Motik, B. and Rosati, R. 2010. Reconciling description logics and rules. J. ACM 57, 5, 93--154.
29. Motik, B., Grau, B. C., Horrocks, I., Wu, Z., Fokoue, A., and Lutz, C. Eds. 2009. Profiles. W3C Recommendation. http://www.w3.org/TR/owl2-profiles/.
30. Patel, C., Cimino, J. J., Dolby, J., Fokoue, A., Kalyanpur, A., Kershenbaum, A., Ma, L., Schonberg, E., and Srinivas, K. 2007. Matching patient records to clinical trials using ontologies. In Proceedings of the 6th International Semantic Web Conference and 2nd Asian Semantic Web Conference, (ISWC’07 + ASWC’07). K. Aberer, K.-S. Choi, N. F. Noy, D. Allemang, K.-I. Lee, L. J. B. Nixon, J. Golbeck, P. Mika, D. Maynard, R. Mizoguchi, G. Schreiber, and P. Cudré-Mauroux Eds., Springer, 816--829.
31. Pearce, D. and Wagner, G. 1990. Reasoning with negative information I: Strong negation in logic programs. In Language, Knowledge and Intentionality, L. Haaparanta, M. Kusch, and I. Niiniluoto Eds., Acta Philosophica Fennica 49, 430--453.
32. Pereira, L. M. and Alferes, J. J. 1992. Well founded semantics for logic programs with explicit negation. In Proceedings of the 10th European Conference on Artificial Intelligence (ECAI’92). B. Neumann Ed., John Wiley and Sons, 102--106.
33. Rosati, R. 2007. On conjunctive query answering in EL. In Description Logics 2007, D. Calvanese, E. Franconi, V. Haarslev, D. Lembo, B. Motik, A.-Y. Turhan, and S. Tessaris Eds., CEUR Electronic Workshop Proceedings.
34. Sagonas, K., Swift, T., and Warren, D. S. 2000. The limits of fixed-order computation. Theor. Comput. Sci. 254, 1--2, 465--499.
35. Slota, M. and Leite, J. 2010a. On semantic update operators for answer-set programs. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI’10). H. Coelho, R. Studer, and M. Wooldridge Eds., Frontiers in Artificial Intelligence and Applications, vol. 215, IOS Press, 957--962.
36. Slota, M. and Leite, J. 2010b. Towards closed world reasoning in dynamic open worlds. Theory Pract. Logic Program. 10, 4--6, 547--564.
37. Slota, M. and Leite, J. 2011. Back and forth between rules and SE-models. In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11). J. P. Delgrande and W. Faber Eds., Lecture Notes in Computer Science, vol. 6645, Springer, Vancouver, Canada, 174--186.
38. Slota, M., Leite, J., and Swift, T. 2011. Splitting and updating hybrid knowledge bases. Theory Pract. Logic Program. 11, 4--5, 801--819.
39. Swift, T. 1999. A new formulation of tabled resolution with delay. In Recent Advances in Artifiial Intelligence, Lecture Notes in Artificial Intelligence, vol. 1695, Springer, 163--177.
40. Swift, T., Pinto, A. M., and Pereira, L. M. 2009. Incremental answer completion. In Proceedings of the 25th International Conference on Logic Programming (ICLP’09). P. M. Hill and D. S. Warren Eds., 519--524.
41. Tarski, A. 1955. Lattice-theoretic fixpoint theorem and its applications. Pacific J. Math. 5, 2, 285--309.
42. van Gelder, A. 1989. The alternating fixpoint of logic programs with negation. In Principles of Database Systems. ACM Press, 1--10.
43. van Gelder, A., Ross, K. A., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3, 620--650.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Logic programming and answer set programming

      • Nonmonotonic, default reasoning and belief revision

• Theory of computation

  • Logic

    • Constraint and logic programming

  • Theory and algorithms for application domains

    • Machine learning theory

      • Inductive inference