=Paper=
{{Paper
|id=Vol-1/paper-7
|storemode=property
|title=Do we need the closed world assumption in knowledge representation?
|pdfUrl=https://ceur-ws.org/Vol-1/hustadt-long.pdf
|volume=Vol-1
|authors=U. Hustadt
}}
==Do we need the closed world assumption in knowledge representation?==
https://ceur-ws.org/Vol-1/hustadt-long.pdf
Do we need the closed-world assumption in knowledge
representation?
Ullrich Hustadt
Max-Planck-Institut fur Informatik
Im Stadtwald, D-66123 Saarbrucken
e-mail hustadt@mpi-sb.mpg.de
1 Introduction typically used in the construction of the knowledge
Database systems and knowledge representation sys- base of a reasoning agent. A knowledge base can
tems represent and reason about some aspect of the be thought of as representing the beliefs of such
real world. In both it is common to separate the an agent. One of the most prominent knowledge
two functions of representation, i.e. describing the representation formalisms is kl-one [Brachman and
conceptual scheme and the actual data, and compu- Schmolze,1985] which has been used in the construc-
tation, i.e. answering of queries and manipulation of tion of natural language processing systems.
data. The knowledge representation language of kl-one
The database management system of a database and all it's derivates can be considered as a subset
system provides a data definition language to de- of rst-order logic with equality. With respect to
scribe the conceptual scheme. The data de nition describing structural properties of objects and con-
language is used to describe the database in terms ceptual schemes they are more expressive than the
of a data model. Operations on the database re- data de nition languages corresponding to the rela-
quire a specialized language, called a data manipu- tional or object-oriented model.
lation language or query language. One of the most In the late eighties inference in kl-one was shown
important data models is the relational model which to be undecidable [Schmidt-Schauss,1989]. Since
describes the world in terms of atomic values and re- then the emphasis in research has been on devel-
lations on the set of all atomic values. Data manip- oping and investigating systems that are computa-
ulation languages of the relational model comprise tionally well behaved, i.e. are tractable or at least
the relational algebra, and the domain and tuple re- decidable [Brachman et al.,1991; Donini et al.,1991;
lational calculi. The object-oriented model supports Buchheit et al.,1993]. As a result many commonly
a more elaborated description of the world by allow- used knowledge representation languages have re-
ing complex objects, i.e. objects constructed using stricted expressiveness and are in their current form
record formation and set formation, classes, i.e. ab- no longer suitable for natural language applications.
stract data types describing methods, which are op- They are still more expressive than data de nition
erations to be performed on the objects, and class languages, but the question can be risen whether
hierarchies. there is an application needing this additional ex-
The data manipulation languages of these data pressive power.
models are based on the following assumptions. Nevertheless, data manipulation languages and
query languages of knowledge representation for-
The closed-world assumption malisms di er considerably in their underlying as-
which says that all information that is not true sumptions.
in the database is considered as false. The open-world assumption
The unique-name assumption which says that there can be true facts that are
which says that two distinct constants (either not contained in the knowledge base.
atomic values or objects) necessarily designate The unique-name assumption
two di erent objects in the universe. which says that two distinct constants (either
The domain-closure assumption atomic values or objects) necessarily designate
which says that there are no other objects in the two di erent objects in the universe.
universe than those designated by constants of The open-domain assumption
the database. which says that there can be more objects in the
These assumptions are important to understand the universe than those designated by constants in
way computations are performed in databases. the knowledge base unless a constraint in the
Knowledge representation formalisms are aimed knowledge base prevents this.
to represent general conceptual information and are That means, that even if the data de nition language
Acknowledgments: This work has been supported and the data manipulation language of a database
by the German Ministry for Research and Technology management system and a knowledge base manage-
(BMFT) under grant ITS 9102 (Project Logo). Respon- ment system would coincide, the results of data ma-
sibility for the contents lies with the author. nipulations would di er.
In the next section I will give some examples that following way.
show the usefulness of closed-world inferences in nat- (?lambda ?x car(inst: ?x) or
ural language processing. Thus knowledge represen-
tation languages sticking to the open-world assump- truck(inst: ?x)) (4)
tion seem to be insucient for natural language pro- An expression of the (?lambda ?x P ) denotes the
cessing. set of all ?x satisfying P . The answer we have to
infer from the knowledge base is that veh1 and veh2
2 Query answering in Natural both belong to this set.
Language Processing Obviously, this answer cannot be computed by the
comment and question handler without taking dec-
In cooperation with the PRACMA Project1 (De- laration (1) into account. For instance, it is not pos-
partment of Computer Science, University of Saar- sible to nd the correct answer to (4) by computing
brucken) we have been developing a suitably ex- the answer sets for (?lambda ?x car(inst: ?x))
tended knowledge representation system, called mo- and (?lambda ?x truck(inst: ?x)) and to return
tel [Hustadt and Nonnengart,1993], which is in- the union of the resulting sets as an answer.
tended to be a module of the pracma system. The A question of the buyer concerning which objects
PRACMA Project [Jameson et al.,1994] is concerned do not belong to the set of trucks is translated into
with the modeling of noncooperative information- the following NLL expression.
providing dialogues. An example from pracma's
domain is the dialogue between a person S trying to (?lambda ?x not car(inst: ?x)) (5)
sell her used car to a potential buyer B. Naturally, Whereas the closed-world assumption would allow
the goals of S con ict in part with those of B. us to infer that veh1 belongs to this set, the open-
In the nal implementation, the natural language world assumption underlying NLL doesn't support
analysis module of the pracma system will use this conclusion.
the semantic representation language NLL [Laub- The question whether all cars are vehicles can also
sch and Nerbonne,1991] to represent the German- be formulated in NLL. To answer this question we
language input strings. The resulting NLL expres- can try to infer
sions will be stored in the pragmatic dialogue mem-
ory. Various modules will process the content of the (forall ?x vehicle(inst: ?x) if
dialogue memory, the most important one for us is car(inst: ?x)) (6)
the comment and question handler. The result of from the knowledge base. The answer to this ques-
this module is transfered to the natural language tion has to be independent of the constants currently
generator which is responsible for verbalizing NLL occurring in our knowledge base. On the basis of
expressions. declaration (1), the answer has to be positive.
NLL contains a rst-order logic core with anadic
predicates, generalized quanti ers, plural reference Now let us assume that the left front seat of veh2
expressions, and -abstraction. To t the pur- is red. Choosing lfseat to designate the left front
poses of pracma the language has been extended seat, this can be represented in the following way.
by modal operators. hasPart(inst: veh2, theme: lfseat) (7)
Suppose the knowledge base of the car seller S seat(inst: lfseat) (8)
contains declarations de ning that vehicles are either
cars or trucks, veh1 is a truck, and veh2 is a vehicle. hasColour(inst: lfseat, theme: red) (9)
This can be represented in NLL in the following To answer the question whether all seats of veh2
way. are red we have to try to infer the following NLL
(forall ?x vehicle(inst: ?x) iff expression.
(car(inst: ?x) or (forall ?x
truck(inst: ?x)) (1) hasColour(inst: ?x, theme: red)
truck(inst: veh1) (2) if hasPart(inst: veh2, theme: ?x)
vehicle(inst: veh2) (3) and seat(inst: ?x)) (10)
Here veh1 and veh2 are constants, vehicle, car, Because of the open-domain and open-world as-
and truck are predicate symbols. In NLL argu- sumption, the answer to the question cannot be pos-
ments of predicates are identi ed via keywords, e.g. itive. Although the only seat the car seller knows to
inst, rather than positions in argument vectors. be part of veh2 is actually red, there may be other
Any identi er preceded by a question mark, e.g. seats of veh2 and these seats may not be red.
?x, is a variable. In addition we have used the Intuitively, a positive answer is much more plau-
boolean operators iff (equivalence) and or (disjunc- sible. We would assume that the car seller knows all
tion), and the universal quanti er forall in decla- the seats of veh2 and knows the colour of every seat
ration (1). of veh2. It is possible to extend the knowledge base
Now a question of the buyer concerning which ob- using number restrictions in such a way that we can
jects are either cars or trucks is represented in the infer a positive answer, e.g.
1
PRACMA is short for `PRocessing Arguments be- ((= 1) ?x hasPart(inst: veh2, theme: ?x)
tween Controversially Minded Agents.' and seat(inst: ?x)) (11)
declares that veh2 has exactly one seat. decla- [Brachman et al., 1991] Ron J. Brachman, Debo-
rations (7),(8),(9), and (11) taken together allow rah L. McGuinness, Peter F. Patel-Schneider, and
us to answer query (10) positively. However, it A. Borgida. Living with classic: When and how
seems to be more natural to extend the language to use a kl-one-like language. In J. F. Sowa,
by an epistemic modal operator in the style of Lif- editor, Principles in Semantic Networks: Explo-
schitz [Lifschitz,1991] to solve the problem. For a rations in the Representation of Knowledge, pages
description of an extension of the knowledge repre- 401{456. Morgan Kaufmann, San Mateo, Califor-
sentation language ALC by an epistemic operator nia, 1991.
refer to Donini et al. [Donini et al.,1992]. [Buchheit et al., 1993] M. Buchheit, F. M. Donini,
Suppose our language contains such an epistemic and A. Schaerf. Decidable reasoning in terminolo-
operator K. Then we have two possibilities to get a gical knowledge representation systems. Research
positive answer to the question. The rst possibility Report RR-93-10, Deutsches Forschungszentrum
is to reformulate the question slightly in the follow- fur Kunstliche Intelligenz, Saarbrucken, Germany,
ing way. 1993.
(forall ?x [Donini et al., 1991] F. M. Donini, M. Lenzerini,
hasColour(inst: ?x, theme: red) if D. Nardi, and W. Nutt. The complexity of concept
K(hasPart(inst: veh2, theme: ?x) languages. In J. Allen, R. Fikes, and E. Sandewall,
and seat(inst: ?x))) (12) editors, Proceedings of the Second International
Conference on Principles of Knowledge Represen-
Now the question is whether all known seats of veh2 tation and Reasoning, pages 151{162, Cambridge,
are red and the answer has to be positive. This USA, April 22{25 1991. Morgan Kaufmann.
approach causes the problem how the natural lan- [Donini et al., 1992] F. M. Donini, M. Lenzerini,
guage analysis module should determine the epis- D. Nardi, A. Schaerf, and W. Nutt. Adding
temic character of question (12) opposed to the non- Epistemic Operators to Concept Languages. In
epistemic character of question (6). B. Nebel, C. Rich, and W. Swartout, editors, Pro-
The second possibility is to add a declaration of ceedings of the Third International Conference on
the following form to the knowledge base Principles of Knowledge Representation and Rea-
not (hasPart(inst: veh2, theme: ?x) soning, pages 342{353, Cambridge, USA, 1992.
and seat(inst: ?x)) if Morgan Kaufmann.
not K(hasPart(inst: veh2, theme: ?x) [Hustadt and Nonnengart, 1993] U. Hustadt and A.
and seat(inst: ?x)) (13) Nonnengart. Modalities in knowledge representa-
tion. In Chris Rowles, Huan Liu, and Norman Foo,
This declaration allows to conclude that an object editors, Proceedings of the 6th Australian Joint
is either not part of veh2 or not a seat if it is not Conference on Arti cial Intelligence, pages 249{
known to be part of veh2 and a seat. 254, Melbourne, Australia, 16{19 November 1993.
Obviously, we are now able to turn our knowledge World Scienti c.
base system into a database system either by suit- [Jameson et al., 1994] Anthony Jameson, B. Kip-
ably adding epistemic operators to all the queries or per, A. Ndiaye, R. Schafer, J. Simons, T. Weis,
by adding enough epistemic rules to the knowledge and D. Zimmermann. Cooperating to be noncoop-
base. Therefore, the extension of knowledge repre- erative: The dialog system pracma. To appear in
sentation languages with an epistemic operator is a the Proceedings of the 18th Annual German Con-
rst step to unify the database world and the knowl- ference on Arti cial Intelligence, 1994. Springer.
edge base world.
[Laubsch and Nerbonne, 1991] J. Laubsch and J.
3 Future Work Nerbonne. An Overview of NLL. Technical re-
It is well-known that theorem proving in a rst- port, Hewlett Packard Laboratories, May 1991.
order language containing an epistemic operator is [Lifschitz, 1991] Vladimir Lifschitz. Nonmonotonic
not even semi-decidable. Although the answers to databases and epistemic queries. In Proceedings
the example questions presented in the previous sec- of the Twelfth International Conference on Arti-
tion seem to be derived easily, there is no hope to nd cial Intelligence, pages 381{386, Sydney, Aus-
a correct and complete inference mechanism which tralia, August 24{30 1991. Morgan Kaufmann.
is able to deduce them. [Schmidt-Schauss, 1989] M. Schmidt-Schauss. Sub-
If we need a correct inference mechanism, the only sumption in kl-one is Undecidable. In R. J.
possibility we have is to restrict the knowledge rep- Brachman and H. J. Levesque, and R. Reiter, edi-
resentation language, i.e. we have to identify a de- tors,Proceedings of the First International Confer-
cidable fragment of NLL to which we can add an ence on Principles of Knowledge Representation
epistemic operator without loosing decidability. and Reasoning, pages 421{431, Toronto, Canada,
References May 15{19 1989. Morgan Kaufmann.
[Brachman and Schmolze, 1985] Ron J. Brachman
and J. G. Schmolze. An Overview of the kl-one
knowledge representation system. Cognitive Sci-
ence, 9(2):171{216, 1985.