17.6.1 Description Logics

Description Logics can be viewed as an effort to better understand and specify the semantics of these earlier structured network representations, and to provide a conceptual framework that is especially well-suited to certain kinds of domain modeling. Formally, the term Description Logics refers to a family of logical approaches that correspond to varying subsets of FOL. The various restrictions placed on the expressiveness of Description Logics serve to guarantee the tractability of various critical kinds of inference. Our focus here, however, will be on the modeling aspects of DLs rather than computational complexity issues.

When using Description Logics to model an application domain, the emphasis is on the representation of knowledge about categories, individuals that belong to those categories, and the relationships that can hold among these individuals. The set of categories, or concepts, that make up the particular application domain is called its Terminology. The portion of a knowledge-base that contains the terminology is traditionally called the TBox; this is in contrast to the ABox that contains facts about individuals. The terminology is typically arranged into a hierarchical organization called an Ontology that captures the subset/superset relations among the categories.

To illustrate this approach, let's return to our earlier culinary domain, which included notions like restaurants, cuisines, and patrons, among others. We represented concepts like these in FOL by using unary predicates such as Restaurant(x); the DL equivalent simply omits the variable, so the category corresponding to the

notion of a restaurant is simply written as Restaurant. $ ^{2} $ To capture the notion that a particular domain element, such as Frasca, is a restaurant we simply assert Restaurant(Frasca) in much the same way we would in FOL. The semantics of these categories is specified in precisely the same way that was introduced earlier in Sec. 17.3: a category like Restaurant simply denotes the set of domain elements that are restaurants.

Having specified the categories of interest in a state of affairs, the next step is to arrange these categories into a hierarchical structure. There are two ways to capture the hierarchical relationships present in a terminology: we can directly assert relations between categories that are related hierarchically, or we can provide complete definitions for our concepts and then rely on these definitions to infer hierarchical relationships. The choice between these methods hinges on the use to which the resulting categories will be put and the feasibility of formulating precise definitions for many naturally occurring categories. We'll discuss the first option here, and the return to the notion of definitions later in this section.

To directly specify a hierarchical structure, we can assert subsumption relations between the appropriate concepts in a terminology. The subsumption relation is conventionally written as $ C \sqsubseteq D $, and is read as $ C $ is subsumed by $ D $; that is, all members of the category $ C $ are also members of the category $ D $. Not surprisingly, the formal semantics of this relation is provided by a simple set relation; any domain element that is in the set denoted by $ C $ is also in the set denoted by $ D $.

Continuing with our restaurant theme, adding the following statements to the TBox asserts that all restaurants are commercial establishments, and moreover that there are various sub-types of restaurants.

Restaurant ☐ CommercialEstablishment

ItalianRestaurant ☐ Restaurant

ChineseRestaurant ☐ Restaurant

MexicanRestaurant ☐ Restaurant

Ontologies such as this are conventionally illustrated using diagrams such as the one shown in Fig. 17.6 where subsumption relations are denoted by links between the nodes representing the categories.

Note however that it was precisely the vague nature of network diagrams like this that motivated the development of Description Logics. For example, from this diagram we can't tell whether or not the given set of categories is exhaustive or disjoint. That is, we can't tell if these are all the kinds of restaurants that we'll be dealing with in our domain, or whether there might be others. We also can't

tell if an individual restaurant must fall into only one of these categories, or if it is possible, for example, for a restaurant to be both Italian and Chinese. The DL statements given above are more transparent in their meaning; they simply assert a set of subsumption relations between categories and make no claims about coverage or mutual exclusion.

If an application requires coverage and disjointness information then it needs to be made explicitly. The simplest ways to capture this kind of information is through the use of negation and disjunction operators. For example, the following assertion would tell us that Chinese restaurants can't also be Italian restaurants.

ChineseRestaurant ☐ not ItalianRestaurant

Specifying that a set of sub-concepts covers a category can be achieved with with disjunction, as in the following:

Restaurant ⊆ (or Italian Restaurant Chinese Restaurant Mexican Restaurant)

