Contexts and views
sowa@west.poly.edu (John F. Sowa)
Date: Wed, 31 May 1995 09:43:01 +0500
From: sowa@west.poly.edu (John F. Sowa)
Message-id: <9505311343.AA01475@west>
To: cg@cs.umn.edu, interlingua@isi.edu, kr-advisory@isi.edu, srkb@isi.edu
Subject: Contexts and views
Cc: fikes@sumex-aim.stanford.edu, mrg@cs.stanford.edu, vishal@cs.stanford.edu
Content-Length: 8208
Sender: owner-srkb@cs.umbc.edu
Precedence: bulk
At the last two meetings of ANSI X3T2, there were several issues
that came up concerning contexts and their representation in conceptual
graphs and KIF:
1. At the February meeting, Mike Genesereth and I were discussing the
translation of CG contexts to KIF. The most general translation is
to represent the CG box by a quoted formula in KIF. That mapping
is sometimes necessary, but Mike objected that it too often generates
quotes in KIF when a simpler, unquoted formula would be adequate.
2. At the May meeting, Vishal Sikka represented the Stanford contingent,
since Mike was not able to attend. Vishal is now translating the
IDEF1X representation of two ISO examples (Hotel Reservations and
Japan Wines) into KIF. Jim Fulton is planning to translate Vishal's
KIF version to Express, and I agreed to translate it to CGs. But
a question came up about the representation of "views" in IDEF1X.
Views can be translated directly to CG contexts, but they represent
the kinds of contexts that Mike would like to represent without quotes.
These points get into a number of questions about the syntax and semantics
of contexts and their relationship to a number of other issues, such as
the relationship between McCarthy's contexts and Barwise & Perry's
situations. The word "view", which is explicitly used in IDEF1X, is also
used with a similar (but not formally defined) meaning in many other
languages used for database design and systems analysis.
In logic, the notion of view corresponds roughly to "domain of discourse."
But most theoretical treatments of logic usually have only a single, fixed
domain of discourse. The notion of view corresponds to a subdomain, which
is part of some larger domain, but with some interesting features:
1. If a view were a strict subdomain, there would be no problem in
representing it in any version of logic, including KIF. However,
a view might contain new names, relations, and axioms that are not
defined in the outer domain. These new features are generally
"conservative extensions" in the sense that they do not create
any inconsistencies with anything in the larger domain, but it might
be possible to have different views, each of which is compatible
with the larger domain, but incompatible with one another.
2. As an example of a need for views, consider a real estate developer
who is laying out the plans for a new tract of houses. The developer
is defining a knowledge base of facts and constraints about the roads,
utilities, zoning, land use, parcel size, etc. Meanwhile, different
architects and contractors are designing their own knowledge bases
for individual lots and houses. They would all like to share as much
of the knowledge as possible: the KB for each lot should be a "view"
of the global KB, and it should be consistent with the global KB for
the entire development. However, the vocabulary used by each architect
might include many terms that apply to the details of houses that are
not included in the global KB for the entire development. Furthermore,
all the architects are working in parallel, and there is no way to
guarantee that they will all use the same words in the same way.
3. The problem of guaranteeing that the entire KB is consistent is
usually solved by building models: any first-order theory is
guaranteed to be consistent if there exists at least one model.
Architects and land developers are used to making models, in fact,
quite detailed ones with little trees, roads, houses, and cars.
As long as the model for each lot fits into the larger model for
the whole development, the global system is consistent. There is
no need to ensure consistent definitions for terms that are used
only for local details within the scope of a single lot or house.
4. But that raises the notion of "scope of names". We need a syntactic
mechanism that allows us to define new names for constants, relations,
and types. That means that the ontology for the global KB might be
extended and enriched inside some view (i.e. subdomain).
5. To determine what this suggestion means semantically, consider the
above example. The developer's KB covers a bigger domain, but its
ontology isn't detailed enough to describe all the features of
the construction of individual houses. The KB for each house and
its surrounding lot is a "view". It must be consistent with the
global KB, but not necessarily with the views for neighboring lots.
This example is typical of many kinds of practical problems that are
central to the problems of knowledge sharing. In fact, this scenario
of a land developer who must deal with multiple contractors is very
close to the issues that arise in large projects of any kind.
In conceptual graphs, the context box provides a natural unit of
modularization. It has always been the central mechanism for delimiting
scope of quantifiers, and it has been used as the analog of Kamp's contexts
for delimiting the scope of indexical references. Using the context box
as a mechanism for delimiting the scope of names is analogous to the use
of BEGIN-END blocks in Algol-like languages for delimiting the scope of
declarations. It is quite easy to add such a feature syntactically to
conceptual graphs, and the previous examples suggest a straightforward
method of defining the semantics:
1. The collection of all contexts forms a strict tree in both CGs
and Algol-like languages. Therefore, assign a unique index i to
each context.
2. For each identifier (constant, relation, or type name), concatenate
its name n in the context i in which it was first defined with the
index of the context: n.i therefore represents a globally unique
identifier.
3. Now we can use the globally unique names in a conventional first-order
model with just one set of global individuals and relations. If two
contractors in contexts i and j have different definitions of Widget,
there is no conflict, because the global names Widget.i and Widget.j
are distinct.
A slightly more complicated problem arises if there are multiple ways of
carving up the same physical domain. For example, the town, county, and
state might have different school districts, sewer districts, congressional
districts, etc., which might overlap in conflicting ways:
1. The collection of all contexts still forms a strict tree syntactically,
although different branches of the tree might refer to the same
physical objects in different ways. We can still use the above
method to generate unique names, even though the same physical object
might have different names in different branches of the tree.
2. Instead of trying to form a single global model, we can form multiple
models -- one for each path from the root of the tree down to a leaf.
These path-based models are all conventional first-order models, even
though two different paths might be inconsistent with each other.
3. All paths have a common root, and many paths will share more than one
containing context near the beginning. Objects named in different
paths can only be discussed in a context that is common to both paths.
If something is named in one path, but not the other, it might be
possible to extend the ontology in one of the common contexts.
If not, then it is not possible to discuss the object from both views
at the same time. However, each view can still be consistent with
the model for its own branch.
This scenario is typical of many kinds of practical projects, and a
knowledge representation designed for collaboration and sharing must be
able to accommodate it. I am not claiming that this mechanism solves
all the problems of contexts, but it supports one important class of
problems. We need something like it for those problems.
A similar mechanism in KIF would simplify the mapping from CGs to KIF,
and it would provide an important modularization mechanism that is
necessary for building and sharing large knowledge bases.
John Sowa