Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-17T22:27:35.205Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient description logic reasoning in Prolog: The DLog system

Published online by Cambridge University Press:  01 May 2009

GERGELY LUKÁCSY  and
PÉTER SZEREDI
GERGELY LUKÁCSY
Affiliation:
Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Magyar tudósok körútja 2, H-1117, Hungary (e-mail: [email protected], [email protected])
PÉTER SZEREDI
Affiliation:
Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Magyar tudósok körútja 2, H-1117, Hungary (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Traditional algorithms for description logic (DL) instance retrieval are inefficient for large amounts of underlying data. As DL is becoming more and more popular in areas such as the Semantic Web and information integration, it is very important to have systems which can reason efficiently over large data sets. In this paper we present an approach to transform DL axioms, formalised in the DL language, into a Prolog program under the unique name assumption. This transformation is performed with no knowledge about particular individuals: they are accessed dynamically during the normal Prolog execution of the generated program. This technique, together with the top-down Prolog execution, implies that only those pieces of data are accessed that are indeed important for answering the query. This makes it possible to store the individuals in a database instead of memory, which results in better scalability and helps in using DL ontologies directly on top of existing information sources. The transformation process consists of two steps: (1) the DL axioms are converted to first-order clauses of a restricted form, and (2) a Prolog program is generated from these clauses. Step (2), which is the focus of the present paper, actually works on more general clauses than those obtainable by applying step (1) to a knowledge base. We first present a base transformation, the output of which can be either executed using a simple interpreter or further extended to executable Prolog code. We then discuss several optimisation techniques, applicable to the output of the base transformation. Some of these techniques are specific to our approach, while others are general enough to be interesting for DL reasoner implementors not using Prolog. We give an overview of DLog, a DL reasoner in Prolog, which is an implementation of the techniques outlined above. We evaluate the performance of DLog and compare it to some widely used DL reasoners, such as RacerPro, Pellet and KAON2.

Keywords

description logiclogic programmingresolutionlarge data setsopen world
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 9 , Issue 3 , May 2009 , pp. 343 - 414
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baader, F., Calvanese, D., McGuinness, D., Nardi, D. and Patel-Schneider, P. F., Eds. 2004. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, Cambridge, UK.Google Scholar
Bechhofer, S. 2004. OWL web ontology language reference. W3C recommendation [online]. Accessed 23 May 2009. URL: http://www.w3.org/TR/owl-ref/Google Scholar
Bechhofer, S. 2006. The DIG description logic interface [online]. Accessed 23 May 2009. URL: http://dig.cs.manchester.ac.uk/Google Scholar
Calvanese, D., Giacomo, G. D., Lenzerini, M., Nardi, D. and Rosati, R. 1998. Description logic framework for information integration. In Proceedings of the 6th International Conference on the Principles of Knowledge Representation and Reasoning (KR'98), Trento, Italy, June 2–5, 1998, Cohn, A. G., Schubert, L. K., and Shapiro, S. C., Eds. Morgan Kaufmann, San Francisco, CA, 2–13.Google Scholar
Cheng, M. H., Parker, D. S. and van Emden, M. 1994. Prolog technology term rewriting: Applicative systems. In Proceedings of the International Workshop on Higher-Order Algebra, Logic and Term Rewriting (HOA'93), Heering, J., Meinke, K., Möller, B., and Nipkow, T., Eds. Amsterdam, The Netherlands, Springer-Verlag, Berlin/Heidelberg, Germany.Google Scholar
Costa, V. S., Warren, D. H. D. and Yang, R. 1991. The Andorra-I preprocessor: Supporting full Prolog on the basic Andorra model. In Proceedings of the 8th International Conference on Logic Programming (ICLP'91), Furukawa, K., Ed. MIT Press, Cambridge, MA, 443–456.Google Scholar
Delbru, R., Polleres, A., Tummarello, G. and Decker, S. 2008. Context dependent reasoning for semantic documents in Sindice. In Proceedings of the Fourth International Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS 2008), Domingue, J. and Anutariya, C., Eds. Karlsruhe, Germany [online]. Accessed 23 May 2009. URL: http://www.polleres.net/publications/delb-etal-2008.pdfGoogle Scholar
Eisfeld, M. 2002. Model construction for configuration design. In Proceedings of the Workshop of Applications of Description Logics. Technical University of Dresden, Germany [online]. Accessed 23 May 2009. URL: http://SunSITE.Informatik.RWTH-Aachen.de/Publications/CEUR-WS/Vol-63/Eisfeld-02.ps.gzGoogle Scholar
Eiter, T., Gottlob, G. and Mannila, H. 1997. Disjunctive datalog. ACM Transactions on Database Systems 22, 3, 364–418.CrossRefGoogle Scholar
Fernández, M., Malhotra, A., Marsh, J., Nagy, M. and Walsh, N. 2004. XML Query (XQuery) [online]. Accessed 23 May 2009. URL: http://www.w3.org/TR/xpath-datamodel/Google Scholar
Franconi, E. 2003. Natural language processing. In The Description Logic Handbook: Theory, Implementation, and Applications. Baader, et al. , Eds. Cambridge University Press, New York, 450–461.Google Scholar
Freytag, J. C. 1989. The basic principles of query optimization in relational database management systems. In Proceedings of the IFIP 11th World Computer Congress, San Francisco, CA, 1989, Ritter, G., Ed. North-Holland, Amsterdam, Netherlands, 801–807.Google Scholar
Glimm, B., Horrocks, I., Lutz, C. and Sattler, U. 2007. Conjunctive query answering for the description logic SHIQ. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), Veloso, M. M., Ed. AAAI Press, Menlo Park, CA, 399–404.Google Scholar
Grosof, B. N., Horrocks, I., Volz, R. and Decker, S. 2003. Description logic programs: Combining logic programs with description logic. In Proceedings of the 12th International World Wide Web Conference (WWW 2003), ACM, New York, NY, 48–57.CrossRefGoogle Scholar
Guo, Y., Pan, Z. and Heflin, J. 2004. An evaluation of knowledge base systems for large OWL datasets. In International Semantic Web Conference, Hiroshima, Japan, McIlraith, S. A., Plexousakis, D. and van Harmelen, F., Eds. Springer-Verlag, Berlin/Heidelberg, Germany, 274–288.Google Scholar
Haarslev, V. and Möller, R. 2004. Optimization techniques for retrieving resources described in OWL/RDF documents: First results. In Ninth International Conference on the Principles of Knowledge Representation and Reasoning, KR 2004, Whistler, BC, Canada, June 2–5, Dubois, D., Welty, C. A., and Williams, M.-A., Eds. AAAI Press, Menlo Park, CA, 163–173.Google Scholar
Haarslev, V., Möller, R., van der Straeten, R. and Wessel, M. 2004. Extended query facilities for Racer and an application to software-engineering problems. In Proceedings of the 2004 International Workshop on Description Logics (DL-2004), Whistler, BC, Canada, June 6–8, Haarslev, V. and Möller, R., Eds. 148–157 [online]. Accessed 23 May 2009. URL: http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-104/20Haarslev-a-final.pdfGoogle Scholar
Hogan, A., Harth, A. and Polleres, A. 2008. SAOR: Authoritative reasoning for the Web. In Proceedings of the Third Asian Semantic Web Conference (ASWC 2008), Bankok, Thailand, Domingue, J. and Anutariya, C., Eds. Lecture Notes in Computer Science, vol. 5367. Springer-Verlag, Berlin/Heidelberg, Germany, 76–90.Google Scholar
Horrocks, I., Li, L., Turi, D. and Bechhofer, S. 2004. The instance store: DL reasoning with large numbers of individuals. In Proceedings of DL2004, Haarslev, V. and Möller, R., Eds. British Columbia, Canada [online]. Accessed 23 May 2009. URL: http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-104/04Horrocks-final.pdfGoogle Scholar
Horrocks, I., Sattler, U., Tessaris, S. and Tobies, S. 2000. How to decide query containment under constraints using a description logic. In Proceedings of the Seventh International Conference on Logic for Programming and Automated Reasoning (LPAR'2000), Voronkov, A., Ed. Lecture Notes in Computer Science, vol. 1955. Springer-Verlag, Berlin/Heidelberg, Germany, 441–450.Google Scholar
Horrocks, I. and Voronkov, A. 2006. Reasoning support for expressive ontology languages using a theorem prover. In Proceedings of the 4th International Symposium of Foundations of Information and Knowledge Systems, Dix, J. and S. Hegner, J., Eds. Lecture Notes in Computer Science, vol. 3861. Springer, Berlin/Heidelberg, Germany, 201–218.Google Scholar
Hustadt, U., Motik, B. and Sattler, U. 2004. Reasoning for Description Logics around SHIQ in a Resolution Framework, tech. rep. FZI, Karlsruhe, Germany.Google Scholar
Hustadt, U., Motik, B. and Sattler, U. 2005. Data complexity of reasoning in very expressive description logics. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005). International Joint Conferences on Artificial Intelligence, Kaelbling, L. P. and Saffiotti, A., Eds. Professional Book Center, Denver, CO, 466–471.Google Scholar
Kowalski, R. and Kuehner, D. 1971. Linear resolution with selection function. Artificial Intelligence 2, 227–260.CrossRefGoogle Scholar
Lukácsy, G., Nagy, Zs. and Szeredi, P. 2006. Using logic programs for description logic reasoning. In Proceedings of Semantics 2006, Schaffert, S. and Sure, Y., Eds. OCG Books, Vienna, Austria, 113–125.Google Scholar
Lukácsy, G., Szeredi, P. and Kádár, B. 2008. Prolog based description logic reasoning. In Proceedings of the 24th International Conference on Logic Programming (ICLP'08), Udine, Italy, de la Banda, M. G. and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, Berlin/Heidelberg, Germany, 455–469.Google Scholar
Motik, B. 2006. Reasoning in Description Logics using Resolution and Deductive Databases, PhD thesis. Univesität Karlsruhe (TH), Karlsruhe, Germany.Google Scholar
Motik, B. and Rosati, R. 2007. A faithful integration of description logics with logic programming. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), Veloso, M. M., Ed. Morgan Kaufmann, San Francisco, CA, 477–482.Google Scholar
Muthukumar, K. and Hermenegildo, M. 1992. Compile-time derivation of variable dependency using abstract interpretation. Journal of Logic Programming 13, 2–3, 315–347.CrossRefGoogle Scholar
Nagy, Zs., Lukácsy, G. and Szeredi, P. 2006a. Description logic reasoning using the PTTP approach. In Proceedings of the 2006 International Workshop on Description Logics (DL2006), Parsia, B., Sattler, U. and Toman, D., Eds. CEUR, vol. 189. Windermere, UK, 183–191, [online]. Accessed 23 May 2009. URL: http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-189/submission_25.pdfGoogle Scholar
Nagy, Zs., Lukácsy, G. and Szeredi, P. 2006b. Translating description logic queries to Prolog. In Proceedings of the 8th International Symposium on Practical Aspects of Declarative Languages (PADL 2006), Charleston, SC, January 9–10, 2006, Hentenryck, P. V., Ed. Lecture Notes in Computer Science, vol. 3819. Springer-Verlag, Berlin/Heidelberg, Germany, 168–182.Google Scholar
Nagypál, G. and Motik, B. 2003. A fuzzy model for representing uncertain, subjective, and vague temporal knowledge in ontologies. In Proceedings of the 2003 International Conference on Ontologies, Databases and Applications of Semantics (ODBASE 2003), Meersman, R., Tari, Z. and Schmidt, D. C., Eds. Lecture Notes in Computer Science, vol. 2888. Springer, Catania, Italy, Berlin/Heidelberg, Germany, 906–923.Google Scholar
Nieuwenhuis, R. and Rubio, A. 1995. Theorem proving with ordering and equality constrained clauses. Journal of Symbolic Computation 19, 4, 321–351.CrossRefGoogle Scholar
Nilsson, U. and Maluszynski, J., Eds. 1990. Logic, Programming and Prolog. John Wiley, New York, NY.Google Scholar
Plaisted, D. A. and Greenbaum, S. 1986. A structure-preserving clause form translation. Journal Symbolic Logic and Computation 2, 3, 293–304.CrossRefGoogle Scholar
Przymusinski, T. C. 1994. Well-founded and stationary models of logic programs. Annals of Mathematics and Artificial Intelligence 12, 141–187.CrossRefGoogle Scholar
Samuel, K., Obrst, L., Stoutenburg, S., Fox, K., Franklin, P., Johnson, A., Laskey, K. J., Nichols, D., Lopez, S. and Peterson, J. 2008. Translating OWL and Semantic Web rules into Prolog: Moving toward description logic programs. Theory and Practice of Logic Programming 8, 3, 301–322.CrossRefGoogle Scholar
Sirin, E., Parsia, B., Grau, B. C., Kalyanpur, A. and Katz, Y. 2007. Pellet: A practical OWL-DL reasoner. Web Semantics 5, 2, 51–53.CrossRefGoogle Scholar
Somogyi, Z., Henderson, F. J. and Conway, T. C. 1996. The execution algorithm of Mercury, an efficient purely declarative logic programming language. Journal of Logic Programming 29, 1–3, 17–64.CrossRefGoogle Scholar
Stevens, R., Goble, C., Horrocks, I. and Bechhofer, S. 2002. OILing the way to machine understandable bioinformatics resources. IEEE Transactions on Information Technology in Biomedicine 6, 2, 129–134.CrossRefGoogle ScholarPubMed
Stickel, M. E. 1992. A Prolog technology theorem prover: a new exposition and implementation in Prolog. Theoretical Computer Science 104, 1, 109–128.CrossRefGoogle Scholar
Venken, R. 1984. A Prolog meta-interpreter for partial evaluation and its application to source to source transformation and query-optimisation. In Proceedings of the 6th European Conference on Artificial Intelligence (ECAI-84), Pisa, Italy, September 5–7, 1984, O'Shea, T., Ed. Elsevier, Amsterdam, The Netherlands, 347–356.Google Scholar
Warren, D. S. 1999. Programming in tabled Prolog (draft) [online]. Accessed 23 May 2009. URL: http://www.cs.sunysb.edu/~warren/xsbbook/book.htmlGoogle Scholar
Zombori, Zs. 2008. Efficient two-phase data reasoning for description logics. In Artificial Intelligence in Theory and Practice II, IFIP 20th World Computer Congress, TC 12: IFIP AI 2008 Stream, Milano, Italy, Bramer, M., Ed. IFIP International Federation for Information Processing, vol. 276. Springer, Boston, MA, 393–402.Google Scholar