# What'S In An Attribute? Consequences For The Least Common Subsumer

## Ralf Küsters

KUESTERS@TI.INFORMATIK.UNI-KIEL.DE
Institut für Informatik und Praktische Mathematik Christian-Albrechts-Universitat zu Kiel 24098 Kiel Germany Alex Borgida Department of Computer Science Rutgers University Piscataway, NJ 08855 USA
BORGIDA @CS. RUT GERS. EDU

## Abstract

Functional relationships between objects, called "attributes", are of considerable importance in knowledge representation languages, including Description Logics (DLs). A study of the literature indicates that papers have made, often implicitly, different assumptions about the nature of attributes: whether they are always required to have a value, or whether they can be partial functions. The work presented here is the first explicit study of this difference for subclasses of the Classic DL, involving the same-as concept constructor.

It is shown that although determining subsumption between concept descriptions has the same complexity (though requiring different algorithms), the story is different in the case of determining the least common subsumer (lcs).  For attributes interpreted as partial functions, the lcs exists and can be computed relatively easily; even in this case our results correct and extend three previous papers about the lcs of DLs. In the case where attributes must have a value, the lcs may not exist, and even if it exists it may be of exponential size.

Interestingly, it is possible to decide in polynomial time if the lcs exists.

## 1. Introduction

Knowledge representation systems based on Description Logics (DLs) have been the subject of continued attention in Artificial Intelligence, both as a subject of theoretical studies (Borgida, 1994; Baader, 1996; Baader & Sattler, 2000; Giacomo & Lenzerini, 1996; Calvanese, Giacomo, & Lenzerini, 1999b) and in applications (Artale, Franconi, Guarino, &
Pazzi, 1996; Brachman, McGuinness, Patel-Schneider, & Borgida, 1999; McGuinness &
Patel-Schneider, 1998). More impressively, DLs have found applications in other areas involving information processing, such as databases (Borgida, 1995; Calvanese, Lenzerini, & Nardi, 1999), semi-structured data (Calvanese, Giacomo, & Lenzerini, 1998, 1999a),
information integration (Calvanese, Giacomo, Lenzerini, Nardi, & Rosati, 1998; Borgida
& Küsters, 2000), as well as more general problems su as configuration (McGuinness
& Wright, 1998) and software engineering (Borgida & Devanbu, 1999; Devanbu & Jones, 1997). In fact, wherever the ubiquitous term "ontology" is used these days (e.g., for pro-
©2001 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.