What's in an Attribute? Consequences for the Least Common Subsumer
  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.
