onomy in such a way that it is directly linked to the Concept conjunction is to be interpreted as set inmost specic concept it is subsumed by and to the such as Back, Classic, KRIS, and These Loom.1 initions or may even detect that a denition is incoherent. in turn automatically classify these objects with remost general concept it in turn subsumes. TermiDescription logics (also called terminological logics terms, viz. so-called concepts and roles. The forto the ability to insert a new concept into the taxplication domain explicit and then to classify these set of concept structuring primitives. Common connological knowledge representation systems thereby logical reconstruction and specication of kno wledge mer are intended to represent classes of objects of a classes of objects, or structured by means of a xed systems are used to make the terminology of an apcept structuring primitives are concept conjunction cation; on the other hand they may detect hidden ship relations which have been asserted explicitly. In ject is a member of. subsumption and equivalence relations between defgiven domain, while the latter represent binary relato semantic relations like subsumption and equivaple concept names, representing not further specied lence. More precisely, automatic classication refers Terminologies comprise two dieren t kinds of of the terminology. The systems mentioned above tersection, while the concept 8R:C denotes all those A model of the application is then given by associspect to the given terminology and to those memberor concept languages) have been designed for the ating special objects of the domain with the concepts this case, however, automatic classication refers to support the task to formalize an application in at u and universal quantication 8R:C over a role R. user to isolate the intrinsic concepts of the applileast two respects. On the one hand, they urge the tions over this domain. Concepts can either be simdenitions automatically in to a taxonomy according the ability to nd the most specic concept the obrepresentation systems descending from Kl-One originally claimed to be computationally tractable. ists no algorithm at all which decides whether one concept of Kl-One subsumes another one or not, even with respect to empty terminologies.
Unfortunately, answering such queries is in most putational worst case complexity. This applies, for In fact, Schmidt-Schau proved that there ex- [1989] instance, to the basic inference of Kl-One, although cases provably intractable, at least in terms of comsubsumes another one or not uses more than polyaccount. Notably, this result holds no matter which sibly recursive) concept introduction is taken into semantics or least or greatest xe d point semantics, of the usual kinds of semantics for recursive concept nomial time in the worst case if at least one (posas Nebel called them. [1991] in case of the standard concept language ALC, every algorithm capable of deciding whether one concept Moreover, in 1993, , it is proved that [Schild, 94a], introductions is presupposed, viz. either descriptive It is also known that even in case of the minimal structuring primitives other than concept conjuncthere exists no polynomial time algorithm which decides with respect to acyclic terminologies whether tion and universal quantication over role names), P = NP [Nebel, 1990]. one concepts subsumes another one or not, unless concept language (comprising no concept and role swered is then formulated within the same logic, the going back to McCarthy According to this [1968]. In the previous section, we have seen that, as cently, Halpern and Vardi proposed a possible [1991] traditional approach to knowledge representation, drawn from the famous blocks world. Suppose, for block or not. Figure 1 depicts exactly this situation, tractability results seems to have reached its logical sented by a nite set of form ulae of some given logic, whether every semantic structure which is a model thermore, we would like to know whether b is a top while Figure 2 gives its representation in terms of solution to this very problem of knowledge represenWe shall illustrate this traditional approach to answer depends on whether this formula is a logical tation. As a starting point, they re-examined the Woods and Schmolze put it, \the surfeit of in- [1992] knowledge representation by means of an example, instance, we would like to represent a blocks world ing the world or not. In other words, it is checked and the latter in turn lies on a table. Suppose, furconsequence of the collection of formulae representof any use is intractable (in the worst case)." Reof each of the formulae representing the world is also approach the world to be modeled should be repreinvolving two blocks, say, a and b, where a lies on b end with the conclusion that practically everything rst-order logic in the traditional w ay just described. a model of formula corresponding to the question. preferably rst-order logic. If a question to be annames which are mentioned somewhere in the termiterpretation extending V which is a model of T is a on block b, while the latter in turn lies on the table, our blocks world in terms of ALC, even when auglying on b or on the table. As a matter of fact, there of T , that is, it xes the in terpretation of Block and Then V Q is intended to mean that every in- j=T model of Q as well, where an interpretation I is said rather than an advantage. of such a valuation is called physical knowledge base, nology or in the query, but which are not dened). familiar blocks world in terms of ALC together with But before engaging into details, have a look at together with a domain, the syntactic representation tion in the spirit of the model checking approach. A the interpretation of each primitive concept and role is incomplete in that it solely states that block a lies T is an arbitrary terminology, and Q is a query. but a valuation along with a domain. When taken nite seman tic structure is shown there which xes tionally. Observe, however, that this representation emphasizing the fact that they are intended to really made for terminological reasoning, is a nuisance is no way at all to give an accurate representation of Figure 4, which shows how to represent the already mented by the inverse of roles. This means, in this case the so-called open world tradition- assumption,3 Dom just in case that I = Dom and, moreover, :I is such a physical knowledge base with domain Dom, Figure 5 modies the just considered representathe inverse of roles as it would be done tradi- 1, place customary knowledge bases. Now, suppose V to extend a physical knowledge base V with domain but it is left open whether there is any other block on. Such a semantic structure is obviously nothing interprets all those concept and role names handled the same as the one of deciding ordinary subsumppoints due to Emerson and Lei [1986]. the concept and role structuring primitives of U , We also investigated the consequences of incorpocase of ALC. Thus our results suggest that the main tion between two concepts with respect to acyclic complete knowledge. (a) in such a way that V is solely required to have a this case the computational complexity is essentially cursive concept denitions, however, we exploited storing already evaluated ones. To deal with resource of computational complexity of terminological reasoning seems to be the ability to express inversal description logic U . In fact, we proved that in a technique for computing least and greatest xed nite domain, V Q is still decidable in the uni- j=T terminologies in the minimal concept language.5 mitting of null values causes intractability, even in It turned out that even when relaxing condition rating some limited kind of incomplete knowledge turned out that, when presupposing P 6= NP, adby means of Reiter’s null values It [Reiter, 1984]. semantics. It can easily be veried that the sample those which are not further specied according to the above. cept denitions considered in the literature. The in that it ensures all primitive concepts and roles Q in polynomial time just mimics the semantics of stitutes the most liberal restriction on recursive concomment. Condition (b) is commonly presupposed for terminological reasoning, while condition (c) conquery of Figure 5 obeys each of the three conditions make sense as these concepts and roles are exactly most important condition, however, is the rst one Of course, each of these conditions calls for some to be specied extensionally. This restriction does The employed algorithm capable of deciding V j=T Another interpretation of our results is that, when graph of G such that every and-vertex of has Gs Gs trees, or binary trees. The powerful role forming primitives of U actually admit of plausible and nonserve as a powerful but tractable query language for ing all the concepts mentioned in this section, where cal knowledge base in a completely straightforward gies are to be thought of as dening so-called views, ery or-vertex has at least one of those edges it has exactly those edges it has in G and, moreover, evmay even extract from a nite and-or-graph G (or a recursive denitions of these concepts. As every tionally have recursive concept introductions along possibly dened recursiv ely. be given least xed point semantics. This is just those which are trees or binary trees. If we additaken together with the least and greatest xed poin t nary From this point of view terminolo- relations.6 the recursive concept introduction of Solvable should directed graphs exactly those which are acyclic or with least xed poin t semantics at our disposal, we to demonstrate that even though the model checking concepts such as directed acyclic graphs (DAG s), those vertices which are a root of an acyclic submanner, these concepts provide views which can be sive power that it is even capable of accurately denused to extract from a huge collection of (connected) relational databases comprising solely unary and biin G. Figure 6 gives the terminology of U dennite graph can uniquely be represented by a physicollection of such) exactly the solvable vertices, i.e., At this very point, it is important to note that the universal description logic U is so strong in expressemantics, the universal concept language U can