Contexts and views (John F. Sowa)
Date: Wed, 31 May 1995 09:43:01 +0500
From: (John F. Sowa)
Message-id: <9505311343.AA01475@west>
Subject: Contexts and views
Content-Length: 8208
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

 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