bobdc.blog

I drive a Honda Accord EX. To even write that, I had to look at the back of my car to remember the "EX" part, because it never meant anything to me. I try to remember to mention it when I call the dealership to ask about the availability of some part, because it might matter to them, but it doesn't to me.

The "DL" in "OWL DL" used to mean about as much to me as the "EX" in "Honda Accord EX". I always thought of the three versions of the OWL language as basically being small, medium, and large, and with most OWL tools going with the Goldilocks approach of selecting the one in the middle, I always worked with that one, even if I had no idea where the plural form "Description Logics" was used. After reading chapter 1 of the Nardi and Brachman 2003 book "An Introduction to Description Logics" (PDF) I understand much more what Description Logics bring to OWL. The chapter never actually mentions OWL, but now I understand better what OWL DL has that OWL Lite doesn't, where those extra features came from, and what they buy you. I'll try to summarize the key points here, with ample quotations, and I heartily encourage you to read the whole thing. (I also encourage anyone to correct any misunderstandings in my attempts to summarize.)

The "DL" in "OWL DL" used to mean about as much to me as the "EX" in "Honda Accord EX".

According to the paper's introduction,

Research in the field of knowledge representation and reasoning is usually focused on methods for providing high-level descriptions of the world that can be effectively used to build intelligent applications. In this context, "intelligent" refers to the ability of a system to find implicit consequences of its explicitly represented knowledge.

A good goal, and for me, one of the keys to the value of OWL: finding implicit consequences of explicitly represented knowledge.

If I understand the paper correctly, Descriptions Logics build on first-order logic, an alternative to the network- and frame-based approaches to knowledge representation that became popular in the 1970s. The second paragraph of Wikipedia's entry on First-order logic gives a good idea of what it does:

While propositional logic deals with simple declarative propositions, first-order logic additionally covers predicates and quantification. Take for example the following sentences: "Socrates is a man", "Plato is a man". In propositional logic these will be two unrelated propositions, denoted for example by p and q. In first-order logic however, both sentences would be connected by the same property: Man(x), where Man(x) means that x is a man. When x=Socrates we get the first proposition - p, and when x=Plato we get the second proposition - q. Such a construction allows for a much more powerful logic when quantifiers are introduced, such as "for every x..." - for example, "for every x, if Man(x), then...". Without quantifiers, every valid argument in FOL is valid in propositional logic, and vice versa.

(The idea of "predicates" and two sentences being connected by the same property should be familiar to RDF users.) Nardi and Brachman tell us that:

Owing to their more human-centered origins, the network-based systems were often considered more appealing and more effective from a practical viewpoint than the logical systems. Unfortunately they were not fully satisfactory because of their usual lack of precise semantic characterization. The end result of this was that every system behaved differently from the others, in many cases despite virtually identical looking components and even identical relationship names.

The article describes DL's "humble origins in the late 1970's as a remedy for logical and semantic problems in frame and semantic network representations", although it wasn't always known as Description Logics.

...research in the area of Description Logics began under the label terminological systems, to emphasize that the representation language was used to establish the basic terminology adopted in the modeled domain.

Coming up with a terminology to model a domain! That should be familiar to anyone who has worked on OWL ontologies.

A particular terminological system is known as a "Description Logic" (for example, DAML+OIL, as described by this pdf file) and "DL" refers to the family of Description Logics. Knowledge Representation Systems based on Description Logics are collectively known as DL-KRS. (Nardi and Brachman also tell us that "The ancestor of DL systems is KL-ONE [Brachman and Schmolze, 1985], which signaled the transition from semantic networks to more well-founded terminological (description) logics"—can we look forward to a Description Logic named KRS-One?)

Here's their perspective on something else that makes OWL DL more powerful than OWL Lite—the ability to say that a string quartet has exactly four musicians or that a basketball team has at least five players:

Number restrictions are sometimes viewed as a distinguishing feature of Description Logics, although one can find some similar constructs in some database modeling languages (notably Entity-Relationship models).

The section titled "Reasoning" begins with this introduction to another important concept that DL brings to OWL:

The basic inference on concept expressions in Description Logics is subsumption, typically written as C D. Determining subsumption is the problem of checking whether the concept denoted by D (the subsumer) is considered more general than the one denoted by C (the subsumee). In other words, subsumption checks whether the first concept always denotes a subset of the set denoted by the second one.

For example, one might be interested in knowing whether Woman Mother. In order to verify this kind of relationship one has in general to take into account the relationships defined in the terminology... Another typical inference on concept expressions is concept satisfiability, which is the problem of checking whether a concept expression does not necessarily denote the empty concept.

That is, that there is at least one thing that it describes.

The concepts of ABox and TBox used to confuse me, but I have a clearer idea now:

A DL knowledge base is analogously typically comprised by two components—"TBox" and an "ABox". The TBox contains intensional knowledge in the form of a terminology (hence the term "TBox", but "taxonomy" could be used as well) and is built through declarations that describe general properties of concepts... The ABox contains extensional knowledge—also called assertional knowledge (hence the term "ABox")—knowledge that is specific to the individuals of the domain of discourse.

ABox assertions are about Individuals in the data (what object-oriented developers call "instances"—the actual data, as opposed to metadata) and TBox assertions build the terminology used to describe the classes. The assertion/taxonomy part makes for a nice mnemonic to keep ABoxes and TBoxes straight, similar to the ceiling/ground trick for remembering the difference between stalactites and stalagmites.