Of course, having a hierarchy such as the one given in Fig. 17.6 tells us next to nothing about the concepts in it. We certainly don't know anything about what makes a restaurant a restaurant, much less Italian, Chinese or expensive. What is needed are additional assertions about what it means to be a member of any of these categories. In Description Logics such statements come in the form of relations between the concepts being described and other concepts in the domain. In keeping with its origins in structured network representations, relations in Description Logics are typically binary and are often referred to as roles, or role-relations.

To see how such relations work, let's consider some of the facts about restaurants discussed earlier in the chapter. We'll use the hasCuisine relation to capture information as to what kinds of food restaurants serve, and the hasPriceRange relation to capture how pricey particular restaurants tend to be. We can use these relations to say something more concrete about our various classes of restaurants. Let's start with our ItalianRestaurant concept. As a first approximation, we might say something uncontroversial like Italian restaurants serve Italian cuisine. To capture these notions, let's first add some new concepts to our terminology to represent various kinds of cuisine.

$$ \texttt{MexicanCuisine}\sqsubseteq\texttt{Cuisine}\qquad\quad\texttt{ExpensiveRestaurant}\sqsubseteq\texttt{Restaurant} $$

$$ \texttt{ItalianCuisine}\sqsubseteq\texttt{Cuisine} $$

ModerateRestaurant ☐ Restaurant

$$ \begin{array}{l} \text{ChineseCuisine } \sqsubseteq \text{Cuisine} \end{array} $$

CheapRestaurant ☐ Restaurant

$$ \texttt{VegetarianCuisine}\sqsubseteq\texttt{Cuisine} $$

Next let's revise our earlier version of Italian Restaurant to capture cuisine information.

$$ \texttt{Italian Restaurant}\sqsubseteq\texttt{Restaurant}\sqcap\exists\texttt{has Cuisine.ItalianCuisine} $$

The way to read this expression is that individuals in the category Italian-Restaurant are subsumed both by the category Restaurant, and by an unnamed class defined by the existential clause — the set of entities that serve Italian cuisine. An equivalent statement in FOL would be:

$$ \forall x{I t a l i a n R e s t a u r a n t}(x)\to{R e s t a u r a n t}(x)\land(\exists y{S e r v e s}(x,y)\land{I t a l i a n C u i s i n e}(y)) $$

This FOL translation should make it clear what the DL assertions given above do, and do not entail. In particular, they don't say that domain entities classified as Italian restaurants can't engage in other relations like being expensive, or even serving Chinese cuisine. And critically, they don't say much about domain entities that we know do serve Italian cuisine. In fact, inspection of the FOL translation the makes it clear that we can't infer that any new entities belong to this category based

on their characteristics. The best we can do is infer new facts about restaurants that we're explicitly told are members of this category

Of course, inferring the category membership of individuals given certain characteristics is a common and critical reasoning task that we need to support. This brings us back to the alternative approach to creating hierarchical structures in a terminology: actually providing a definition of the categories we're creating in the form of necessary and sufficient conditions for category membership. In this case, we might explicitly provide a definition for Italian Restaurant as being those restaurants that serve Italian cuisine, and Moderate Restaurant as being those whose price range is moderate.

$$ \texttt{I t a l i a n R e s t a u r a n t}\equiv\texttt{R e s t a u r a n t}\sqcap\exists\mathfrak{h}a s\texttt{C u i s i n e.I t a l i a n C u i s i n e} $$

$$ Moderate Restaurant~=~Restaurant\sqcap has Price Range.Moderate Prices $$

While our earlier statements provided necessary conditions for membership in these categories, these statements provide both necessary and sufficient conditions.

Finally, let's now consider the superficially similar case of vegetarian restaurants. Clearly, vegetarian restaurants are those that serve vegetarian cuisine. But they don't merely serve vegetarian fare, that's all they serve. We can accommodate this kind of constraint by adding an additional restriction in the form of a universal quantifier to our earlier description of VegetarianRestaurants, as follows:

VegetarianRestaurant ≡ Restaurant

hasCuisine.VegetarianCuisine

☐HasCuisine.VegetarianCuisine

Inference

Paralleling the focus of Description Logics on categories, relations and individuals, is a processing focus on a restricted subset of logical inference. Rather than employ the full range of reasoning permitted by FOL, DL reasoning systems emphasize the closely coupled problems of subsumption and instance checking.

