Deborah L. McGuinness
Stanford University, Stanford, CA, 94305
Abstract: Description logic (DL) has existed as a field for a few decades yet only somewhat recently has appeared to transform from an area of academic interest to an area of broad interest. This paper provides a brief historical perspective of description logic developments that have impacted DL usability to include communities beyond universities and research labs. This paper provides one perspective on this evolution.
Description logics (previously called terminological logics and KL-ONE-like systems) started with a motivation of providing a formal foundation for semantic networks. The first implemented DL system – KL-ONE – grew out of Brachman’s thesis [Brachman, 1977]. This work was influenced by the work on frame systems but was focused on providing a foundation for building term meanings in a semantically meaningful and unambiguous manner. It rejected the notion of maintaining an ever growing (seemingly adhoc) vocabulary of link and node names seen in semantic networks and instead embraced the notion of a fixed set of domain-independent “epistemological primitives” that could be used to construct complex, structured object descriptions. It included constructs such as “defines-an-attribute-of” as a built-in construct and expected terms like “has-employee” to be higher-level terms built up from the epistemological primitives. Higher level terms such as “has-employee” and “has-part-time-employee” could be related automatically based on term definitions instead of requiring a user to place links between them. In its original incarnation, this led to maintaining the motivation of semantic networks of providing broad expressive capabilities (since people wanted to be able to represent natural language applications) coupled with the motivation of providing a foundation of building blocks that could be used in a principled and well-defined manner. KL-ONE provided an important first step in description logic history and since then, many systems have been designed and implemented taking differing positions on the requirements of expressive power, completeness of reasoning, and tractability of reasoning. One early paper describing some description logic systems up to 1990 is provided in [MacGregor, 1991] and includes some of the earlier implemented and used systems such as BACK [Peltason, 1991], CLASSIC [Brachman et al, 1989], and LOOM [MacGregor, 1991]. K-REP [Mays et al, 1991], although not included in that article, also appeared in the same time frame.
Some of these early systems are interesting from the perspective of DLs emerging from ivory towers since one (BACK) made an attempt to be the basis of a company, another (K-REP) was the basis of a domain-specific commercial application in medical information systems which spun out of IBM, another (CLASSIC) was the basis of a family of some commercially fielded applications in the areas of data mining (IMACS [Selfridge-et-al, 1993]), knowledge-enhanced search (FindUR [McGuinness-et-al, 1998; McGuinness,2000]), and a family of configurators fielded at AT&T and Lucent that were deployed for over a decade(PROSE/QUESTAR[McGuinness-Wright, 2000]). Another (LOOM) was also was used extensively in a number of government research and application programs. Some of these (and other) early systems have had success moving from their roots in universities or industrial research labs into use in fielded (e.g. [Brachman et al, 1999], [Rychtyckyj, 1996]) applications and provide good examples of use in practice for the description logic-based applications of today.
These early systems however typically sacrificed something (usually expressive power, but sometimes completeness) in order to maintain some forms of usability (typically efficiency but sometimes understandability). The more recent set of implemented description logics are expressive (at least with respect to concept reasoning) and also maintain complete reasoners with computationally efficient implementations. A few examples of implemented description logics in this class today are DLP [Patel-Schneider, 1999], FACT [Horrocks, 1998], and RACE [Haarslev-Moeller, 1999]. These systems are interesting since they do not need to limit the number of “epistemological primitives” as much as earlier usable description logics did in order to maintain a handle on computational efficiency of reasoning. Thus they can support certain applications that need more expressive power along with guaranteed deductive closure of reasoning with efficiency. While work such as [Horrocks-Patel-Schneider, 1999] that discusses efficiency of description logic reasoning has facilitated a broader range of possible applications using today’s DLs, arguably, this was not enough to really draw description logics out into the mainstream. Similarly, while work providing environments to support DL-usage also arose, such as Ontosaurus (http://sevak.isi.edu:8950/ploom/shuttle.html), and usability learnings were compiled, such as [McGuinness-Patel-Schneider, 1999], and supporting materials such as tutorials became available, such as (http://www.bell-labs.com/project/classic/papers/ClassTut/ClassTut.html ), these were useful but arguably also not enough to draw description logics into mainstream usage. Similarly, although description logics saw maintained interest in a few application communities such as configuration with PROSE and Ford’s system, databases with continuous KRDB (http://sunsite.informatik.rwth-aachen.de/Societies/KRDB/) workshops since 1994, and medicine (e.g., [Rector et al, 1996], [Mays et al, 1997]), arguably this also was not enough to make the order of magnitude increase in interest in description logics and really pull them out of academic settings into the mainstream commercial world.
One progression that may be of most interest to those viewing description logic’s movement into more mainstream use is its progression into web usage. Arguably, this is the single use that has drawn description logics out of ivory towers more than anything else. Some communities recognized that description logics, with its long researched area of formal foundations for structured knowledge representation formalism, might be just the thing that web languages, such as XML and RDF(S) [Lassila-Swick, 1999][Brickley-Guha, 2000], could benefit from. The merging of the goals from frame-based systems of usability, from web languages of broad web usage, and from description logics of formal foundations for extensible, semantically understood systems led to efforts such as OIL [Fensel-et-al, 2001]. OIL may epitomize the effort to take DLs to the web. Most recently the OIL work was used when the same combination of goals emerged for the web language [McGuinness et al, 2001] and (http://www.daml.org/2000/10/daml-ont.html) for the Darpa Agent Markup Language program [Hendler-McGuinness, 2000] and (http://www.daml.org/about.html).
This program has a goal of facilitating the next generation web. The resulting DAML+OIL language now provides a foundation on which web applications can be built that is compatible with the emerging web standards of XML and RDF(S) and provides the formal foundations for unambiguous specification of term meanings.
There appear to be many forces that may be supporting the transition of description logics into more mainstream usage. The World Wide Web Consortium (W3C www.w3c.org) is arguably the strongest force in web standards and it now supports a semantic web activity (http://www.w3.org/2000/01/sw/Overview.html). The language for the DAML program – thus a description logic-inspired language – is expected to be the initial proposal for the web ontology language to be worked on through W3C. Additionally, many corporations are acknowledging that ontologies are central to their knowledge-oriented applications [McGuinness, 2001]. Essentially every e-commerce application, whether from a somewhat recently formed company such as VerticalNet or from a more established bricks and mortar company, such as Dell, has some ontological information stored behind its applications. Some of us who consult to companies on knowledge representation and reasoning applications, such as representation for e-commerce, are finding that CEOs and marketing directors are the people who are calling to explore the types of ontology-based applications that might be included in commercial products. Also, some venture capitalists are becoming knowledgeable and interested in the field. This is a stark contrast to the recent past when calls, if they came, typically came from technologists. Additionally applications of today and projected applications for the future appear to require more inferential power than past ontology-based applications such as simple taxonomy-based applications like Yahoo. Many people are looking for the “smarter” applications of tomorrow that will make some deductions for the user. This may provide exactly the requirements that not only allow description logics to shine, but also provide challenges to simpler “knowledge management” approaches.
In summary, description logic’s history of emphasis on formal foundations may have been the thing that kept it (and its literature) from emerging into the mainstream in the past because a plethora of formal papers may have appeared daunting to prospective readers/users. Today however, the needs of emerging applications, such as those appearing on the web have motivated people to look for foundations on which long-lived and extensible applications may be built. Thus the fact that description logics are strong in formal foundations may now be the thing that is supporting its emergence into the broader world of web applications and other application areas. This, along with the tangible results of early DL applications, work such as reasoning efficiency that is now embodied in today’s implemented systems, learnings of usability efforts, and finally, and potentially most importantly, efforts such as OIL and DAML+OIL may be putting description logics in a place where they can find commercial need, acceptance, and demand.
While any errors in presentation are my own, my description logic perspective has been greatly enhanced by my long collaboration with my CLASSIC co-authors [Borgida, 1989] Borgida, Brachman, Patel-Schneider, and Resnick, more recent collaborations with my OIL co-authors [Bechhofer et al, 2000], [Fensel et al, 2001], Bechhofer, Broekstra, Decker, Erdmann, Fensel, Goble, van Harmelen, Horrocks, Klein, Motta, Staab, and Studer, and my many DAML+OIL co-authors and colleagues (not previously mentioned) including Berners-Lee, Connolly, Dean, Decker, Fikes, Hayes, Hendler, Lassila, McIlraith, and Stein. Also, influencing this position are a number of applications of DL and ontology technology including many done at AT&T, (e.g., [McGuinness-Wright, 2000], [McGuinness, 1999], [Brachman et al, 1993]), Stanford [McGuinness et al, 2000], Cisco, and VerticalNet [Das et al, 2001].
Franz Baader and B. Hollunder. `KRIS: Knowledge representation and inference system', SIGART Bulletin, 2(3), pp 8-14, 1991.
Sean Bechhofer, Jeen Broekstra, Stefan Decker, Michael Erdmann, Dieter Fensel, Carole Goble, Frank van Harmelen, Ian Horrocks, Michel Klein, Deborah L. McGuinness, Enrico Motta, Peter F. Patel-Schneider, Steffen Staab, and Rudi Studer. ``An informal description of OIL-Core and Standard OIL: a layered proposal for DAML-O''. Posted at http://www.ontoknowledge.org/oil/downl/dialects.pdf .
Brachman, R., A Structural Paradigm for Representing Knowledge, Ph.D. thesis, Harvard University, USA, 1977.
Ronald J. Brachman, Alex Borgida, Deborah L. McGuinness, and Peter F. Patel-Schneider. "Reducing" CLASSIC to Practice: Knowledge Representation Theory Meets Reality. In Artificial Intelligence 114(1-2) pages 203-237, October, 1999. http://www.ksl.stanford.edu/people/dlm/papers/aij99-abstract.html.
Ronald J. Brachman, Deborah L. McGuinness, Peter Patel-Schneider, Lori Alperin Resnick, Alex Borgida. `Living with CLASSIC: When and how to use a KL-ONE-like language', Principles of Semantic Networks ed, Sowa, Morgan Kaufmann, 1991.
Ronald J. Brachman, Peter G. Selfridge, Loren G. Terveen, Boris Altman, Alex Borgida, Fern Halper, Thomas Kirk, Alan Lazar, Deborah L. McGuinness, Lori Alperin Resnick. ``Integrated Support for Data Archaeology.'' In International Journal of Intelligent and Cooperative Information Systems, 2:2 1993, pages 159--185.
Dan Brickley & R.V.Guha, "Resource Description Framework (RDF) Schema Specification 1.0", W3C Candidate Recommendation 27 March 2000, World Wide Web Consortium, Cambridge (MA); available on-line as http://www.w3.org/TR/rdf-schema/.
Alex Borgida, Ronald J. Brachman, Deborah L. McGuinness, and Lori Alperin Resnick. ``CLASSIC: A Structural Data Model for Objects'', Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, June, 1989, pp. 59--67.
Aseem Das, Wei Wu, and Deborah L. McGuinness. ``Industrial Strength Ontology Management''. Stanford Knowledge Systems Laboratory Technical Report KSL-01-07 2001. In the Proceedings of the International Semantic Web Working Symposium, Stanford, Ca, July, 2001. http://www.ksl.stanford.edu/people/dlm/papers/ontologyBuilderVerticalNet-abstract.html.
Dieter Fensel, Ian Horrocks, Frank van Harmelen, Deborah L. McGuinness, and Peter F. Patel-Schneider. ``OIL: An Ontology Infrastructure for the Semantic Web ''. In IEEE Intelligent Systems, Vol. 16, No. 2, March/April 2001. http://www.computer.org/intelligent/ex2001/x2038abs.htm
Richard Fikes and Deborah L. McGuinness. ``An Axiomatic Semantics for RDF, RDF Schema, and DAML+OIL'' KSL Technical Report KSL-01-01, 2001.
Enrico Franconi. `CRACK', Proceedings of the International Workshop on Description Logics - DL-98, pp 58-59, Trento, Italy, 1998.
V. Haarslev, Ralf Moeller. `RACE System Description', Proceedings of the International Workshop on Description Logics - DL-99, pp 130-132, 1999.
Jim Hendler and Deborah L. McGuinness. The DARPA Agent Markup Language. IEEE Intelligent Systems 16(6): 67-73. 2000. http://www.ksl.stanford.edu/people/dlm/papers/ieee-daml01-abstract.html.
Ian Horrocks. `FaCT and iFaCT', Proceedings of the International Workshop on Description Logics - DL-99, pp 133-135, 1999.
Ian Horrocks and Peter Patel-Schneider. `Optimizing description logic subsumption', Journal of Logic and Computation, Vol 9(3), pp 267-293, 1999.
Ian Horrocks, Alan Rector, and Carole Goble. A Description Logic Based Schema for the Classification of Medical Data, Knowledge Representation Meets Databases - KRDB-96, 1996.
Ora Lassila & Ralph Swick, "Resource Description Framework (RDF) Model and Syntax Specification", W3C Recommendation 22 February 1999, World Wide Web Consortium, Cambridge (MA); available on-line as http://www.w3.org/TR/REC-rdf-syntax/.
Robert MacGregor. The Evolving Technology of Classification-based Knowledge Representation Systems, Principles of Semantic Networks, ed, Sowa, pp 385-400. Morgan Kaufmann, Los Altos, CA, 1991.
Robert MacGregor, Inside the LOOM Description Classifier', SIGART Bulletin, 2(3), pp 88-92, 1991.
Eric Mays, Robert Dionne, and R Weida. K-Rep System Overview, SIGART Bulletin, Vol 2(3), pp 93-97, June 1991.
Eric Mays, R. Weida, Robert Dionne, M. Laker, B. White, C. Liang, and F. J. Oles. Scalable and expressive medical terminologies. Proceedings/AMIA Annual Fall Symposium 1996; 259-263.
Deborah L. McGuinness. Ontologies Come of Age. To appear in Dieter Fensel, Jim Hendler, Henry Lieberman, and Wolfgang Wahlster, editors. The Semantic Web: Why, What, and How, MIT Press, 2001. http://www.ksl.stanford.edu/people/dlm/papers/ontologies-come-of-age-abstract.html.
Deborah L. McGuinness. Ontology-enhanced Search for Primary Care Medical Literature. In the Proceedings of the International Medical Informatics Association Working Group 6- Medical Concept Representation and Natural Language Processing Conference, Phoenix, Arizona, December 16--19, 1999. http://www.ksl.stanford.edu/people/dlm/papers/imia99-abstract.html .
Deborah McGuinness, Richard Fikes, James Rice, and Steve Wilder. An Environment for Merging and Testing Large Ontologies. Principles of Knowledge Representation and Reasoning: Proceedings of the Seventh International Conference (KR2000). A. G. Cohn, F. Giunchiglia and B. Selman, editors. San Francisco, CA, Morgan Kaufmann Publishers. http://www.ksl.stanford.edu/people/dlm/papers/aaai00-abstract.html.
Deborah L. McGuinness, Richard Fikes, Lynn Andrea Stein, and James Hendler. ``DAML-ONT: An Ontology Language for the Semantic Web ''. To appear in Dieter Fensel, Jim Hendler, Henry Lieberman, and Wolfgang Wahlster, editors. The Semantic Web: Why, What, and How, MIT Press, 2001. http://www.ksl.stanford.edu/people/dlm/papers/daml-ont-abstract.html.
Deborah L. McGuinness and Peter F. Patel-Schneider. ``Usability Issues in Knowledge Representation Systems''. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, Madison, Wisconsin, July, 1998. This is an updated version of ``Usability Issues in Description Logic Systems'' published in Proceedings of International Workshop on Description Logics, Gif sur Yvette, (Paris), France, September, 1997.
Deborah L. McGuinness and Jon Wright. ``An Industrial Strength Description Logic-based Configurator Platform''. IEEE Intelligent Systems, Vol. 13, No. 4, July/August 1998, pp. 69-77.
Peter Patel-Schneider. `DLP System Description', Proceedings of the International Workshop on Description Logics - DL-98, pp 87-89, Trento, Italy, 1998.
Chris Peltason. `The BACK System - An Overview', SIGART Bulletin, Vol 2(3), pp 114-119, 1991.
Alan Rector, S. Bechhofer, Carole Goble, Ian Horrocks, W. A. Nowlan, and W. D. Solomon. The GRAIL concept modelling language for medical terminology. Artificial Intelligence in Medicine 1997; 9:139-171.
Nestor Rychtyckyj. `DLMS: An Evaluation of KL-ONE in the Automobile Industry', Proceedings of the International Knowledge Representation and Reasoning Conference, pp 588-596, 1996.