The basic reasoning task in an ABox is instance checking, which verifies whether a given individual is an instance of (belongs to) a specified concept. Although other reasoning services are usually considered and employed, they can be defined in terms of instance checking. Among them we find knowledge base consistency, which amounts to verifying whether every concept in the knowledge base admits at least one individual; realization, which finds the most specific concept an individual object is an instance of; and retrieval, which finds the individuals in the knowledge base that are instances of a given concept. These can all be accomplished by means of instance checking.

"Retrieval" sounds simple enough when you think in terms of a traditional database application, but when you use implicit as well as explicit knowledge to find individuals that are instances of a given concept, it's not so simple anymore. In fact,

The presence of individuals in a knowledge base makes reasoning more complex from a computational viewpoint [Donini et al., 1994b], and may require significant extensions of some TBox reasoning techniques.

No wonder ontologies with no associated "meatdata" are so popular!

Later, an approach that viewed the DL more as a component became evident; in this view the DL system acts as a component of a larger environment, typically leaving out functions, such those [sic] for data management, that are more effectively implemented by other technologies. The architecture where the component view is taken requires the definition of a clear interface between the components, possibly adopting different modeling languages, but focusing on Description Logics for the implementation of the reasoning services that can add powerful capabilities to the application.

This is where the real promise of this technology lies: plugging in these "reasoning services" to the many existing systems that do data management, whether the latest RDF triplestore or a straightforward MySQL or Oracle RDBMS. The paper elaborates on the relationship to database managers again later:

...Description Logics as modeling languages overlap to a large extent with other modeling languages developed in fields such as Programming languages and Database Management. While we shall focus on this relationship later, we recall here that, when compared to modeling languages developed in other fields the characteristic feature of Description Logics is in the reasoning capabilities that are associated with it. In other words, we believe that, while modeling has general significance, the capability of exploiting the description of the model to draw conclusions about the problem at hand is a particular advantage of modeling using Description Logics.

DL has another important connection to traditional database development:

In addition, Description Logics provide a formal framework that has been shown to be rather close to the languages used in semantic data modeling, such as the Entity-Relationship Model [Calvanese et al., 1998g]. Description Logics are equipped with reasoning tools that can bring to the conceptual modeling phase significant advantages, as compared with traditional languages, whose role is limited to modeling. For instance, by using concept consistency one can verify at design time whether an entity can have at least one instance, thus clearly saving all the difficulties arising from discovering such a situation when the database is being populated [Borgida, 1995].

The paper later describes a particular Description Logic and "a precise correspondence between the chosen DL and the Entity-Relationship model". There's an even more obvious correspondence to another popular concept in system development; the section on "Relationship to other fields of Computer Science" tells us that

...the underlying ideas of concept/class and hierarchical structure based upon the generality and specificity of a set of classes have appeared in many other field [sic] of Computer Science, such as Database Management and Programming Languages.

The article puts other related work into historical perspective, such as DAML+OIL, a language that derives from

DAML-ONT [McGuinness et al., 2002], an ontology language for the Web inspired by object-oriented and frame-based languages, and OIL [Fensel et al., 2001], with a similar goal of expressing ontologies, but with a closer connection to Description Logics.

The appeal of using DL with more W3C-oriented technologies such as RDF and XML becomes more apparent here:

A more recent use of Description Logics is concerned with so-called "semi-structured" data models [Calvanese et al., 1998c], which are being proposed in order to overcome the difficulties in treating data that are not structured in a relational form, such as data on the Web, data in spreadsheets, etc. In this area Description Logics are sufficiently expressive to represent models and languages that are being used in practice, and they can offer significant advantages over other approaches because of the reasoning services they provide.

The use with RDBMS and "semi-structured" data leads to what could be the biggest payoff of all for DL:

Another problem that has recently increased the applicability of Description Logics is information integration. As already remarked, data are nowadays available in large quantities and from a variety of sources. Information integration is the task of providing a unique coherent view of the data stored in the sources available. In order to create such a view, a proper relationship needs to be established between the data in the sources and the unified view of the data. Description Logics not only have the expressiveness needed in order to model the data in the sources, but their reasoning services can help in the selection of the sources that are relevant for a query of interest, as well as to specify the extraction process [Calvanese et al., 2001c].

The paper often returns to the theme that more than most knowledge representation systems, Description Logics were designed to be something that could be implemented—and not only implemented, but designed in such a way that specific features could have their effect on implementation efficiency measured and evaluated:

The way Description Logics were able to separate out the structure of concepts and roles into simple term-forming operators opened the door to extensive analysis of a broad family of languages. One could add and subtract these operators from the language and explore both the computational ramifications and the relationship of the resulting language to other formal languages in Computer Science, such as modal logics and data models for database systems.

Or, as they say in their conclusion,

Perhaps, the most important aspect of work on Description Logics has been the very tight coupling between theory and practice. The exemplary give-and-take between the formal, analytical side of the field and the pragmatic, implemented side—notable throughout the entire history of Description Logics—has been a role model for other areas of AI.

The great part about it for the rest of us is that existing implementations of this knowledge representation system are not badly-documented demos sitting on a computer at the former university of whoever wrote the paper several years ago (which is often the case with knowledge representation implementations), but W3C-standardized open source software with a wide community of practice. So get out there and play with OWL DL, and perhaps Nardi and Brachman's paper can give you the background to get even more out of these tools.