=Paper=
{{Paper
|id=Vol-1/paper-8
|storemode=property
|title=Tractable reasoning in a universal description logic
|pdfUrl=https://ceur-ws.org/Vol-1/schild-long.pdf
|volume=Vol-1
|authors=K. Schild
}}
==Tractable reasoning in a universal description logic==
https://ceur-ws.org/Vol-1/schild-long.pdf
Tractable Reasoning in a Universal Description Logic:
Extended Abstract
Klaus Schild
German Research Center for Arti cial Intelligence
Stuhlsatzenhausweg 3, D-66123 Saarbrucken, FRG
e-mail: schild@dfki.uni-sb.de
1 Introduction objects d of the domain for which each object re-
Description logics (also called terminological logics lated to d by the role R is a member of the con-
or concept languages) have been designed for the cept C. Although there exist many other concept
logical reconstruction and speci cation of knowledge structuring primitives, it is commonly accepted that
representation systems descending from Kl-One these two should be part of each concept language.
such as Back, Classic, KRIS , and Loom.1 These In contrast to concepts, roles are often taken to be
systems are used to make the terminology of an ap- atomic, i.e., there are no roles other than role names.
plication domain explicit and then to classify these The standard concept language ALC , for instance,
de nitions automatically into a taxonomy according does not comprise any role structuring primitives.
to semantic relations like subsumption and equiva- However, in addition to those mentioned above, this
lence. More precisely, automatic classi cation refers language comprises concept disjunction t, concept
to the ability to insert a new concept into the tax- negation : as well as existential quanti cation 9R:C
onomy in such a way that it is directly linked to the over a role R as concept structuring primitives. For
most speci c concept it is subsumed by and to the details the reader is referred to [Schmidt-Schau and
most general concept it in turn subsumes. Termi- Smolka, 1991].
nological knowledge representation systems thereby De nitions are given by associating a concept or
support the task to formalize an application in at role T with a concept name (resp., role name) TN.
least two respects. On the one hand, they urge the Such: a de nition is represented by the expression
user to isolate the intrinsic concepts of the appli- TN = T and is called concept and role introduction
cation; on the other hand they may detect hidden respectively. Terminologies are just nite sets of con-
subsumption and equivalence relations between def- cept and role introductions such that each concept
initions or may even detect that a de nition is inco- and role name is de ned at most once, i.e., for ev-
herent. ery concept and role name TN there exists at most
A model of the application is then given by associ- one concept or role introduction the left-hand side
ating special objects of the domain with the concepts of which is TN.
of the terminology. The systems mentioned above As already mentioned, a model of application do-
in turn automatically classify these objects with re- main is described in terms of the given terminology.
spect to the given terminology and to those member- More precisely, speci c objects of the domain and
ship relations which have been asserted explicitly. In pairs of objects can be associated with concepts and
this case, however, automatic classi cation refers to roles of the terminology, where these objects are syn-
the ability to nd the most speci c concept the ob- tactically represented by so-called individual names.
ject is a member of. It can either be asserted that an individual name a
Terminologies comprise two di erent kinds of is an instance of a concept C or that it is related to
terms, viz. so-called concepts and roles. The for- another individual name, say, b, by a role R. Such
mer are intended to represent classes of objects of a assertions are called assertional axioms and are rep-
given domain, while the latter represent binary rela- resented by the expressions a:C and (a; b):R respec-
tions over this domain. Concepts can either be sim- tively. A nite set of assertional axioms forms a
ple concept names, representing not further speci ed knowledge base.
classes of objects, or structured by means of a xed From a theoretical point of view, the computa-
set of concept structuring primitives. Common con- tional service provided by terminological knowledge
cept structuring primitives are concept conjunction representation systems can be reduced to answer
u and universal quanti cation 8R:C over a role R. queries of the following form with respect to a knowl-
Concept conjunction is to be interpreted as set in- edge base KB and to a terminology T : a query can
tersection, while the concept 8R:C denotes all those be an assertional axiom or an inclusion axiom of the
This work was supported by a grant from the form T1 v T2 , where T1 and T2 are either two con-
Deutsche Forschungsgemeinschaft (DFG). cepts or two roles. The meaning of such a query Q
1 For a good overview of the so-called Kl-One family posed with respect to KB and T is usually given in
the reader is referred to [Woods and Schmolze, 1992]; for terms of so-called interpretations and models. An
Kl-One itself cf. [Brachman and Schmolze, 1985] . interpretation I consists of a domain I and a val-
uation V over I along with an interpretation func-
tion :I . The valuation V over I maps each concept a
name to a subset of I I and each role name to a bi- b Is b a top block?
nary relation over . Individual names, however, table
are mapped toI singleton sets containing exactlyI one
element of . The interpretation function : , on
the other hand, just extends V to deal with arbitrary Figure 1: A sample blocks world.
concepts and roles in such a way that all concept and
role structuring primitives are interpreted properly. 8 8x:block (x) , x = a _ x = b; 9
The concept structuring primitives u, t, :, for in- >< >=
stance, are to be interpreted as the corresponding a 6= b; a 6= table ; b 6= table ;
set operations on I , while the interpretation of theI >: 8x8y:on (x; y) , (x = a ^ y = b) >;
concept 8R:C is de ned inductively as follows: if C _ (x = b ^ y = table )
and RII have already beenI
de ned,
I
then (8R:C)I is ?
fd 2 : 8e(hd; ei 2 R ); e 2 C g. j= block (b) ^ :9x:block (x) ^ on (x; b)
An interpretation I is then said to be a model
of the inclusion axiom T1 v T2 just in case that Figure 2: Representing the sample blocks world by
T1I T2I and, if a and b are individual names such rst-order formulae.
that aI is fag and bI is fbg, then I is a model of
the assertional axiom a:C (resp., of (a; b):R) just in 3 Model Checking Versus Theorem
case that a 2 C I (resp., ha; bi 2 RI ). Not very
surprising, an interpretation is a model of KB and T Proving
if it is a model of each of the elements of KB and T . In the previous section, we have seen that, as
Now, Q is said to be entailed by KB and T , written Woods and Schmolze [1992] put it, \the surfeit of in-
KB j=T Q, if and only if every interpretation which tractability results seems to have reached its logical
is a model of KB and T is a model of Q as well. end with the conclusion that practically everything
Moreover, we say that T2 subsumes T1 with respect of any use is intractable (in the worst case)." Re-
to T if and only if it holds that ; j=T T1 v T2. cently, Halpern and Vardi [1991] proposed a possible
solution to this very problem of knowledge represen-
tation. As a starting point, they re-examined the
traditional approach to knowledge representation,
2 Terminological Reasoning is going back to McCarthy [1968]. According to this
Inherently Intractable approach the world to be modeled should be repre-
sented by a nite set of formulae of some given logic,
preferably rst-order logic. If a question to be an-
Unfortunately, answering such queries is in most swered is then formulated within the same logic, the
cases provably intractable, at least in terms of com- answer depends on whether this formula is a logical
putational worst case complexity. This applies, for consequence of the collection of formulae represent-
instance, to the basic inference of Kl-One, although ing the world or not. In other words, it is checked
originally claimed to be computationally tractable. whether every semantic structure which is a model
In fact, Schmidt-Schau [1989] proved that there ex- of each of the formulae representing the world is also
ists no algorithm at all which decides whether one a model of formula corresponding to the question.
concept of Kl-One subsumes another one or not, We shall illustrate this traditional approach to
even with respect to empty terminologies. knowledge representation by means of an example,
Moreover, in [Schild, 1993, 94a], , it is proved that drawn from the famous blocks world. Suppose, for
in case of the standard concept language ALC , every instance, we would like to represent a blocks world
algorithm capable of deciding whether one concept involving two blocks, say, a and b, where a lies on b
subsumes another one or not uses more than poly- and the latter in turn lies on a table. Suppose, fur-
nomial time in the worst case if at least one (pos- thermore, we would like to know whether b is a top
sibly recursive) concept introduction is taken into block or not. Figure 1 depicts exactly this situation,
account. Notably, this result holds no matter which while Figure 2 gives its representation in terms of
of the usual kinds of semantics for recursive concept rst-order logic in the traditional way just described.
introductions is presupposed, viz. either descriptive McCarthy's approach, however, gives rise to the
semantics or least or greatest xed point semantics, problem that the need to represent all facts about
as Nebel [1991] called them. the world in terms of some logic necessitates the
It is also known that even in case of the minimal use of very expressive logics such as full rst-order
concept language (comprising no concept and role logic. This, in fact, gives rise to diculties because
structuring primitives other than concept conjunc- it is known that there exists no algorithm at all
tion and universal quanti cation over role names), which generally decides logical consequence in full
there exists no polynomial time algorithm which de- rst-order logic [Church, 1936], and this remains
cides with respect to acyclic terminologies whether true even when only nite interpretation domains
one concepts subsumes another one or not, unless are taken into consideration [Trahtenbrot, 1963].
P = NP [Nebel, 1990]. At this very point Halpern and Vardi stressed that
8 a:Block ; b:Block ; table::Block ; 9
Dom = fa; b; table g < =
[ block ] = fa; bg (a; b):on ; (b; table ):on ;
: a:(:9on 1:Block ); table :(:9on :Block ) ;
[ on ] = fha; bi; hb; tableig
?
j= block (b) ^ :9x:block (x) ^ on (x; b) T = fTopBlock =: Block u :9on 1 :Block g
?
j=T b:TopBlock
Figure 3: Representing the sample blocks world by
a semantic structure. Figure 4: Representing the sample blocks world by
an ALC 1-KB.
in many cases the natural representation of a world
to be modeled is a semantic structure rather than
a collection of formulae. If, as in the traditional Dom = fa; b; tableg
approach, queries are represented by formulae of a [ Block ] = fa; bg
given logic, a query can be answered in this case [ on ] = fha; bi; hb; tableig
depending on whether the formula representing the
query is true in the given semantic structure or not. T = fTopBlock =: Block u :9on 1 :Block g
?
That is to say, it is checked whether the semantic j=T b:TopBlock
structure is a model of the formula corresponding
to the query. The fact that a (closed) formula is Figure 5: Representing the sample blocks world by
true in a semantic structure M is usually indicated a physical ALC 1 -KB.
by M j= . Resorting to this convention, Figure 3
gives such an alternative representation of the blocks
world considered above. names which are mentioned somewhere in the termi-
In many cases this model checking approach has nology or in the query, but which are not de ned).
tremendous bene ts, at least in terms of computa- But before engaging into details, have a look at
tional complexity. For instance, checking the truth Figure 4, which shows how to represent the already
of an arbitrary closed rst-order formula2 in a familiar blocks world in terms of ALC together with
nite semantic structure xing the interpretation the inverse of roles 1 , as it would be done tradi-
of all predicates and constants occurring in is tionally. Observe, however, that this representation
known to be decidable using at most polynomial is incomplete in that it solely states that block a lies
space [Chandra and Merlin, 1977]. Recall that in on block b, while the latter in turn lies on the table,
contrast to this, there exists no algorithm at all but it is left open whether there is any other block
which is able to decide whether an arbitrary formula lying on b or on the table. As a matter of fact, there
of this kind is a logical consequence of a nite set of is no way at all to give an accurate representation of
rst-order formulae, even with only nite interpreta- our blocks world in terms of ALC , even when aug-
tion domains taken into account. However, it is also mented by the inverse of roles. This means, in this
known that rst-order model checking is still at least case the so-called open world assumption,3 tradition-
as hard as any other problem solvable using at most ally made for terminological reasoning, is a nuisance
polynomial space, hence this problem is still very rather than an advantage.
hard [Chandra and Merlin, 1977]. Anyway, Halpern Figure 5 modi es the just considered representa-
and Vardi's intention was to forge a new approach tion in the spirit of the model checking approach. A
to knowledge representation rather than to give con- nite semantic structure is shown there which xes
crete instances which allow for tractable inferences. the interpretation of each primitive concept and role
of T , that is, it xes the interpretation of Block and
4 The Model Checking Approach to on. Such a semantic structure is obviously nothing
Terminological Reasoning but a valuation along with a domain. When taken
together with a domain, the syntactic representation
It should be clear that terminological knowledge rep- of such a valuation is called physical knowledge base,
resentation, as described in the introduction, is com- emphasizing the fact that they are intended to re-
mitted to the traditional approach to knowledge rep- place customary knowledge bases. Now, suppose V
resentation rather than to the model checking ap- is such a physical knowledge base with domain Dom,
proach. In [Schild, 1994b] we investigated the con- T is an arbitrary terminology, and Q is a query.
sequences of adapting Halpern and Vardi's model Then V j=T Q is intended to mean that every in-
checking approach to terminological reasoning. It terpretation extending V which is a model of T is a
turned out that even in case of the most powerful de- model of Q as well, where an interpretation I is said
scription logic considered in the literature, answering to extend a physical knowledge base V with domain
queries become tractable just by replacing the usual Dom just in case that I = Dom and, moreover, :I
kind of knowledge bases with single nite seman- interprets all those concept and role names handled
tic structures xing the interpretation of all primi-
tive concepts and roles (i.e., those concept and role 3
In contrast to the closed world assumption, usually
made for databases, the open world assumption does not
2
This formula should involve no function symbols assume that all those facts that are not explicitly men-
other than constants. tioned (or that cannot be inferred) are taken to be false.
by V in exactly the same way as V does. the concept and role structuring primitives of U ,
In [Schild, 1994b] we investigated the computa- storing already evaluated ones. To deal with re-
tional complexity of answering such queries with re- cursive concept de nitions, however, we exploited
spect to physical knowledge bases in the description a technique for computing least and greatest xed
logic U , introduced by Patel-Schneider [1987] as a points due to Emerson and Lei [1986].
universal description logic. This concept language is It turned out that even when relaxing condition
universal in the sense that it encompasses all others (a) in such a way that V is solely required to have a
considered in the literature, except for those which nite domain, V j=T Q is still decidable in the uni-
comprise nonstandard facilities like defaults, for in- versal description logic U . In fact, we proved that in
stance. In addition to those of ALC , this language this case the computational complexity is essentially
comprises number restrictions of the form 9nR:C the same as the one of deciding ordinary subsump-
and 9 R:C as well as role value maps of the form
m tion between two concepts with respect to acyclic
R S as concept structuring primitives. Number terminologies in the minimal concept language.5
restrictions restrict the number of role llers (i.e., We also investigated the consequences of incorpo-
those objects which are related to an object by a rating some limited kind of incomplete knowledge
role), while role value maps impose restrictions on by means of Reiter's null values [Reiter, 1984]. It
the llers of two roles. The concept R S states turned out that, when presupposing P 6= NP, ad-
that all llers of the role R are also llers of the role mitting of null values causes intractability, even in
S. In addition, U admits of individual names to oc- case of ALC . Thus our results suggest that the main
curring in concepts. The role structuring primitives source of computational complexity of terminologi-
of U are the identity role , Boolean operations u, t, cal reasoning seems to be the ability to express in-
: on roles, the inverse R 1 of a role, the composition+ complete knowledge.
R S of two roles, as well as the transitive closure R
and the re exive-transitive closure R of a role. For 5 Description Logics as Tractable
details cf. [Schild, 1994b] or [Patel-Schneider, 1987].
Notably, it is known that there cannot exist any al- Query Languages for Databases
gorithm which is capable of deciding subsumption Another interpretation of our results is that, when
between two concepts (or two roles) of U , even with taken together with the least and greatest xed point
respect to empty terminologies [Schild, 1988]. semantics, the universal concept language U can
The main result of [Schild, 1994b] is that even in serve as a powerful but tractable query language for
this language V j=T Q can be decided in polynomial relational databases comprising solely unary and bi-
time provided that each of the following conditions nary relations.6 From this point of view terminolo-
is satis ed: gies are to be thought of as de ning so-called views,
(a) V has a nite domain and speci es all concept possibly de ned recursively.
and role names occurring in T and Q except for At this very point, it is important to note that the
those which are de ned in T ; universal description logic U is so strong in expres-
(b) Roles are not de ned recursively; sive power that it is even capable of accurately de n-
ing concepts such as directed acyclic graphs (DAG s),
(c) Concepts can be de ned recursively, but then trees, or binary trees. The powerful role forming
they must occur in their de nition4 positively, primitives of U actually admit of plausible and non-
i.e., they must occur in the scope of an even recursive de nitions of these concepts. As every -
number of negations, where 9m R: counts also nite graph can uniquely be represented by a physi-
as a negation. Moreover, each recursive de ni- cal knowledge base in a completely straightforward
tion must be given either least or greatest xed manner, these concepts provide views which can be
point semantics, not necessarily in a uniform used to extract from a huge collection of (connected)
way. directed graphs exactly those which are acyclic or
Of course, each of these conditions calls for some those which are trees or binary trees. If we addi-
comment. Condition (b) is commonly presupposed tionally have recursive concept introductions along
for terminological reasoning, while condition (c) con- with least xed point semantics at our disposal, we
stitutes the most liberal restriction on recursive con- may even extract from a nite and-or-graph G (or a
cept de nitions considered in the literature. The collection of such) exactly the solvable vertices, i.e.,
most important condition, however, is the rst one those vertices which are a root of an acyclic sub-
in that it ensures all primitive concepts and roles graph Gs of G such that every and-vertex of Gs has
to be speci ed extensionally. This restriction does exactly those edges it has in G and, moreover, ev-
make sense as these concepts and roles are exactly ery or-vertex has at least one of those edges it has
those which are not further speci ed according to the in G. Figure 6 gives the terminology of U de n-
semantics. It can easily be veri ed that the sample ing all the concepts mentioned in this section, where
query of Figure 5 obeys each of the three conditions the recursive concept introduction of Solvable should
above. be given least xed point semantics. This is just
The employed algorithm capable of deciding V j=T to demonstrate that even though the model check-
Q in polynomial time just mimics the semantics of 5
Technically speaking, in this case deciding V j=T Q
4 In this context, a de nition is meant to be the sub- in U is co-NP-complete.
terminology of T which contains exactly those concept 6
Note that unary and binary relations do suce as
introductions which are involved in the recursion. far as only object-oriented databases are concerned.
[Nebel, 1990] Bernhard Nebel. Terminological Rea-
DirectedGraph=: 8connected :Vertex soning is Inherently Intractable. Arti cial Intelli-
connected=: (edge t edge 1 ) gence, 43:235{249, 1990.
=: 8connected :(edge + :)
Acyclic [Nebel, 1991] Bernhard Nebel. Terminological cy-
cles: Semantics and computational properties. In
DAG =: DirectedGraph u Acyclic J. Sowa, editor, Formal Aspects of Semantic Net-
Tree=: DAG works, pages 331{361. Morgan Kaufmann, San
u 8edge :91 edge 1 :Vertex Mateo, Cal., 1991.
BinaryTree =: Tree [Patel-Schneider, 1987] Peter F. Patel-Schneider.
u 8edge :92 edge :Vertex Decidable, Logic-Based Knowledge Representa-
AndOrGraph =: DirectedGraph tion. PhD thesis, University of Toronto, Toronto,
Ont., 1987. Computer Science Department, Tech-
u 8connected :AndOrVertex nical Report 201/87.
AndOrVertex =: AndVertex u :OrVertex [Reiter, 1984] Raymond Reiter. Towards a logical
t OrVertex u :AndVertex reconstruction of relational database theory. In
Solvable =: :9edge :Vertex M. L. Brodie, J. Mylopoulos, and J. W. Schmidt,
t AndVertex u 8edge :Solvable editors, On Conceptual Modeling, pages 191{233.
Springer-Verlag, Berlin, FRG, 1984.
t OrVertex u 9edge :Solvable [Schild, 1988] Klaus Schild. Undecidability of sub-
Figure 6: A terminology of U . sumption in U . KIT Report 67, Department of
Computer Science, Technische Universitat Berlin,
Berlin, FRG, 1988.
ing approach to terminological knowledge represen- [Schild, 1993] Klaus Schild. Terminological cycles
tation does make it possible to answer queries in and the propositional -calculus. DFKI Research
polynomial time, there are actually nontrivial infer- Report RR-93-18, German Research Center for
ences to perform. Arti cial Intelligence (DFKI), Saarbrucken, FRG,
Acknowledgements April 1993.
I would like to thank Martin Buchheit for valuable [Schild, 1994a] Klaus Schild. Terminological cycles
comments on earlier drafts of the abstract. and the propositional -calculus. In Proceedings of
the 4th International Conference on Principles of
Knowledge Representation and Reasoning, pages
References 509{520, Bonn, FRG, 1994.
[Brachman and Schmolze, 1985] Ronald J. Brach- [Schild, 1994b] Klaus Schild. Tractable reasoning in
man and James G. Schmolze. An overview of the a universal description logic. DFKI Research Re-
KL-ONE knowledge representation system. Cog- port, German Research Center for Arti cial Intel-
nitive Science, 9(2):171{216, 1985. ligence (DFKI), Saarbrucken, FRG, 1994. Forth-
[Chandra and Merlin, 1977] Ashok K. Chandra and coming.
P. M. Merlin. Optimal implementation of con- [Schmidt-Schau and Smolka, 1991]
junctive queries in relational databases. In Pro- Manfred Schmidt-Schau and Gert Smolka. At-
ceedings of the 9th ACM Symposium on Theory of tributive concept descriptions with complements.
Computing, pages 77{90, 1977. Arti cial Intelligence, 48(1):1{26, 1991.
[Church, 1936] Alonzo Church. An unsolvable prob- [Schmidt-Schau, 1989] Manfred Schmidt-Schau.
lem of elementary number theory. American Jour- Subsumption in KL-ONE is undecidable. In Pro-
nal of Mathematics, 58:345{363, 1936. ceedings of the 1st International Conference on
[Emerson and Lei, 1986] E. Allen Emerson and Principles of Knowledge Representation and Rea-
Chin-Laung Lei. Ecient model checking in frag- soning, pages 421{431, Toronto, Ont., 1989.
ments of the propositional mu-calculus (extended [Trahtenbrot, 1963] B. A. Trahtenbrot. Impossibil-
abstract). In Proceedings of the 1st IEEE Sympo- ity of an algorithm for the decision problem in
sium on Logic in Computer Science, pages 267{ nite classes. American Mathematical Society
278, Boston, Mass., 1986. Translation Series, 23(2):1{5, 1963.
[Halpern and Vardi, 1991] Joseph Y. Halpern and [Woods and Schmolze, 1992] William A. Woods
Moshe Y. Vardi. Model checking vs. theorem prov- and James G. Schmolze. The KL-ONE family.
ing: A manifesto. In Proceedings of the 2nd In- In F.W. Lehmann, editor, Semantic Networks in
ternational Conference on Principles of Knowl- Arti cial Intelligence, pages 133{178. Pergamon
edge Representation and Reasoning, pages 325{ Press, 1992.
334, Cambridge, Mass., 1991.
[McCarthy, 1968] John McCarthy. Programs with
common sense. In M. Minsky, editor, Semantic In-
formation Processing, pages 403{418. MIT Press,
Cambridge, Mass., 1968.