Manos Theodorakis
and Panos Constantopoulos
Department of Computer Science,
University of Crete
and
Institute of Computer Science,
Foundation for Research and Technology - Hellas
P.O.Box 1385, GR 711 10 Heraklion, Crete, Greece
{etheodor |
panos}@ics.forth.gr
In information bases following semantic and object-oriented data models logical names are used for the external identification of objects. Yet the naming schemes employed are not ``natural'' enough and several problems often arise: logical names can be ambiguous, excessively long, unrelated to or unable to follow the changes of the environment of named object. In natural language, similar problems are resolved by the context within which words are used. An approach to introducing a notion of context in an information base is to provide structuring mechanisms for decomposing it into possibly overlapping parts. This paper focuses on developing a context mechanism for an information base and, in particular, exploiting this mechanism for naming purposes. Rules are developed for generating meaningful names for objects by taking their context into account. This context-based naming enhances name readability, resolves name ambiguities, saves a lot of redundant name substrings, and it localizes and thus facilitates consistency checking, query processing and update operations. In modeling, it supports systematic naming of objects, and thus enhances cooperation between the designers and the end-users in the sense that the contents of the information base are more understandable by both of them.
In natural language, words are used to identify concepts (concrete or abstract) and context is used to essentially enhance the expressiveness of a finite vocabulary. In information bases, in particular those following object-oriented or semantic data models, logical names are used to externally identify objects. Context mechanisms, however, are not offered in general. Introducing context in information bases would enhance expressiveness, understandability and flexibility, and would support cooperative applications, where contextual divisions of the information bases naturally arise.
A general approach to introducing a notion of context in an information base is to provide structuring mechanisms for decomposing it into possibly overlapping parts. This paper focuses on developing a context construct for an information base following an object-oriented semantic data model and, in particular, exploiting this construct for naming purposes.
At the conceptual level, the information base describes objects and relationships between them. The objects are identified by logical names. These names are usually derived from the names of the real world concepts that the objects represent. A variety of problems arise, especially in large databases, such as logical names that are ambiguous, excessively long, unrelated to the environment of the respective objects, or unable to follow the changes of that environment.
An abstract context model for partitioning information bases was proposed and its integration into a powerful object-oriented notation, namely the Telos knowledge representation language [23], was addressed by Mylopoulos and Motschnig-Pitrik [24, 25]. Inspired in large part by that work, as well as by the application requirements of the Semantic Index System [5, 6, 7, 9, 8], in this paper we introduce a context construct for a data model essentially conformant with the structural part of Telos, and we define a context-based naming scheme.
Contexts are defined in a broad sense, in which they may overlap, and in a strict sense, in which they are disjoint. The disjoint strict contexts can be thought of as characterizing the objects they contain in a unique manner, whereas in general an object may be contained in more than one broad contexts. Objects are assigned unique names within their strict contexts. The latter are hierarchically organized, thus enabling the generation of unique path names for all objects in an information base. This scheme implements name relativism not only for relationships, as usual, but also for objects of independent standing. Meaningful object names are generated automatically through the respective contexts. Thus names are dynamic, related with and following the changes of the environment of the objects.
The paper is organized as follows: The next section briefly surveys manifestations of context and naming in different fields. Section 3 reviews the information representation framework and define a refined notion of path, necessary for introducing a versatile path-based name generating scheme. In section 4 the context construct and the context-based naming mechanism are developed. Section 5 addresses some implementation issues and section 6 contains general discussion and conclusions.
In linguistics and cognitive psychology the notion of context plays an important role in language comprehension and generation. People naturally use contextual information in order to convey a specific meaning. Langacker claimed that all linguistic units are context-dependent [20]. One of the basic characteristics of natural language is ambiguity [27]. People frequently employ the same form to convey more than one meanings in everyday speech. This is the case of polysemous words (e.g. the word ``line'' in ``a line of code'' or ``a line in the bank'') and homonyms (e.g. ``bat'' the mammal or ``bat'' the athletic implement). On the other hand, different forms are often used to convey the same meaning (synonyms, e.g. ``cheap'' and ``inexpensive''). These ambiguities are resolved by reference to a specific context. For example, the same meaning can be expressed by different words in the dialects of different cultural or professional groups [18]. Conversely, the same word can be used by different groups to convey different meanings, or even within one group to convey different meanings in different situations.
In artificial languages, the opposite of the previous assumption, that is, one meaning can have only one linguistic representation, is also true. This clearly requires using absolute or global ``names''. An interesting question in artificial language design is how to extend a name by suffixing or prefixing constructs in order to make it unique in a given context or, given a name, how to restrict the context so that this name may convey a unique meaning.
There are several manifestations of context-based naming: in programming languages, the parts of the program which are visible to a particular program segment are determined by the scopes and scope rules using scope resolution operators. More recently, in an object-oriented framework, aspects [28], roles [15, 29, 2] and conceptual slices (views) [30] have been introduced to support multiple state and multiple behavior of the same objects, which is similar to handling the same object in different context or to moving an object into another context.
In traditional databases, views present a consistent partition of the database [14, 3]. Such mechanisms have been adopted in object-oriented databases [1, 22] and semantic data models [11]. In addition, database integration has to deal with naming conflicts of two types, homonyms and synonyms, because the global schema of the integrated database is usually generated by merging one or more user-oriented schemas [4].
In artificial intelligence contexts have been introduced as means of partitioning knowledge into manageable sets [17], or they have been considered as logical constructs that facilitate reasoning activities [21, 16]. Moreover, contexts have been proposed as a partitioning scheme for hypertext databases [12], and perspectives as a mechanism for organizing and manipulating groups of nodes and links in a hypertext network [26]. More recently, general abstractions for partitioning information bases with contexts have been proposed, which address issues of naming conventions, authorization, transaction execution and overlapping contexts [24, 25]. Other approaches employ context as a way to face the complexity of information base update [8], or to develop a naming mechanism for semantic data models [31].
We assume information bases that follow an object-oriented data model conformant with the structural part of the Telos language [23]. This is a generalization of graph-theoretic structures used in semantic networks, semantic data models and object-oriented representations. An information base can be thought of as consisting of nodes and links, with nodes describing objects of independent existence and links representing relationships among such objects. Nodes and links are considered as objects and are organized along three dimensions: classification (instance of), generalization (isA) and attribution. Attributes represent object properties and binary relationships. Attributes of attributes and so on can be defined. Multiple classification is allowed, supporting the separate representation of multiple modeling aspects. Classes of objects within a given instantiation level are also organized in terms of generalization relationships. These can be multiple and give rise to hierarchies that are directed acyclic graphs.
Figure 1: Information base example
An object is associated with two identifiers: a system-generated, globally unique identifier, completely independent of any physical location (a surrogate [10]), which distinguishes it internally from all other objects, and an atomic logical name which accomplishes logical reference to the object and identifies it externally. The logical name of a node is unique over the entire information base, and the logical name of a link is unique among the links emanating from the same object. This results in the naming of the nodes being different from the naming of concepts in the real world. The latter are often named taking into account a specific context.
An example is illustrated in Figure 1, where the information base represents articles and their structure. The nodes are depicted by boxes and the links by directed arrows. The text inside a box or above an arrow corresponds to the atomic logical name, and the text in square brackets to their internal object identifier.
In the next section we define a new naming mechanism for nodes relaxing the unique node name assumption. To do this we introduce a notion of context whereby the information base is partitioned into possibly overlapping conceptual slices. A given node may belong to several contexts. Yet, we assume that one of these contexts can always be selected as more characteristic for a given node in a specific information base, and for naming purposes the node is associated exclusively with that context. Correspondingly, we assume that each of the real-world concepts modeled by nodes can be characterized uniquely by one of the real-world contexts of the domain of discourse.
In the rest of this section we introduce a refined notion of path, that explicitly differentiates between link classes, and corresponding notions of navigation and path names.
We use the symbols 
for the set of objects,
for the set of nodes,
for the set of links ( 
).
It is true that: 
.
We use 
for the set of binary relations (classes of links,
),
and 
for the set of atomic names.
The functions 
and 
give the object which the
link a emanates from and points to, respectively.
The function 
gives the set of instances of class 
.
We use the expression 
(or 
)
to denote that there exists at least (or only) one
link between the nodes x and y (either in the forward or backward
direction, i.e. 
),
which is instance of link class r.
We use the expression 
to denote that link a connects the nodes x and y.
As mentioned earlier, objects can have an atomic name.
The binding of atomic names to objects is determined by the atomic name
function 
.
Thus, for our purposes an information base ( 
) is defined
as a triple: 
.
Accessing information in such an information base often involves navigating from one object to another by following links (in the forward or backward direction) [19]. Navigation relies on the notion of path; It begins at the first node of the path and reaches the last one following links of specific classes and passing through (visiting) specific nodes in a given order. The orientation of links is disregarded, since for every link an inverse one can be defined (e.g. ``a Car includes an Engine'' and ``an Engine is part of a Car'' describe the same real-world situation).
In Figure 1, the path 
denotes the navigation from the article ``CBN'' to the first of its
sections and the path 
denotes the
navigation from the second section to the article it belongs to.
A path can be composed by other paths as follows:
where 
and 
.
The functions Root(p) and Leaf(p) give
the first and the last node of path p, respectively.
In our example 
and 
.
The length ( 
) of a path is
defined as the number of nodes occurring in the path
(e.g. len(p') = 3).
Reaching a node requires either to explicitly specify the
node (by its identifier) or to navigate the information base
through a path leading to that node.
The set of paths reaching a specific node x,
, is defined as follows:
.
For example, in Figure 1 we have:
(instof represents the internal identifier of the instance-of relation).
The communication between user and information base is effected through logical names. Therefore, a path should be referred externally by a logical name. A logical name (or simply name) is defined as a sequence of atomic names that can occur in a database, or that are allowed in a term of a query language. Since the atomic name of a link is unique among the links emanating from the same object, a link is not fully identified externally by its atomic name. Full identification is achieved by extending its atomic name with the name of its from-object. In general, link names can be defined as follows:
The binding of arbitrary link names to links is determined by the link name function.
In our example, 
and
.
A node, on the other hand, can be accessed not only by its atomic name (which is, so far, a unique external identifier), but also by a path. Each path can be denoted externally by a name. The path name is defined as follows:
We suppose, as mentioned before, that for every (forward)
relationship there is an inverse one which represents the same
situation. That is, for each relationship r there exists
the inverse 
with atomic logical name 
.
With this in mind, we define the path name function,
which provides the binding of path names to paths.
For example, in figure 1, we have:
,
,
(note that 
).
Under certain circumstances a path name can characterize and identify a node uniquely. Then, this name can be considered as the external identification of the node. In the next section we define a mechanism which provides the necessary environment (context-based) for uniquely identifying nodes by path names.
We now introduce the notion of context and define a context-based naming scheme. Our aim is to relax the unique node name assumption, so that different nodes can be named with the same atomic name. On the other hand, we have to ensure that there is always a unique external identifier for each object. These are the relative and global names of the object, which are composite and generated by taking into account the context to which the object belongs. Meaningful node names are produced automatically, by using the connections of the object with its environment. Thus names can be frugal and dynamically follow the changes of the environment. Contexts can be considered as conceptual slices of the information base. A node can be contained in more than one contexts, yet we shall make the working hypothesis that a single context can best characterize each node. Thus, in the naming scheme developed here, contexts are considered as disjoint.
We define two element selector functions on contexts: the first
to retrieve the node ( 
) and
the second to retrieve the link class of a context
( 
).
We distinguish the contents of a context into broad contents and
strict contents. Correspondingly, we distinguish contexts into
broad and strict depending on their contents.
Broad contents of a context c = (y,r) consists of
the node y, the link class r (elements of c)
and all the nodes which are connected with the node y with links that
are instances of the link class r and these links (neighbors of c).
They are created by the constructor function brCnts as follows:
Figure 2: An isA hierarchy of weapons and instruments
For example, in Figure 1, consider the contexts:
, which represents the sections of the body of the
article ``CBN'',
, and 
.
The broad contents of those contexts are:
,
and
.
Another example is shown in Figure 2, which
represents an isA hierarchy of weapons and instruments. Consider again
the contexts: 
and 
, which
represent all the specializations of instruments and combat knives,
respectively.
The broad contents of those contexts are:
and
.
Broad contexts are possibly overlapped in a sense that they may have
common neighbors. For example, contexts 
and 
contain
in common the neighbor node 
.
Strict contexts, on the other hand, are disjoint.
Their contents (strCnts) are subset of the corresponding broad contents
and specified by the scope function in a way to avoid overlapping
among their neighbors.
The constructor of strict contents is identical with the constructor
of broad contents except from the definition of 
, which is
defined as follows:
Contexts
are organized in a tree hierarchy in a sense that neighbor nodes
of a context may define other contexts. The root of all
contexts is the information base context, which is defined as:
IBcontext = (individual,instof) and is build in the information base.
Because of the tree hierarchy the scope function can be applied
recursively on a node.
Figure 3: Context and naming: an example
For example, Figure 3 shows the information
base of Figure 1 with a scope function defined
over it and a set of contexts, tabulated on the top of the figure.
By virtue of that table of values
, 
,
.
The strict contents of the context 
are
,
,
.
We can see that contexts and 
have identical strict and
broad contents.
On the contrary, context 
does not have any neighbors.
This is because it has been selected (by the user and
denoted by the scope function) that the node
is better characterized as a figure by the context
than as a figure of section 2 by the context .
The set of fixed points of S in :
,
we call set of individuals.
This means that individuals are fully identified externally by their atomic names.
This axiom is a strict interpretation of our assumption that one of the contexts can always be selected as more characteristic for a given node in an information base.
Figure 4: Context and naming: an example of isA hierachy
The information base of Figure 3
satisfies the axioms of the context-based naming mechanism.
The set of individuals is:
.
These are nodes belonging to the information base context.
On the other hand nodes 
and 
,
which are components of the composite objects 
and
belong to contexts 
and , respectively.
Their atomic names are unique among the nodes contained in these
contexts. This is the reason why the atomic names of these two objects are
much shorter than their counterparts in Figure 1.
Another example is shown in Figures 2 and 4.
Both they describe the same real world situation,
which is an isA hierarchy of weapons and instruments.
The second satisfies the axioms of the context-based naming mechanism.
The filled arrows denote that the to-node is in the
scope of the context defined by the from-node and isA link class.
Comparing Figure 3 with Figure 1
(or Figure 4 with 2)
we observe that in Figure 3 (or 4)
not only the atomic names of the nodes are much shorter than in
Figure 1 (or 2)
but also the same atomic name is used more than once (homonyms).
A straightforward question is ``how could we externally refer to nodes with the same atomic name?''. This can be achieved using the global and relative name of a node, which are names of scope paths. Scope paths denote navigations within contexts and are formally defined as follows:
For example, in Figure 3 we have
and
and in Figure 4:
.
Intuitively, by combining axiom 4.5 with
definition 4.6 it is easy to see that there is a unique way
to navigate from one node to another within contexts
(following scope paths).
For example, in Figure 3, to navigate
from or towards within contexts,
there is a unique way (the scope path 
or
, respectively).
It can be proved that the scope paths of a node are acyclic.
This ensures that contexts are disjoint and organized in a tree hierarchy.
The proofs of all theorems that follow are given in Appendix.
Every scope path is assigned a specific name by the path name function,
called scope name.
The set of all scope names of a specific node x
are defined as follows:
.
The scope names identify the ending nodes of the respective scope
paths uniquely, either over the whole
information base (global names) or with respect to a context (relative
names).
Relative name of a node with respect to a context is defined the name of the scope path which ends at that node and its root node belongs to the neighbors of that context.
For example, in Figure 3 the relative name of
the node with respect to the context is `1',
and denotes the fact that object represents the first
section in the body of article `BCN' and in Figure 4
the relative name of node 
with respect to the context
is `combat.[subclass].oriental'.
For example, in Figure 3 the global name of
the node is its atomic name `CBN', of is
` 
', which represents the body of the article named CBN
and of is ` 
', which
represents the first section of that article.
The global name of node , which belongs to the context 
,
is `Figure.[classof].paths'.
In Figure 4 the global name of node 
is
`weapon.[subclass].attacking' (note that 
),
which represents the class of attacking weapons and of
is `knife.[subclass]. combat. [subclass].oriental', which
represents the oriental combat knives.
A specific context can be externally referred to by its name,
CxtName, defined as follows: 
.
For example, the name of context 
in Figure 3
is 
and the name of context 
in
Figure 4 is
(instrument.[subclass].golf, subclass).
The name of a node (relative or global) is constructed using
the scope of the node and therefore the environment which is
considered more characteristic for it.
Consequently, if the environment changes (by update operations)
the name will change accordingly.
For example, if the atomic name of node
in Figure 3 changes from `CBN' to `new_CBN', the
global names of nodes representing the body, sections and paragraphs
of that article will adapt to that change (e.g. the global name
of node will change to ` 
').
In addition, the way the name is constructed
results in ``meaningful'' names. For example, the global name of node
is: , which refers to
section 1 of article ``CBN'' of the real word.
In terms of a query language, a specific object can
be referred to by a name which is known to the user (for example its
atomic name) and either extend this name or restrict its context in
order to identify it uniquely. For example, the name ``club'' in the
information base of Figure 4 produces a naming conflict
with respect to the information base context.
On the other hand, the same name with respect to the context
(golf,subclass) identifies object 
uniquely.
The same result is obtained if instead of restricting the
context, we extend the name to ``golf.[subclass].club''.
Figure 5: Implementation: necessary structures
Our mechanism can be easily incorporated into a structurally object-oriented information base system. The only extra requirements are to save the scope function information and to check the necessary integrity constraints. This can be easily achieved by extending the structure which saves the atomic name function (L) so as to capture contextual information. Suppose that the atomic name function is implemented by a table, called symbol table, comprising two columns: the first for the internal identification of an object and the second for its atomic name (see Figure 5(a)). For each object a row is created in the symbol table and saves the internal identifier and the atomic name of that object (each row represents a specific relationship of the atomic name function). For the purposes of the context-based naming mechanism this structure can be extended to the structure shown in Figure 5(b).
Another implementation approach for context-based naming is to create a different symbol table for each context consisting of the contents of that context and their atomic names.
The first approach is easy implemented but requires some extra time to compute the name of an object or to access an object identified by a path name, because it has to look up the whole symbol table. On the other hand the second approach needs some extra structures to be implemented and requires extra memory and address space to save the different local symbol tables but it localizes and thus facilitates consistency checking, query processing and update operations.
To validate our mechanism, we have started a prototype implementation within the Semantic Index System (SIS) based on the first approach. The SIS [6, 7] is a system for the management of very large collections of highly interrelated information objects with evolving structures. The SIS data model follows the structural part of the Telos knowledge representation language [23].
The objective of this paper was to deal with the question of naming in information bases, where several problems appear: ambiguous logical names, excessively long and difficult to handle, unrelated to the environment of the named object, or unable to follow changes of that environment. As a solution to this problem, we proposed a context-based naming mechanism.
Our approach in a sense simulates naming in natural language: a notion of context is supported and objects can be identified externally by using logical names with respect to a specific context (relative names). This results in the use of polysemous and homonymous names, which is common in natural language. Names are generated dynamically by taking into account the context of the corresponding object. Moreover, the generated names are meaningful, which contributes to the quality of a limited natural language generation, useful for developing hypermedia applications over information bases [9], and data entry facilitation. Object identification techniques like extending a name in a specific context or restricting the context of a specific name are also supported. All these contribute important quality factors to modeling, like simplicity, flexibility and expressiveness. The capability of using relative names ensures the frugality of atomic names thus saving a lot of redundant name substrings. Our experience from large modeling applications indicates that as many as 60% of the names in some applications (such as the CLIO cultural documentation system [5]) can be redundant. In addition, the unnamed objects can be exploited by higher level update operations which facilitate the interactive creation of composite objects [8, 32].
The names, on the other hand, are composite and can be extended or restricted dynamically in order to identify the desired object uniquely. Moreover, they are consistent with the environment of the named object. This minimizes the maintainance cost of names, because names follow the updates (renaming, deletion, changing from one context to another, etc.) of the information base, which is very important for evolutionary applications. It also enhances the visibility and readability of the names making them more understandable to the users. This is important for the development of interactive applications. In addition, the use of atomic, relative or global names enhances query expressiveness, since both the formulation and the results of a query can include atomic, relative or global names.
An important feature of this mechanism is that it can be easily incorporated into an information bases system. The only extra requirements are to save the scope function information and to check the necessary integrity constraints. Moreover, the absence of redundant name substrings facilitates string matching algorithms to be performed more efficiently. The price is some extra time to compute the name of an object or to access an object identified by a path name. We can cope with this problem by using a local symbol table (interpretation of atomic name function) for the contents of each context. This localizes and facilitates consistency checking, query processing and update operations.
For modeling purposes the context-based naming mechanism is suitable for representing composite objects and managing complex conceptual structures found in many advanced applications such as scientific catalogs, CAD, manufacturing and software development. It is also useful for terminological bases, which are usually huge and exhibit a lot of naming ambiguities, and for evolutionary applications.
Future research includes dealing with conjunctive contexts (a node can be characterized in conjunction by more than one contexts) and disjunctive contexts (a node can be characterized by one of several contexts) relaxing the assumption that a node belongs to only one context. Disjunctive contexts will generate names which are synonyms for a given node. Also, overlapping contexts and intercontext communication need attention.
We would like to thank Anastasia Analyti for carefully reading the paper and for her valuable comments, Martin Dörr for many stimulating conversations on the subject, and Yannis Tzitzikas and Polivios Klimathianakis for their contribution to this work. We would like also to thank the anonymous referees for their helpful comments.
Definition A.1 Path composition.
The composition between paths is defined as follows:
Definition A.2 Path equality.
We define the equation between two paths as follows:
Definition A.3 Length of a path.
The length of a path is the number of nodes
occurring in the path ( ).
The composition, length and equality of names
are defined like those of paths. The composition operator for names
is the symbol 
and the following identity is true:
.
Clearly, 
and 
is closed under the composition operator,
and the operator itself is associative, that is:
.
Associativity allows us to omit an indication of precedence in
expressions with more than one instance of the operator.
The following identities on len is also a
straightforward consequence of our definitions:
and
.
Proof of Theorem 4.1
Assume, to the contrary, that
.
Then we have \
.
Similarly, we prove that 
and so on.
That is, \
.
By the previous equation it is clear that
This is in contrast with Axiom 4.2, which
implies that all the nodes in a finite number of recursive steps
belongs to information base context. 
Proof of Theorem 4.2
)
.
Since RelN(x,c) = RelN(y,c), we have
.
By definition 4.7,
and 
,
we have
Since RelN(x,c) = RelN(y,c) the previous equations imply that
By definition of relative name and equation (1) we have:
We can go on similarly to prove that
The previous equation is true for i = 1, that is, 
.
Equation (1) and ax.4.4
imply that x = y.
Hence our original assumption that 
must be false.
)
.
The fact that the S is a function combining with the
Axiom 4.5 implies that
Hence, our original assumption that
must be false.
Manos Theodorakis