Subsumption, as a form of inference, is the task of determining whether a superset/subset relationship exists between two concepts based on the facts asserted in a terminology. Correspondingly, instance checking asks if an individual can be a member of a particular category given the facts we know about both the individual and the terminology. The inference mechanisms underlying subsumption and instance checking go beyond simply checking for explicitly stated subsumption relations in a terminology. They must explicitly reason using the relational information asserted about the terminology to infer appropriate subsumption and membership relations.

Returning to our restaurant domain, let's add a new kind of restaurant using the following statement:

OliveGarden ☐ ModerateRestaurant ☐ ☐ hasCuisine.ItalianCuisine

Given this assertion, we might ask whether the OliveGarden chain of restaurants might be classified as an Italian restaurant, or a vegetarian restaurant. More precisely, we can pose the following questions to our reasoning system:

OliveGarden ☐ ItalianRestaurant

OliveGarden ☐ VegetarianRestaurant

The answer to the first question is positive since OliveGarden meets the criteria we specified for the category ItalianRestaurant: it's a Restaurant since we explicitly classified it as a ModerateRestaurant, which is a subtype of Restaurant, and it meets the has.Cuisine class restriction since we've asserted that directly.

The answer to the second question is negative. Recall, that our criteria for vegetarian restaurants contains two requirements: it has to serve vegetarian fare, and that's all it can serve. Our current definition for OliveGarden fails on both counts since we have not asserted any relations that state that OliveGarden serves vegetarian fare, and the relation we have asserted, hasCuisine.ItalianCuisine, contradicts the second criteria.

A related reasoning task, based on the basic subsumption inference, is to derive the implied hierarchy for a terminology given facts about the categories in the terminology. This task roughly corresponds to a repeated application of the subsumption operator to pairs of concepts in the terminology. Given our current collection of statements, the expanded hierarchy shown in Fig. 17.7 can be inferred. You should convince yourself that this diagram contains all and only the subsumption links that should be present given our current knowledge.

Note that whereas subsumption is all about concepts and categories, instance checking is the task of determining whether a particular individual can be classified as a member of a particular category. This process takes what is known about a given individual, in the form of relations and explicit categorical statements, and then compares that information against what is known about the current terminology. It then returns a list of the most specific categories to which the individual can belong.

As an example of a categorization problem consider an establishment that we're told is a restaurant and serves Italian cuisine.

Restaurant(Gondolier)

hasCuisine(Gondolier, ItalianCuisine)

Here, we're being told that the entity denoted by the term Gondolier is a restaurant and serves Italian food. Given this new information and the contents of our current

TBox, we might reasonably like to ask if this is an Italian restaurant, a vegetarian restaurant or if it has moderate prices.

Assuming the definitional statements given earlier, we can indeed categorize the Gondolier as an Italian restaurant. That is, the information we've been given about it meets the necessary and sufficient conditions required for membership in this category. And as with the OliveGarden category, this individual fails to match the stated criteria for the VegetarianRestaurant. Finally, the Gondolier might also turn out to be an moderately priced restaurant, but we can't tell at this point since we don't know anything about its prices. What this means is that given our current knowledge the answer to the query ModerateRestaurant (Gondolier) would be false since it lacks the required hasPriceRange relation.

The implementation of subsumption, instance checking, as well as other kinds of inferences needed for practical applications, varies depending on the expressivity of the Description Logic being used. However, for Description Logics of even modest power, the primary implementation techniques are based on satisfiability methods that in turn rely on the underlying model-based semantics introduced earlier in this chapter.

OWL and the Semantic Web

The highest-profile role for Description Logics has been as a part of the development of the Semantic Web. The Semantic Web is an effort to provide a way to

formally specific the semantics of the contents of... A key component of this effort involves the creation and deployment of ontologies for various application areas of interest.

The meaning representation language used to represent this knowledge is the Web Ontology Language (OWL). OWL embodies a Description Logic that corresponds roughly to the one we've been describing here. There are now widely available tools to facilitate the creation of and reasoning with OWL-based knowledge bases().

17.7 ALTERNATIVE APPROACHES TO MEANING

The idea that the translation of linguistic inputs into a formal representation made up of discrete symbols adequately captures the notion of meaning is, not surprisingly, subject to a considerable amount of debate. The following section give brief, wholly inadequate, overviews of some of the major concerns in these debates.