Abstract
Mainstream research in Description Logics (DLs) until recently concentrated on increasing the expressive power of the employed description language while keeping standard inference problems like subsumption and instance manageable in the sense that highly optimized reasoning procedures for them behave well in practice. One of the main successes of this line of research was the adoption of OWL DL, which is based on an expressive DL, as the standard ontology language for the Semantic Web.
More recently, there has been a growing interest in more light-weight DLs, and in other kinds of inference problems, mainly triggered by need in applications with large-scale ontologies. In this paper, we first review the DL research leading to the very expressive DLs with practical inference procedures underlying OWL, and then sketch the recent development of light-weight DLs and novel inference procedures.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abiteboul S, Hull R, Vianu V (1995) Foundations of Databases. Addison Wesley, Reading, MA
Baader F (1990) Terminological cycles in KL-ONE-based knowledge representation languages. In: Proc of the 8th Nat Conf on Artificial Intelligence (AAAI’90), 29 July–3 August 1990, Boston, MA, USA, pp 621–626
Baader F, Brandt S, Lutz C (2005) Pushing the EL envelope. In: Kaelbling LP, Saffiotti A (eds) Proc of the 19th Int Joint Conf on Artificial Intelligence (IJCAI 2005), 30 July–5 August 2005, Edinburgh, UK. Morgan Kaufmann, Los Altos, pp 364–369
Baader F, Brandt S, Lutz C (2008) Pushing the EL envelope further. In: Clark K, Patel-Schneider PF (eds) Proc of the Fifth International Workshop on OWL: Experiences and Directions (OWLED’08), 26–27 October 2008, Karlsruhe, Germany
Baader F, Calvanese D, McGuinness D, Nardi D, Patel-Schneider PF (eds) (2003) The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press
Baader F, Franconi E, Hollunder B, Nebel B, Profitlich H-J (1994) An empirical analysis of optimization techniques for terminological representation systems or: Making KRIS get a move on. Appl Artif Intel. Special Issue on Knowledge Base Management 4:109–132
Baader F, Küsters R (1998) Computing the least common subsumer and the most specific concept in the presence of cyclic ALN-concept descriptions. In: Proc of the 22nd German Annual Conf on Artificial Intelligence (KI’98), vol 1504, Lecture Notes in Computer Science. Springer, pp 129–140
Baader F, Küsters R (2000) Matching in description logics with existential restrictions. In: Proc of the 7th Int Conf on Principles of Knowledge Representation and Reasoning (KR 2000), 12–15 April 2000, Breckenridge, CO, USA, pp 261–272
Baader F, Küsters R (2006) Nonstandard inferences in description logics: the story so far. In: Gabbay DM, Goncharov SS, Zakharyaschev M (eds) Mathematical Problems from Applied Logic I, vol 4, International Mathematical Series. Springer, pp 1–75
Baader F, Küsters R, Borgida A, McGuinness DL (1999) Matching in description logics. J Logic Comput 9(3):411–447
Baader F, Küsters R, Molitor R (1999) Computing least common subsumers in description logics with existential restrictions. In: Proc of the 16th Int Joint Conf on Artificial Intelligence (IJCAI’99), 31 July–6 August 1999, Stockholm, Sweden, pp 96–101
Baader F, Lutz C, Suntisrivaraporn B (2005) Is tractable reasoning in extensions of the description logic EL useful in practice? In: Proc of the 2005 International Workshop on Methods for Modalities (M4M-05), 1–2 December 2005, Berlin, Germany
Baader F, Morawska B (2009) Unification in the description logic EL. In: Treinen R (ed) Proc of the 20th Int Conf on Rewriting Techniques and Applications (RTA 2009), vol 5595, Lecture Notes in Computer Science. Springer, pp 350–364
Baader F, Narendran P (2001) Unification of concepts terms in description logics. J Symb Comput 31(3):277–305
Baader F, Peñaloza R (2007) Axiom pinpointing in general tableaux. In: Proc of the Int Conf on Analytic Tableaux and Related Methods (TABLEAUX 2007), vol 4548, Lecture Notes in Artificial Intelligence. Springer, pp 11–27
Baader F, Peñaloza R (2008) Automata-based axiom pinpointing. In: Armando A, Baumgartner P, Dowek G (eds) Proc of the Int Joint Conf on Automated Reasoning (IJCAR 2008), vol 5195 Lecture Notes in Artificial Intelligence. Springer, pp 226–241
Baader F, Peñaloza R (2010) Axiom Pinpointing in General Tableaux. J Logic Comput 20(1):5–34
Baader F, Sattler U (2001) An overview of tableau algorithms for description logics. Studia Logica 69:5–40
Baader F, Sertkaya B, Turhan A-Y (2007) Computing the least common subsumer w.r.t a background terminology. J Appl Logic 5(3):392–420
Baader F, Suntisrivaraporn B (2008) Debugging SNOMED CT using axiom pinpointing in the description logic EL+. In: Proc of the International Conference on Representing and Sharing Knowledge Using SNOMED (KR-MED’08), 31 May–2 June 2008, Phoenix, Arizona
Baader F, Tobies S (2001) The inverse method implements the automata approach for modal satisfiability. In: Proc of the Int Joint Conf on Automated Reasoning (IJCAR 2001), vol 2083, Lecture Notes in Artificial Intelligence. Springer, pp 92–106
Brachman RJ, Schmolze JG (1985) An overview of the KL-ONE knowledge representation system. Cognitive Sci 9(2):171–216
Brandt S (2004) Polynomial time reasoning in a description logic with existential restrictions, GCI axioms, and – what else? In: López de Mántaras R, Saitta L (eds) Proc of the 16th Eur Conf on Artificial Intelligence (ECAI 2004), 22–27 August 2004, Valencia, Spain, pp 298–302
Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R (2005) DL-Lite: Tractable description logics for ontologies. In: Veloso MM, Kambhampati S (eds) Proc of the 20th Nat Conf on Artificial Intelligence (AAAI 2005), 25–29 July 2004, San Jose, CA, USA. AAAI Press/The MIT Press, pp 602–607
Calvanese D, de Giacomo G, Lembo D, Lenzerini M, Rosati R (2006) Data complexity of query answering in description logics. In: Doherty P, Mylopoulos J, Welty CA (eds) Proc of the 10th Int Conf on Principles of Knowledge Representation and Reasoning (KR 2006), 2–5 June 2006, Lake District, UK. AAAI Press/The MIT Press, pp 260–270
Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R (2007) Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J Autom Reason 39(3):385–429
Calvanese D, De Giacomo G, Lenzerini M (2002) 2ATAs make DLs easy. In: Proc of the 2002 Description Logic Workshop (DL 2002). CEUR Electronic Workshop Proceedings. http://ceur-ws.org/Vol-53/, last access 5.4.2011, pp 107–118
Donini FM, Colucci S, Di Noia T, Di Sciascio E (2009) A tableaux-based method for computing least common subsumers for expressive description logics. In: Boutilier C (ed) Proc of the 21st Int Joint Conf on Artificial Intelligence (IJCAI 2009), 11–17 July 2009, Pasadena, CA, USA, pp 739–745
Fitting M (1972) Tableau methods of proof for modal logics. Notre Dame J Formal Logic 13(2):237–247
Glimm B, Horrocks I, Lutz C, Sattler U (2007) Conjunctive query answering for the description logic SHIQ. In: Veloso MM (ed) Proc of the 20th Int Joint Conf on Artificial Intelligence (IJCAI 2007), 6–12 January 2007, Hyderabad, India, pp 399–404
Haarslev V, Möller R (2001) RACER system description. In: Proc of the Int Joint Conf on Automated Reasoning (IJCAR 2001), vol 2083, Lecture Notes in Artificial Intelligence. Springer, pp 701–706
Haarslev V, Möller R (2008) On the scalability of description logic instance retrieval. J Autom Reason 41(2):99–142
Hayes PJ (1979) The logic of frames. In: Metzing D (ed) Frame Conceptions and Text Understanding. Walter de Gruyter, pp 46–61 (republished in: Brachman RJ, Levesque HJ (eds) (1985) Readings in Knowledge Representation. Morgan Kaufmann, Los Altos)
Horrocks I (2003) Implementation and optimization techniques. In: Baader F, Calvanese D, McGuinness D, Nardi D, Patel-Schneider PF (eds) The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, pp 306–346
Horrocks I, Kutz O, Sattler U (2006) The even more irresistible SROIQ. In: Doherty P, Mylopoulos J, Welty CA (eds) Proc of the 10th Int Conf on Principles of Knowledge Representation and Reasoning (KR 2006) 2–5 June 2006, Lake District, UK. AAAI Press/The MIT Press, pp 57–67
Horrocks I, Patel-Schneider PF (2004) Reducing OWL entailment to description logic satisfiability. J Web Sem 1(4):345–357
Horrocks I, Patel-Schneider PF, van Harmelen F (2003) From SHIQ and RDF to OWL: The making of a web ontology language. J Web Sem 1(1):7–26
Horrocks I, Sattler U (2005) A tableaux decision procedure for SHOIQ. In: Proc of the 19th Int Joint Conf on Artificial Intelligence (IJCAI 2005), 30 July–5 August 2005, Edinburgh, UK. Morgan Kaufmann, Los Altos
Kalyanpur A, Parsia B, Horridge M, Sirin E (2007) Finding all justifications of OWL DL entailments. In: Proc of the 6th International Semantic Web Conference and 2nd Asian Semantic Web Conference, ISWC 2007+ASWC 2007, Busan, Korea, vol 4825, Lecture Notes in Computer Science. Springer, pp 267–280
Kazakov Y (2008) RIQ and SROIQ are harder than SHOIQ. In: Brewka G, Lang J (eds) Proc of the 11th Int Conf on Principles of Knowledge Representation and Reasoning (KR 2008), 16–19 September 2008, Sydney, Australia. AAAI Press, pp 274–284
Kontchakov R, Wolter F, Zakharyaschev M (2008) Can you tell the difference between DL-Lite ontologies? In: Brewka G, Lang J (eds) Proc of the 11th Int Conf on Principles of Knowledge Representation and Reasoning (KR 2008), 16–19 September 2008, Sydney, Australia. Morgan Kaufmann, Los Altos, pp 285–295
Lee K, Meyer T, Pan JZ (2006) Computing maximally satisfiable terminologies for the description logic ALC with GCIs. In: Proc of the 2006 Description Logic Workshop (DL 2006), vol 189 CEUR Electronic Workshop Proceedings
Levesque HJ, Brachman RJ (1987) Expressiveness and tractability in knowledge representation and reasoning. Comput Intell 3:78–93
Lutz C (2008) The complexity of conjunctive query answering in expressive description logics. In: Armando A, Baumgartner P, Dowek G (eds) Proc of the Int Joint Conf on Automated Reasoning (IJCAR 2008), Lecture Notes in Artificial Intelligence. Springer, pp 179–193
Lutz C, Milicic M (2007) A tableau algorithm for description logics with concrete domains and general TBoxes. J Autom Reason 38(1–3):227–259
Lutz C, Toman D, Wolter F (2009) Conjunctive query answering in the description logic EL using a relational database system. In: Proc of the 21st International Joint Conference on Artificial Intelligence IJCAI09, 11–17 July 2009, Pasadena, CA, USA. AAAI Press
Lutz C, Walther D, Wolter F (2007) Conservative extensions in expressive description logics. In: Veloso MM (ed) Proc of the 20th Int Joint Conf on Artificial Intelligence (IJCAI 2007), 6–12 January 2007, Hyderabad, India, pp 453–458
Lutz C, Wolter F (2007) Conservative extensions in the lightweight description logic EL. In: Pfenning F (ed) Proc of the 21st Int Conf on Automated Deduction (CADE 2007), vol 4603, Lecture Notes in Computer Science, Bremen, Germany. Springer, pp 84–99
Mays E, Dionne R, Weida R (1991) K-REP system overview. SIGART Bull 2(3):93–97
Minsky M (1981) A framework for representing knowledge. In: Haugeland J (ed) Mind Design. The MIT Press. A longer version appeared in: The Psychology of Computer Vision (1975) (republished in: Brachman RJ, Levesque HJ (eds) (1985) Readings in Knowledge Representation. Morgan Kaufmann, Los Altos)
Nebel B (1988) Computational complexity of terminological reasoning in BACK. Artif Intell 34(3):371–383
Nebel B (1990) Terminological reasoning is inherently intractable. Artif Intell 43:235–249
Ortiz M, Calvanese D, Eiter T (2008) Data complexity of query answering in expressive description logics via tableaux. J Autom Reason 41(1):61–98
Parsia B, Sirin E, Kalyanpur A (2005) Debugging OWL ontologies. In: Ellis A, Hagino T (eds) Proc of the 14th International Conference on World Wide Web (WWW’05), 10–14 May 2005, Chiba, Japan. ACM, pp 633–640
Patel-Schneider PF (1984) Small can be beautiful in knowledge representation. In: Proc of the IEEE Workshop on Knowledge-Based Systems, 2–4 December 1984, Denver, CO, USA. An extended version appeared as Fairchild Tech Rep 660 and FLAIR Tech Rep 37, October 1984
Peltason C (1991) The BACK system – an overview. SIGART Bull 2(3):114–119
Quillian MR (1967) Word concepts: a theory and simulation of some basic capabilities. Behavioral Sci 12:410–430 (republished in: Brachman RJ, Levesque HJ (eds) (1985) Readings in Knowledge Representation. Morgan Kaufmann, Los Altos)
Reiter R (1987) A theory of diagnosis from first principles. Artif Intell 32(1):57–95
Sattler U, Schneider T, Zakharyaschev M (2009) Which kind of module should I extract? In: Proc of the 2008 Description Logic Workshop (DL 2009), vol 477, CEUR Workshop Proceedings
Schlobach S, Cornet R (2003) Non-standard reasoning services for the debugging of description logic terminologies. In: Gottlob G, Walsh T (eds) Proc of the 18th Int Joint Conf on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico. Morgan Kaufmann, Los Altos, pp 355–362
Schmidt-Schauß M (1989) Subsumption in KL-ONE is undecidable. In: Brachman RJ, Levesque HJ, Reiter R (eds) Proc of the 1st Int Conf on the Principles of Knowledge Representation and Reasoning (KR’89), 15–18 May 1989, Toronto, Ontario, Canada. Morgan Kaufmann, Los Altos, pp 421–431
Schmidt-Schauß M, Smolka G (1991) Attributive concept descriptions with complements. Artif Intell 48(1):1–26
Schubert LK, Goebel RG, Cercone NJ (1979) The structure and organization of a semantic net for comprehension and inference. In: Findler NV (ed) Associative Networks: Representation and Use of Knowledge by Computers. Academic Press, pp 121–175
Sirin E, Parsia B (2004) Pellet: An OWL DL reasoner. In: Proc of the 2004 Description Logic Workshop (DL 2004), 6–8 June 2004, Whistler, British Columbia, Canada, pp 212–213
Suntisrivaraporn B (2008) Module extraction and incremental classification: a pragmatic approach for EL+ ontologies. In: Bechhofer S, Hauswirth M, Hoffmann J, Koubarakis M (eds) Proc of the 5th European Semantic Web Conference (ESWC’08), vol 5021, Lecture Notes in Computer Science. Springer, pp 230–244
Suntisrivaraporn B (2009) Polynomial-Time Reasoning Support for Design and Maintenance of Large-Scale Biomedical Ontologies. PhD thesis, Fakultät Informatik, TU Dresden. http://lat.inf.tu-dresden.de/research/phd/#Sun-PhD-2008, last access 5.4.2011
Tsarkov D, Horrocks I (2006) Fact++ description logic reasoner: system description. In: Furbach U, Shankar N (eds) Proc of the Int Joint Conf on Automated Reasoning (IJCAR 2006), vol 4130, Lecture Notes in Artificial Intelligence. Springer, pp 292–297
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Baader, F. What’s new in Description Logics. Informatik Spektrum 34, 434–442 (2011). https://doi.org/10.1007/s00287-011-0534-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00287-011-0534-y