Unifying Class-Based Representation Formalisms

D. Calvanese, M. Lenzerini and D. Nardi

Volume 11, 1999

Links to Full Text:

Abstract:
The notion of class is ubiquitous in computer science and is central in many formalisms for the representation of structured knowledge used both in knowledge representation and in databases. In this paper we study the basic issues underlying such representation formalisms and single out both their common characteristics and their distinguishing features. Such investigation leads us to propose a unifying framework in which we are able to capture the fundamental aspects of several representation languages used in different contexts. The proposed formalism is expressed in the style of description logics, which have been introduced in knowledge representation as a means to provide a semantically well-founded basis for the structural aspects of knowledge representation systems. The description logic considered in this paper is a subset of first order logic with nice computational characteristics. It is quite expressive and features a novel combination of constructs that has not been studied before. The distinguishing constructs are number restrictions, which generalize existence and functional dependencies, inverse roles, which allow one to refer to the inverse of a relationship, and possibly cyclic assertions, which are necessary for capturing real world domains. We are able to show that it is precisely such combination of constructs that makes our logic powerful enough to model the essential set of features for defining class structures that are common to frame systems, object-oriented database languages, and semantic data models. As a consequence of the established correspondences, several significant extensions of each of the above formalisms become available. The high expressiveness of the logic we propose and the need for capturing the reasoning in different contexts forces us to distinguish between unrestricted and finite model reasoning. A notable feature of our proposal is that reasoning in both cases is decidable. We argue that, by virtue of the high expressive power and of the associated reasoning capabilities on both unrestricted and finite models, our logic provides a common core for class-based representation formalisms.

Extracted Text


Journal of Artificial Intelligence Research 11 (1999) 199-240 Submitted 7/98;
published 9/99

Unifying Class-Based Representation Formalisms Diego Calvanese calvanese@dis.uniroma1.it
Maurizio Lenzerini lenzerini@dis.uniroma1.it Daniele Nardi nardi@dis.uniroma1.it
Dipartimento di Informatica e Sistemistica Universit`a di Roma "La Sapienza"
Via Salaria 113, I-00198 Roma, Italy

Abstract The notion of class is ubiquitous in computer science and is central
in many formalisms for the representation of structured knowledge used both
in knowledge representation and in databases. In this paper we study the
basic issues underlying such representation formalisms and single out both
their common characteristics and their distinguishing features. Such investigation
leads us to propose a unifying framework in which we are able to capture
the fundamental aspects of several representation languages used in different
contexts. The proposed formalism is expressed in the style of description
logics, which have been introduced in knowledge representation as a means
to provide a semantically well-founded basis for the structural aspects of
knowledge representation systems. The description logic considered in this
paper is a subset of first order logic with nice computational characteristics.
It is quite expressive and features a novel combination of constructs that
has not been studied before. The distinguishing constructs are number restrictions,
which generalize existence and functional dependencies, inverse roles, which
allow one to refer to the inverse of a relationship, and possibly cyclic
assertions, which are necessary for capturing real world domains. We are
able to show that it is precisely such combination of constructs that makes
our logic powerful enough to model the essential set of features for defining
class structures that are common to frame systems, object-oriented database
languages, and semantic data models. As a consequence of the established
correspondences, several significant extensions of each of the above formalisms
become available. The high expressiveness of the logic we propose and the
need for capturing the reasoning in different contexts forces us to distinguish
between unrestricted and finite model reasoning. A notable feature of our
proposal is that reasoning in both cases is decidable. We argue that, by
virtue of the high expressive power and of the associated reasoning capabilities
on both unrestricted and finite models, our logic provides a common core
for class-based representation formalisms.

1. Introduction In many fields of computer science we find formalisms for
the representation of objects and classes (Motschnig-Pitrik & Mylopoulous,
1992). Generally speaking, an object denotes an element of the domain of
interest, and a class denotes a set of objects with common characteristics.
We use the term "class-based representation formalism" to refer to a formalism
that allows one to express several kinds of relationships and constraints
(e.g., subclass constraints) holding among the classes that are meaningful
in a set of applications. Moreover, class-based formalisms aim at taking
advantage of the class structure in order to provide various information,
such as whether a class is consistent, i.e., it admits at least one object,
whether a class is a subclass of another class, and more generally, whether
a given constraint

cfl1999 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.

Calvanese, Lenzerini, & Nardi holds between a given set of classes. From
the above characterization, it should be clear that the formalisms referred
to in this paper deal only with the structural aspects of objects and classes,
and do not include any features for the specification of behavioral properties
of objects.

Three main families of class-based formalisms are identified in this paper.
The first one comes from knowledge representation and in particular from
the work on semantic networks and frames (see for example Lehmann, 1992;
Sowa, 1991). The second one originates in the field of databases and in particular
from the work on semantic data models (see for example Hull & King, 1987).
The third one arises from the work on types in programming languages and
object-oriented systems (see for example Kim & Lochovsky, 1989).

In the past there have been several attempts to establish relationships among
the various families of class-based formalisms (see Section 6 for a brief
survey). The proposed solutions are not fully general and a formalism capturing
both the modeling constructs and the reasoning techniques for all the above
families is still missing. In this paper we address this problem by proposing
a class-based representation formalism, based on description logics (Brachman
& Levesque, 1984; Schmidt-Schauss & Smolka, 1991; Donini, Lenzerini, Nardi,
& Schaerf, 1996), and by using it for comparing other formalisms.

In description logics, structured knowledge is described by means of so called
concepts and roles, which denote unary and binary predicates, respectively.
Starting from a set of atomic symbols one can build complex concept and role
expressions by applying suitable constructors which characterize a description
logic. Formally, concepts are interpreted as subsets of a domain and roles
as binary relations over that domain, and all constructs are equipped with
a precise set-theoretic semantics. The most common constructs include boolean
operations on concepts, and quantification over roles. For example, the concept
Person u 8child.Male, denotes the set of individuals that are instances of
the concept Person and are connected through the role child only to instances
of the concept Male, while the concept 9child denotes all individuals that
are connected through the role child to some individual. Further constructs
that have been considered important include more general forms of quantification,
number restrictions, which allow one to state limits on the number of connections
that an individual may have via a certain role, and constructs on roles,
such as intersection, concatenation and inverse. A description logic knowledge
base, expressing the intensional knowledge about the modeled domain, is built
by stating inclusion assertions between concepts, which have to be satisfied
by the models of the knowledge base. The assertions are used to specify necessary
and/or necessary and sufficient conditions for individuals to be instances
of certain concepts. Reasoning on such knowledge bases includes the detection
of inconsistencies in the knowledge base itself, determining whether a concept
can be populated in a model of the knowledge base, and checking subsumption,
i.e., whether all instances of a concept are necessarily also instances of
another concept in all models of the knowledge base.

In this paper we propose a description logic called aluni, which is quite
expressive and includes a novel combination of constructs, including number
restrictions, inverse roles, and inclusion assertions with no restrictions
on cycles. Such features make aluni powerful enough to provide a unified
framework for frame systems, object-oriented languages, and semantic data
models. We show this by establishing a precise correspondence with a framebased
language in the style of the one proposed by Fikes and Kehler (1985), with
the

200

Unifying Class-Based Representation Formalisms Entity-Relationship model
(Chen, 1976), and with an object-oriented language in the style of the one
introduced by Abiteboul and Kanellakis (1989). More specifically, we identify
the most relevant features to model classes in each of the cited settings
and show that a specification in any of those class-based formalisms can
be equivalently expressed as a knowledge base in aluni. In this way, we are
able to identify which are the commonalities among the families and which
are the specificities of each family. Therefore, even though there are specific
features of every family that are not addressed by aluni, we are able to
show that the formalism proposed in this paper provides important features
that are currently missing in each family, although their relevance has often
been stressed. In this sense, our unifying framework points out possible
developments for the languages belonging to all the three families.

One fundamental reason for regarding aluni as a unifying framework for class-based
representation formalisms is that reasoning in aluni is hard, but nonetheless
decidable, as shown by Calvanese, Lenzerini, and Nardi (1994), Calvanese
(1996c). Consequently, the language features arising from different frameworks
to build class-based representations are not just given a common semantic
account, but are combined in a more expressive setting where one retains
the capability of solving reasoning tasks. The combination of constructs
included in the language makes it necessary to distinguish between reasoning
with respect to finite models, i.e., models with a finite domain, and reasoning
with respect to unrestricted models. Calvanese (1996c) devises suitable techniques
for both unrestricted and finite model reasoning, that enable for reasoning
in the different contexts arising from assuming a finite domain, as it is
often the case in the field of databases, or assuming that a domain can also
be infinite. In the paper, we discuss the results on reasoning in aluni,
and compare them with other results on reasoning in class-based representation
formalisms.

Summarizing, our framework provides an adequate expressive power to account
for the most significant features of the major families of class-based formalisms.
Moreover, it is equipped with suitable techniques for reasoning in both finite
and unrestricted models. Therefore, we believe that aluni captures the essential
core of the class-based representation formalisms belonging to all three
families mentioned above.

The paper is organized as follows. In the next section we present our formalism
and in Sections 3, 4, and 5 we discuss three families of class-based formalisms,
namely, frame languages, semantic data models, and object-oriented data models,
showing that their basic features are captured by knowledge bases in aluni.
The final sections contain a review of related work, including a discussion
of reasoning in aluni and class-based formalism, and some concluding remarks.

2. A Unifying Class-Based Representation Language In this section, we present
aluni, a class-based formalism in the style of description logics (DLs) (Brachman
& Levesque, 1984; Schmidt-Schauss & Smolka, 1991; Donini et al., 1996; Donini,
Lenzerini, Nardi, & Nutt, 1997). In DLs the domain of interest is modeled
by means of concepts and roles, which denote classes and binary relations,
respectively. Generally speaking, a DL is formed by three basic components:

ffl A description language, which specifies how to construct complex concept
and role

expressions (also called simply concepts and roles), by starting from a set
of atomic

201

Calvanese, Lenzerini, & Nardi Construct Syntax Semantics atomic concept A
AI ` Delta I atomic negation :A Delta I n AI conjunction C1 u C2 CI1 "
CI2 disjunction C1 t C2 CI1 [ CI2 universal quantification 8R.C fo j 8o0
. (o; o0) 2 RI ! o0 2 CIg number restrictions 9*nR fo j ]fo0 j (o; o0) 2
RIg * ng1

9^nR fo j ]fo0 j (o; o0) 2 RIg ^ ng

atomic role P P I ` Delta I Theta  Delta I inverse role P Gamma  f(o;
o0) j (o0; o) 2 P Ig

Table 1: Syntax and semantics of ALU N I

symbols and by applying suitable constructors. It is the set of allowed constructs
that characterizes the description language.

ffl A knowledge specification mechanism, which specifies how to construct
a DL knowledge base, in which properties of concepts and roles are asserted.

ffl A set of basic reasoning tasks provided by the DL. In the rest of the
section we describe the specific form that these three components assume
in aluni.

2.1 The Description Language of aluni In the description language of aluni,
called ALUN I, concepts and roles are formed according to the syntax shown
in Table 1, where A denotes an atomic concept, P an atomic role, C an arbitrary
concept expression, R an arbitrary role expression, and n a nonnegative integer.
To increase readability of concept expressions, we also introduce the following
abbreviations:

? j A t :A; for some atomic concept A ? j A u :A; for some atomic concept
A 9R j 9*1R 9=nR j 9^nR u 9*nR

Concepts are interpreted as subsets of a domain and roles as binary relations
over that domain. Intuitively, :A represents the negation of an atomic concept,
and is interpreted as the complement with respect to the domain of interpretation.
C1 u C2 represents the conjunction of two concepts and is interpreted as
set intersection, while C1 t C2 represents disjunction and is interpreted
as set union. Consequently, ? represents the whole domain,

1. ]S denotes the cardinality of a set S.

202

Unifying Class-Based Representation Formalisms and ? the empty set. 8R.C
is called universal quantification over roles and is used to denote those
elements of the interpretation domain that are connected through role R only
to instances of the concept C. 9*nR and 9^nR are called number restrictions,
and impose on their instances restrictions on the minimum and maximum number
of objects they are connected to through role R. P Gamma , called the inverse
of role P , represents the inverse of the binary relation denoted by P .

More formally, an interpretation I = (Delta I; Delta I ) consists of an
interpretation domain Delta I and an interpretation function Delta I that
maps every concept C to a subset CI of Delta I and every role R to a subset
RI of Delta I Theta  Delta I according to the semantic rules specified
in Table 1. The sets CI and RI are called the extensions of C and R respectively.

Example 2.1 Consider the concept expression

8enrolls.Student u 9*2enrolls u 9^30enrolls u 8teachesGamma .(Professor
t GradStudent) u 9=1teachesGamma  u :AdvCourse

specifying the constraints for an object to be a university course. The expression
reflects the fact that each course enrolls only students, and restrictions
on the minimum and maximum number of enrolled students. By using the role
teaches and the inverse constructor we can state the property that each course
is taught by exactly one individual, who is either a professor or a graduate
student. Finally, negation is used to express disjointness from the concept
denoting advanced courses.

2.2 Knowledge Bases in aluni An aluni knowledge base, which expresses the
knowledge about classes and relations of the modeled domain, is formally
defined as a triple K = (A; P; T ), where A is a finite set of atomic concepts,
P is a finite set of atomic roles, and T is a finite set of so called inclusion
assertions. Each such assertion has the form

A ._ C where A is an atomic concept and C an arbitrary concept expression.
Such an inclusion assertion states by means of the concept C necessary properties
for an element of the domain in order to be an instance of the atomic concept
A. Formally, an interpretation I satisfies the inclusion assertion A ._ C
if AI ` CI . An interpretation I is a model of a knowledge base K if it satisfies
all inclusion assertions in K. A finite model is a model with finite domain.

Example 2.1 (cont.) The assertion

Course ._ 8enrolls.Student u 9*2enrolls u 9^30enrolls u

8teachesGamma .(Professor t GradStudent) u 9=1teachesGamma 

makes use of a complex concept expression to state necessary conditions for
an object to be an instance of the concept Course.

203

Calvanese, Lenzerini, & Nardi In aluni no restrictions are imposed on the
form that the inclusion assertions may assume. In particular we do not rule
out cyclic assertions, i.e., assertions in which the concept expression on
the right hand side refers, either directly or indirectly via other assertions,
to the atomic concept on the left hand side. In the presence of cyclic assertions
different semantics may be adopted (Nebel, 1991). The one defined above,
called descriptive semantics, accepts all interpretations that satisfy the
assertions in the knowledge base, and hence interprets assertions as constraints
on the domain to be modeled. For inclusion assertions, descriptive semantics
has been claimed to provide the most intuitive results (Buchheit, Donini,
Nutt, & Schaerf, 1998). Alternative semantics which have been proposed are
based on fixpoint constructions (Nebel, 1991; Schild, 1994; De Giacomo &
Lenzerini, 1994b), and hence allow to define in a unique way the interpretation
of concepts.

In general, cycles in the knowledge base increase the complexity of reasoning
(Nebel, 1991; Baader, 1996; Calvanese, 1996b) and require a special treatment
by reasoning procedures (Baader, 1991; Buchheit, Donini, & Schaerf, 1993).
For this reason, many DL based systems assume the knowledge base to be acyclic
(Brachman, McGuinness, Patel-Schneider, Alperin Resnick, & Borgida, 1991;
Bresciani, Franconi, & Tessaris, 1995). However, this assumption is unrealistic
in practice, and cycles are definitely necessary for a correct modeling in
many application domains. Indeed, the use of cycles is allowed in all data
models used in databases, and, as shown in the following sections, in order
to capture their semantics in aluni the possibility of using cyclic assertions
is fundamental.

Besides inclusion assertions, some DL based systems also make use of equivalence
assertions (Buchheit et al., 1993), which express both necessary and sufficient
conditions for an object to be an instance of a concept. Although this possibility
is ruled out in aluni, this does not limit its ability of capturing both
frame based systems and database models, where the constraints that can be
expressed correspond naturally to inclusion assertions.

2.3 Reasoning in aluni The basic tasks we consider when reasoning over an
aluni knowledge base are concept consistency and concept subsumption:

ffl Concept consistency is the problem of deciding whether a concept C is
consistent in

a knowledge base K (written as K 6j= C _ ?), i.e., whether K admits a model
I such that CI 6= ;.

ffl Concept subsumption is the problem of deciding whether a concept C1 is
subsumed by

a concept C2 in a knowledge base K (written as K j= C1 _ C2), i.e., whether
CI1 ` CI2 for each model I of K.

The inclusion of number restrictions and inverse roles in ALUN I and the
ability in aluni of using arbitrary, possibly cyclic inclusion assertions
allows one to construct a knowledge base in which a certain concept is consistent
but has necessarily an empty extension in all finite models of the knowledge
base. Similarly, a subsumption relation between two concepts may hold only
if infinite models of the knowledge base are ruled out and only finite models
are considered.

204

Unifying Class-Based Representation Formalisms Keven = (A; P; T ), where

A = fNumber; Eveng, P = fdoublesg, and the set T of assertions consists of:

Number ._ 9doubles

Gamma  u 8doublesGamma .Even

Even ._ Number u 9^1doubles u 8doubles.Number

Figure 1: An aluni knowledge base with two concepts that are equivalent in
all finite

models

Example 2.2 Let Keven be the knowledge base shown in Figure 1. Intuitively,
the assertions in Keven state that for each number there is an even number
which doubles it, and that all numbers which double it are even. Each even
number is a number, doubles at most one number, and doubles only numbers.
Observe that for any model I of Keven, the universal quantifications together
with the functionality of doubles in the assertions imply that ]EvenI * ]NumberI,
while the direct inclusion assertion between Even and Number implies that
]EvenI ^ ]NumberI. Therefore, the two concepts have the same cardinality,
and since one is a sub-concept of the other, if the domain is finite, their
extensions coincide. This does not necessarily hold for infinite domains.
In fact, the names we have chosen suggest already an infinite model of the
knowledge base in which Number and Even are interpreted differently. The
model is obtained by taking the natural numbers as domain, and interpreting
Number as the whole domain, Even as the even numbers, and doubles as the
set f(2n; n) j n * 0g.

The example above shows that aluni does not have the finite model property,
which states that if a concept is consistent in a knowledge base then the
knowledge base admits a finite model in which the concept has a nonempty
extension. Therefore, it is important to distinguish between reasoning with
respect to unrestricted models and reasoning with respect to finite models.
We call (unrestricted) concept consistency (written as K 6j=u C _ ?) and
(unrestricted) concept subsumption (written as K j=u A _ C) the reasoning
tasks as described above, i.e., carried out without restricting the attention
to finite models. The corresponding reasoning tasks carried out by considering
finite models only, are called finite concept consistency (written as K 6j=f
C _ ?) and finite concept subsumption (written as K j=f A _ C).

Example 2.2 (cont.) Summing up the previous considerations, we can say that
Number is not subsumed by Even in Keven , i.e., Keven 6j=u Number _ Even,
but is finitely subsumed, i.e., Keven j=f Number _ Even. Equivalently Numberu:Even
is consistent in Keven, i.e., Keven 6j=u Numberu:Even _ ?, but is not finitely
consistent, i.e., Keven j=f Numberu:Even _ ?.

A distinguishing feature of aluni is that reasoning both in the finite and
in the unrestricted case is decidable. In particular, unrestricted concept
satisfiability and concept subsumption are decidable in deterministic exponential
time (De Giacomo & Lenzerini,

205

Calvanese, Lenzerini, & Nardi 1994a; Calvanese et al., 1994), and since reasoning
in strict sublanguages of aluni is already EXPTIME-hard (Calvanese, 1996c),
the known algorithms are computationally optimal. Finite concept consistency
in aluni is also decidable in deterministic exponential time while finite
concept subsumption (in the general case) is decidable in deterministic double
exponential time (Calvanese, 1996c). A more precise discussion on the methods
for reasoning in aluni is provided in Section 6.2, while a detailed account
of the adopted algorithms and an analysis of their computational complexity
is presented by Calvanese (1996c).

In the next sections we show how the two forms of reasoning with respect
to unrestricted and finite models, capture the reasoning tasks that are typically
considered in different formalisms for the structured representation of knowledge.

3. Frame Based Systems Frame languages are based on the idea of expressing
knowledge by means of frames, which are structures representing classes of
objects in terms of the properties that their instances must satisfy. Such
properties are defined by the frame slots, that constitute the items of a
frame definition. Since the 70s a large number of frame systems have been
developed, with different goals and different features. DLs bear a close
relationship with the kl-one family of frame systems (Woods & Schmolze, 1992).
However, here we would like to consider frame systems from a more general
perspective, as discussed for example by Karp (1992), Karp, Myers, and Gruber
(1995), and establish the correspondence with aluni knowledge bases in this
context.

We remark that we are restricting our attention to those aspects that are
related to the taxonomic structure. Moreover, as discussed below, we consider
assertional knowledge bases, where intensional knowledge is characterized
in terms of inclusion assertions rather than definitions. In addition, we
do not consider those features that cannot be captured in a first-order framework,
such as default values in the slots, attached procedures, and the specification
of overriding inheritance policies. Some of the issues concerning the modeling
of these aspects in DLs are addressed by Donini, Lenzerini, Nardi, Nutt,
and Schaerf (1994), Donini, Nardi, and Rosati (1995), within a modal nonmonotonic
extension of DLs.

3.1 Syntax of Frame Based Systems To make the correspondence precise, we
need to fix syntax and semantics for the frame systems we consider. Unfortunately,
there is no accepted standard and we have chosen to use here basically the
notation adopted by Fikes and Kehler (1985), which is used also in the KEE2
system.

Definition 3.1 A frame knowledge base, denoted by F , is formed by a set
of frame and slot names, and is constituted by a set of frame definitions
of the following form:

Frame : F in KB F E; 2. KEE is a trademark of Intellicorp. Note that a KEE
user does not directly specify her knowledge base

in this notation, but is allowed to define frames interactively via the graphical
system interface.

206

Unifying Class-Based Representation Formalisms Frame: Course in KB University

MemberSlot: enrolls

ValueClass: Student Cardinality.Min: 2 Cardinality.Max: 30 MemberSlot: taughtby

ValueClass: (UNION GradStudent

Professor) Cardinality.Min: 1 Cardinality.Max: 1

Frame: AdvCourse in KB University

SuperClasses: Course MemberSlot: enrolls

ValueClass: (INTERSECTION

GradStudent (NOT Undergrad)) Cardinality.Max: 20

Frame: BasCourse in KB University

SuperClasses: Course MemberSlot: taughtby

ValueClass: Professor

Frame: Professor in KB University Frame: Student in KB University Frame:
GradStudent in KB University

SuperClasses: Student MemberSlot: degree

ValueClass: String Cardinality.Min: 1 Cardinality.Max: 1

Frame: Undergrad in KB University

SuperClasses: Student

Figure 2: A KEE knowledge base where E is a frame expression, i.e., an expression
formed according to the following syntax:

E Gamma ! SuperClasses : F1; : : : ; Fh

MemberSlot : S1

ValueClass : H1 Cardinality.Min : m1 Cardinality.Max : n1 Delta  Delta
Delta  MemberSlot : Sk

ValueClass : Hk Cardinality.Min : mk Cardinality.Max : nk

F and S denote frame and slot names, respectively, m and n denote positive
integers, and H denotes slot constraint, which can be specified as follows:

H Gamma ! F j

(INTERSECTION H1 H2) j (UNION H1 H2) j (NOT H)

For readers that are familiar with the KEE system, we point out that we omit
the specification of the sub-classes for a frame present in KEE, since it
can be directly derived from the specification of the super-classes.

Example 3.2 Figure 2 shows a simple example of a knowledge base modeling
the situation at an university expressed in the frame language we have presented.
The frame Course

207

Calvanese, Lenzerini, & Nardi represents courses which enroll students and
are taught either by graduate students or professors. Cardinality restrictions
are used to impose a minimum and maximum number of students that may be enrolled
in a course, and to express that each course is taught by exactly one individual.
The frame AdvCourse represents courses which enroll only graduate students,
i.e., students who already have a degree. Basic courses, on the other hand,
may be taught only by professors.

3.2 Semantics of Frame Based Systems To give semantics to a set of frame
definitions we resort to their interpretation in terms of first-order predicate
calculus (Hayes, 1979). According to such interpretation, frame names are
treated as unary predicates, while slots are considered binary predicates.

A frame expression E is interpreted as a predicate logic formula E(x), which
has one free variable, and consists of the conjunction of sentences, obtained
from the super-class specification and from each slot specification. In particular,
for the super-classes F1; : : : ; Fh we have:

F1(x) ^ : : : ^ Fh(x)

and for a slot specification

MemberSlot : S

ValueClass : H Cardinality.Min : m Cardinality.Max : n

we have 8

y. (S(x; y) ! H(y)) ^

9y1; : : : ; ym. ((Vi6=j yi 6= yj) ^ S(x; y1) ^ Delta  Delta  Delta  ^
S(x; ym)) ^ 8y1; : : : ; yn+1. ((S(x; y1) ^ Delta  Delta  Delta  ^ S(x;
yn+1)) ! Wi6=j yi = yj);

under the assumption that within one frame definition the occurrences of
x refer to the same free variable. Finally the constraints on the slots are
interpreted as conjunction, disjunction and negation, respectively, i.e.:

(INTERSECTION H1 H2) is interpreted as H1(x) ^ H2(x) (UNION H1 H2) is interpreted
as H1(x) . H2(x) (NOT H) is interpreted as :H(x)

A frame definition

Frame : F in KB F E

is then considered as the universally quantified sentence of the form

8x.(F (x) ! E(x)): The whole frame knowledge base F is considered as the
conjunction of all first-order sentences corresponding to the frame definitions
in F .

Here we regard frame definitions as necessary conditions, which is commonplace
in the frame systems known as assertional frame systems, as opposed to definitional
systems, where frame definitions are interpreted as necessary and sufficient
conditions.

208

Unifying Class-Based Representation Formalisms In order to enable the comparison
with our formalisms for representing structured knowledge we restrict our
attention to the reasoning tasks that involve the frame knowledge base, independently
of the assertional knowledge, i.e., the frames instances. Fikes and Kehler
(1985) mention several reasoning services associated with frames, such as:

ffl Consistency checking, which amounts to verifying whether a frame F is
satisfiable

in a knowledge base. In particular, this involves both reasoning on cardinalities
and checking whether the filler of a given slot belongs to a certain frame.

ffl Inheritance, which, in our case, amounts to the ability of identifying
which of the

frames are more general than a given frame, sometimes called all-super-of
(Karp et al., 1995). All the properties of the more general frames are then
inherited by the more specific one. Such a reasoning is therefore based on
the more general ability to check the mutual relationhips between frame descriptions
in the knowledge base.

These reasoning services are formalized in the first-order semantics as follows.
Definition 3.3 Let F be a frame knowledge base and F a frame in F . We say
that F is consistent in F if the first-order sentence F ^ 9x.F (x) is satisfiable.
Moreover, we say that a frame description E is more general than F in F if
F j= 8x.(F (x) ! E(x)).

3.3 Relationship between Frame Based Systems and aluni The first-order semantics
given above allows us to establish a straightforward relationship between
frame languages and aluni. Indeed, we now present a translation from frame
knowledge bases to aluni knowledge bases.

We first define the function ` that maps each frame expression into an ALUN
I concept expression as follows:

ffl Every frame name F is mapped into an atomic concept `(F ). ffl Every
slot name S is mapped into an atomic role `(S). ffl Every slot constraint
is mapped as follows

(UNION H1 H2) is mapped into `(H1) t `(H2): (INTERSECTION H1 H2) is mapped
into `(H1) u `(H2): (NOT H) is mapped into :`(H):

ffl Every frame expression of the form

SuperClasses : F1; : : : ; Fh MemberSlot : S1

ValueClass : H1 Cardinality.Min : m1 Cardinality.Max : n1 Delta  Delta
Delta  MemberSlot : Sk

ValueClass : Hk Cardinality.Min : mk Cardinality.Max : nk

209

Calvanese, Lenzerini, & Nardi K = (A; P; T ), where

A = fCourse; AdvCourse; BasCourse; Professor; Student; GradStudent; Undergrad;
Stringg, P = fenrolls; taughtby; degreeg, and the set T of assertions consists
of:

Course ._ 8enrolls.Student u 9*2enrolls u 9^30enrolls u

8taughtby.(Professor t GradStudent) u 9=1taughtby

AdvCourse ._ Course u 8enrolls.(GradStudent u :Undergrad) u 9^20enrolls BasCourse
._ Course u 8taughtby.Professor GradStudent ._ Student u 8degree.String u
9=1degree

Undergrad ._ Student

Figure 3: The aluni knowledge base corresponding to the KEE knowledge base
in Figure 2

is mapped into the class expression

`(F1) u Delta  Delta  Delta  u `(Fh) u 8`(S1).`(H1) u 9*m1 `(S1) u 9^n1
`(S1) u Delta  Delta  Delta  8`(Sk).`(Hk) u 9*mk `(Sk) u 9^nk `(Sk):

This mapping allows us to translate a frame knowledge base into an aluni
knowledge base, as specified in the following definition.

Definition 3.4 The aluni knowledge base `(F) = (A; P; T ) corresponding to
a frame knowledge base F is obtained as follows:

ffl A consists of one atomic concept `(F ) for each frame name F in F . ffl
P consists of one atomic role `(S) for each slot name S in F . ffl T consists
of an inclusion assertion

`(F ) ._ `(E) for each frame definition

Frame : F in KB F E

in F.

Example 3.2 (cont.) We illustrate the translation on the frame knowledge
base in Figure 2. The corresponding aluni knowledge base is shown in Figure
3.

210

Unifying Class-Based Representation Formalisms The correctness of the translation
follows from the correspondence between the settheoretic semantics of aluni
and the first-order interpretation of frames (see for example Hayes, 1979;
Borgida, 1996; Donini et al., 1996). We can observe that inverse roles are
in fact not necessary for the formalization of frames. Indeed, the possibility
of referring to the inverse of a slot has been rarely considered in frame
knowledge representation systems (Some exceptions are reported in Karp, 1992).
Due to the absence of inverse roles the distinction between reasoning in
finite and unrestricted models is not necessary3. Consequently, all the above
mentioned forms of reasoning are captured by unrestricted concept consistency
and concept subsumption in aluni knowledge bases. This is summarized in the
following theorem.

Theorem 3.5 Let F be a frame knowledge-base, F be a frame in F , E be a frame
description, and `(F), `(F ), and `(E) be their translations in aluni. Then
the following hold:

ffl F is consistent in F if and only if `(F ) 6j=u `(F ) _ ?. ffl E is more
general than F in F if and only if `(F ) j=u `(F ) _ `(E).

Proof. The claim directly follows from the semantics of frame knowledge bases
and the translation into DLs that we have adopted.

By Theorem 3.5 it becomes possible to exploit the methods for unrestricted
reasoning on aluni knowledge bases in order to reason on frame knowledge
bases. Since the problem of reasoning, e.g., in KEE is already EXPTIME-complete,
we do not pay in terms of computational complexity for the expressiveness
added by the constructs of aluni. In fact, by resorting to the correspondence
with aluni it becomes possible to add to frame systems useful features, such
as the possibility of specifying the inverse of a slot (Karp, 1992), and
still retain the ability to reason in EXPTIME.

4. Semantic Data Models Semantic data models were introduced primarily as
formalisms for database schema design. They provide a means to model databases
in a much richer way than traditional data models supported by Database Management
Systems, and are becoming more and more important because they are adopted
in most of the recent database design methodologies and Computer Aided Software
Engineering tools.

The most widespread semantic data model is the Entity-Relationship (ER) model
introduced by Chen (1976). It has by now become a standard, extensively used
in the design phase of commercial applications. In the commonly accepted
ER notation, classes are called entities and are represented as boxes, whereas
relationships between entities are represented as diamonds. Arrows between
entities, called ISA relationships, represent inclusion assertions. The links
between entities and relationships represent the ER-roles, to which number
restrictions are associated. Dashed links are used whenever such restrictions
are refined for more specific entities. Finally, elementary properties of
entities are modeled by attributes,

3. If we eliminate from ALUN I inverse roles, then the resulting DL has the
finite model property.

211

Calvanese, Lenzerini, & Nardi whose values belong to one of several predefined
domains, such as Integer, String, or Boolean.

The ER model does not provide constructs for expressing explicit disjointness
or disjunction of entities, but extensions of the model allow for the use
of generalization hierarchies which represent a combination of these two
constructs. In order to keep the presentation simple, we do not consider
generalization hierarchies in the formalization we provide, although their
addition would be straightforward. Similarly, we omit attributes of relations.

We now show that all relevant aspects of the ER model can be captured in
aluni, and thus that reasoning on an ER schema can be reduced to reasoning
on the corresponding aluni knowledge base. Since aluni is equipped with capabilities
to reason on knowledge bases, both with respect to finite and unrestricted
models (see Section 6.2), the reduction shows that reasoning on the ER model,
and more generally on semantic data models, is decidable.

As in the case of frame-based systems, we restrict our attention to those
aspects that constitute the core of the ER model. For this reason we do not
consider some features, such as keys and weak entities, that have been introduced
in the literature (Chen, 1976), but appear only in some of the formalizations
of the ER model and the methodologies for conceptual modeling based on the
model. A proposal for the treatment of keys in description logics is presented
by Borgida and Weddell (1997).

In order to establish the correspondence between the ER model and aluni,
we present formal syntax and semantics of ER schemata.

4.1 Syntax of the Entity-Relationship Model Although the ER model has by
now become an industrial standard, several variants and extensions have been
introduced, which differ in minor aspects in expressiveness and in notation
(Chen, 1976; Teorey, 1989; Batini, Ceri, & Navathe, 1992; Thalheim, 1992,
1993). Also, ER schemata are usually defined using a graphical notation which
is particularly useful for an easy visualization of the data dependencies,
but which is not well suited for our purposes. Therefore we have chosen a
formalization of the ER model which abstracts with respect to the most important
characteristics and allows us to develop the correspondence to aluni.

In the following, for two finite sets X and Y we call a function from a subset
of X to Y an X-labeled tuple over Y . The labeled tuple T that maps xi 2
X to yi 2 Y , for i 2 f1; : : : ; kg, is denoted [x1: y1; : : : ; xk: yk].
We also write T [xi] to denote yi.

Definition 4.1 An ER schema is a tuple S = (LS; _S; att S; rel S; card S),
where

ffl LS is a finite alphabet partitioned into a set ES of entity symbols,
a set AS of attribute

symbols, a set US of role symbols, a set RS of relationship symbols, and
a set DS of domain symbols; each domain symbol D has an associated predefined
basic domain DBD , and we assume the various basic domains to be pairwise
disjoint.

ffl _S` ES Theta  ES is a binary relation over ES. ffl att S is a function
that maps each entity symbol in ES to an AS-labeled tuple over DS.

212

Unifying Class-Based Representation Formalisms ffl rel S is a function that
maps each relationship symbol in RS to an US -labeled tuple

over ES. We assume without loss of generality that:

- Each role is specific to exactly one relationship, i.e., for two relationships

R; R0 2 RS with R 6= R0, if rel S(R) = [U1: E1; : : : ; Uk: Ek] and rel S(R0)
= [U 01: E01; : : : ; U 0k0: E0k0 ], then fU1; : : : ; Ukg and fU 01; : :
: ; U 0k0 g are disjoint.

- For each role U 2 US there is a relationship R and an entity E such that

rel S(R) = [: : : ; U : E; : : :].

ffl card S is a function from ES Theta  RS Theta  US to IN0 Theta  (IN0
[ f1g) that satisfies the following condition: for a relationship R 2 RS
such that rel S(R) = [U1: E1; : : : ; Uk: Ek], card S(E; R; U ) is defined
only if U = Ui for some i 2 f1; : : : ; kg, and if E _Lambda S Ei (where
_Lambda S denotes the reflexive transitive closure of _S). The first component
of card S(E; R; U ) is denoted with cminS(E; R; U ) and the second component
with cmax S(E; R; U ). If not stated otherwise, cminS(E; R; U ) is assumed
to be 0 and cmax S(E; R; U ) is assumed to be 1.

Before specifying the formal semantics of ER schemata we give an intuitive
description of the components of a schema. The relation _S models the ISA-relationship
between entities. We do not need to make any special assumption on the form
of _S such as acyclicity or injectivity. The function att S is used to model
attributes of entities. If for example att S associates the AS-labeled tuple
[A1: Integer; A2: String] to an entity E, then E has two attributes A1; A2
whose values are integers and strings respectively. For simplicity we assume
attributes to be single-valued and mandatory, but we could easily handle
also multivalued attributes with associated cardinalities. The function rel
S associates a set of roles to each relationship symbol R, determining implicitly
also the arity of R, and for each role U in such set a distinguished entity,
called the primary entity for U in R. In a database satisfying the schema
only instances of the primary entity are allowed to participate in the relationship
via the role U . The function card S specifies cardinality constraints, i.e.,
constraints on the minimum and maximum number of times an instance of an
entity may participate in a relationship via some role. Since such constraints
are meaningful only if the entity can effectively participate in the relationship,
the function is defined only for the sub-entities of the primary entity.
The special value 1 is used when no restriction is posed on the maximum cardinality.
Such constraints can be used to specify both existence dependencies and functionality
of relations (Cosmadakis & Kanellakis, 1986). They are often used only in
a restricted form, where the minimum cardinality is either 0 or 1 and the
maximum cardinality is either 1 or 1. Cardinality constraints in the form
considered here have been introduced already by Abrial (1974) and subsequently
studied by Grant and Minker (1984), Lenzerini and Nobili (1990), Ferg (1991),
Ye, Parent, and Spaccapietra (1994), Thalheim (1992).

Example 4.2 Figure 4 shows a simple ER schema modeling a state of affairs
similar to the one represented by the KEE knowledge base in Figure 2. We
have used the standard graphic notation for ER schemata, except for the dashed
link, which represents the refinement of a cardinality constraint for the
participation of a sub-entity (in our case AdvCourse) in a relationship (in
our case ENROLLING).

213

Calvanese, Lenzerini, & Nardi AdvCourse

Course

Teacher Student GradStudentdegree/String ENROLLING(2,30) Ein

(4,6)

Eof

TEACHING(1,1) Tof

(0,1)

Tby

(2,20) 6 6

Figure 4: An ER schema 4.2 Semantics of the Entity-Relationship Model The
semantics of an ER schema can be given by specifying which database states
are consistent with the information structure represented by the schema.
Formally, a database state B corresponding to an ER schema S = (LS; _S ;
att S; rel S; card S) is constituted by a nonempty finite set Delta B, assumed
to be disjoint from all basic domains, and a function Delta B that maps

ffl every domain symbol D 2 DS to the corresponding basic domain DBD , ffl
every entity E 2 ES to a subset EB of Delta B, ffl every attribute A 2 AS
to a set AB ` Delta B Theta  SD2DS DBD , and ffl every relationship R 2
RS to a set RB of US-labeled tuples over Delta B.

The elements of EB, AB, and RB are called instances of E, A, and R respectively.

A database state is considered acceptable if it satisfies all integrity constraints
that are part of the schema. This is captured by the definition of legal
database state.

Definition 4.3 A database state B is said to be legal for an ER schema S
= (LS; _S ; att S; rel S; card S), if it satisfies the following conditions:

ffl For each pair of entities E1; E2 2 ES such that E1 _S E2, it holds that
EB1 ` EB2 . ffl For each entity E 2 ES, if att S(E) = [A1: D1; : : : ; Ah:
Dh], then for each instance

e 2 EB and for each i 2 f1; : : : ; hg the following holds:

- there is exactly one element ai 2 ABi whose first component is e, and -
the second component of ai is an element of DBDi .

ffl For each relationship R 2 RS such that rel S (R) = [U1: E1; : : : ; Uk:
Ek], all instances

of R are of the form [U1: e1; : : : ; Uk: ek], where ei 2 EBi , i 2 f1; :
: : ; kg.

214

Unifying Class-Based Representation Formalisms

Even Number

DOUBLES

(1,1)

(0,1) 6

Figure 5: The ER schema corresponding to Example 2.2 ffl For each relationship
R 2 RS such that rel S(R) = [U1: E1; : : : ; Uk: Ek], for each

i 2 f1; : : : ; kg, for each entity E 2 ES such that E _Lambda S Ei and
for each instance e of E in I, it holds that

cminS(E; R; Ui) ^ ]fr 2 RB j r[Ui] = eg ^ cmax S(E; R; Ui):

Notice that the definition of database state reflects the usual assumption
in databases that database states are finite structures (see also Cosmadakis,
Kanellakis, & Vardi, 1990). In fact, the basic domains are not required to
be finite, but for each legal database state for a schema, only a finite
set of values from the basic domains are actually of interest. We define
the active domain Delta Bact of a database state B as the set of all elements
of the basic domains DBD , D 2 DS, that effectively appear as values of attributes
in B. More formally:

Delta Bact = fd 2 DBD j D 2 DS ^ 9A 2 AS; e 2 Delta B . (e; d) 2 ABg: Since
Delta B is finite and AS contains only a finite number of attributes, which
are functional by definition, also Delta Bact is finite.

Reasoning in the ER model includes verifying entity satisfiability and deducing
inheritance. Entity satisfiability amounts to checking whether a given entity
can be populated in some legal database state (Atzeni & Parker Jr., 1986;
Lenzerini & Nobili, 1990; Di Battista & Lenzerini, 1993), and corresponds
to the notion of concept consistency in DLs. Deducing inheritance amounts
to verifying whether in all databases that are legal for the schema, every
instance of an entity is also an instance of another entity. Such implied
ISA relationships can arise for different reasons. Either trivially, through
the transitive closure of the explicit ISA relationships present in the schema,
or in more subtle ways, through specific patterns of cardinality restrictions
along cycles in the schema and the requirement of the database state to be
finite (Lenzerini & Nobili, 1990; Cosmadakis et al., 1990).

Example 4.4 Figure 5 shows an ER schema modeling the same situation as the
knowledge base of Example 2.2. Arguing exactly as in that example we can
conclude that the two entities Number and Even denote the same set of elements
in every finite database legal for the schema, although the ISA relation
from Number to Even is not stated explicitly. It is implied, however, due
to the cycle involving the relationship and the two entities and due to the
particular form of cardinality constraints.

215

Calvanese, Lenzerini, & Nardi 4.3 Relationship between Entity-Relationship
Schemata and aluni We now show that the different forms of reasoning on ER
schemata are captured by finite concept consistency and finite concept subsumption
in aluni. The correspondence between the two formalisms is established by
defining a translation OE from ER schemata to aluni knowledge bases, and
then proving that there is a correspondence between legal database states
and finite models of the derived knowledge base.

Definition 4.5 Let S = (LS; _S ; att S; rel S; card S) be an ER schema. The
aluni knowledge base OE(S) = (A; P; T ) is defined as follows: The set A
of atomic concepts of OE(S) contains the following elements:

ffl for each domain symbol D 2 DS, an atomic concept OE(D); ffl for each
entity E 2 ES, an atomic concept OE(E); ffl for each relationship R 2 RS,
an atomic concept OE(R).

The set P of atomic roles of OE(S) contains the following elements:

ffl for each attribute A 2 AS , an atomic role OE(A); ffl for each relationship
R 2 RS such that rel S(R) = [U1: E1; : : : ; Uk: Ek], k atomic roles

OE(U1); : : : ; OE(Uk).

The set T of assertions of OE(S) contains the following elements:

ffl for each pair of entities E1; E2 2 ES such that E1 _S E2, the assertion

OE(E1) ._ OE(E2) (1)

ffl for each entity E 2 ES such that att S (E) = [A1: D1; : : : ; Ah: Dh],
the assertion

OE(E) ._ 8OE(A1).OE(D1) u Delta  Delta  Delta  u 8OE(Ah).OE(Dh) u 9=1OE(A1)
u Delta  Delta  Delta  u 9=1OE(Ah) (2)

ffl for each relationship R 2 RS such that rel S (R) = [U1: E1; : : : ; Uk:
Ek], the assertions

OE(R) ._ 8OE(U1).OE(E1) u Delta  Delta  Delta  u 8OE(Uk).OE(Ek) u 9=1OE(U1)
u Delta  Delta  Delta  u 9=1OE(Uk) (3) OE(Ei) ._ 8(OE(Ui))Gamma .OE(R);
i 2 f1; : : : ; kg (4)

ffl for each relationship R 2 RS such that rel S (R) = [U1: E1; : : : ; Uk:
Ek], for i 2

f1; : : : ; kg, and for each entity E 2 ES such that E _Lambda S Ei,

- if m = cminS(E; R; Ui) 6= 0, the assertion

OE(E) ._ 9*m(OE(Ui))Gamma : (5) - if n = cmax S (E; R; Ui) 6= 1, the assertion

OE(E) ._ 9^n(OE(Ui))Gamma : (6) ffl for each pair of symbols X1; X2 2 ES
[RS [DS such that X1 6= X2 and X1 2 RS [DS,

the assertion

OE(X1) ._ :OE(X2): (7)

216

Unifying Class-Based Representation Formalisms K = (A; P; T ), where

A = fCourse; AdvCourse; Teacher; Student; GradStudent; TEACHING; ENROLLING;
Stringg, P = fTof; Tby; Ein; Eof; degreeg, and the set T of assertions consists
of:

TEACHING ._ 8Tof.Course u 9=1Tof u

8Tby.Teacher u 9=1Tby

ENROLLING ._ 8Ein.Course u 9=1Ein u

8Eof.Student u 9=1Eof

Course ._ 8Tof

Gamma .TEACHING u 9=1TofGamma  u

8Ein

Gamma .ENROLLING u 9*2EinGamma  u 9^30EinGamma 

AdvCourse ._ Course u 9^20Ein

Gamma 

Teacher ._ 8Tby

Gamma .TEACHING

Student ._ 8Eof

Gamma .ENROLLING u 9*4EofGamma  u 9^6EofGamma 

GradStudent ._ Student u 8degree.String u 9=1degree:

Figure 6: The aluni knowledge base corresponding to the ER schema in Figure
4 Example 4.2 (cont.) We illustrate the translation on the ER schema of Figure
4. The aluni knowledge base that captures exactly its semantics is shown
in Figure 6, where for brevity the disjointness assertions (7) are omitted,
and assertions with the same concept on the left hand side are collapsed.

The translation makes use of both inverse attributes and number restrictions
to capture the semantics of ER schemata. We observe that, by means of the
inverse constructor, a binary relationship could be treated in a simpler
way by choosing a traversal direction and mapping the relationship directly
to a role. Notice also that the assumption of acyclicity of the resulting
knowledge base is unrealistic in this case, and in order to exploit the correspondence
for reasoning in the ER model, we need techniques that can deal with inverse
attributes, number restrictions, and cycles together. As shown in Example
2.2, the combination of these factors causes the finite model property to
fail to hold, and we need to resort to reasoning methods for finite models.

In fact, we can reduce reasoning in the ER model to finite model reasoning
in aluni knowledge bases. For this purpose we define a mapping between database
states corresponding to an ER schema and finite interpretations of the knowledge
base derived from it. Due to the possible presence of relations with arity
greater than 2, this mapping is however not one-to-one and we first need
to characterize those interpretations of the knowledge base that directly
correspond to database states.

Definition 4.6 Let S = (LS; _S ; att S; rel S; card S) be an ER schema and
OE(S) be defined as above. An interpretation I of OE(S) is relation-descriptive,
if for every relationship R 2 RS , with rel S(R) = [U1: E1; : : : ; Uk: Ek],
for every d; d0 2 (OE(R))I , we have that

( ^

1^i^k

8d00 2 Delta I . ((d; d00) 2 (OE(Ui))I $ (d0; d00) 2 (OE(Ui))I )) ! d =
d0: (8)

217

Calvanese, Lenzerini, & Nardi Intuitively, the extension of a relationship
in a database state is a set of labeled tuples, and such a set does not contain
the same element twice. Therefore it is implicit in the semantics of the
ER model that there cannot be two labeled tuples connected through all roles
of the relationship to exactly the same elements of the domain. In a model
of the aluni knowledge base corresponding to the ER schema, on the other
hand, each tuple is represented by a new individual, and the above condition
is not implicit anymore. It also cannot be imposed in aluni by suitable assertions.
The following lemma, however, shows that we do not need such an explicit
condition, when we are interested in reasoning on an aluni knowledge base
corresponding to an ER schema. This is due to the fact that we can always
restrict ourselves to considering only relation-descriptive models.

Lemma 4.7 Let S be an ER schema, OE(S) be the aluni knowledge base obtained
from S according to Definition 4.5, and C be a concept expression of OE(S).
If C is finitely consistent in OE(S), then there is a finite relation-descriptive
model I of OE(S) such that CI 6= ;.

Proof. Let I0 be a finite model of OE(S) such that CI 6= ;. We can build
a finite relationdescriptive model I0 by starting from I0 and applying the
following construction once for each relationship in RS.

Let I be the model obtained in the previous step and let R 2 RS with rel
S(R) = [U1: E1; : : : ; Uk: Ek] be the next relationship to which we apply
the construction. We construct from I a model IR such that condition 8 is
satisfied for relationship R.

Given an individual r 2 (OE(R))I , we denote by Ui(d), i 2 f1; : : : ; kg
the (unique) individual e such that (r; e) 2 (OE(Ui))I. For ei 2 (OE(Ei))I
, i 2 f1; : : : ; kg we define X(U1:e1;:::;Uk:ek) = fr 2 (OE(R))I j Ui(d)
= ei; for i 2 f1; : : : ; kgg. We call conflict-set a set X(U1:e1;:::;Uk:ek)
with more than one element. From each conflict-set X(U1:e1;:::;Uk:ek) we
randomly choose one individual r, and we say that the others induce a conflict
on (U1: e1; : : : ; Uk: ek). We call Conf the (finite) set of all objects
inducing a conflict on some (U1: e1; : : : ; Uk: ek).

We define an interpretation I2Conf as the disjoint union of 2]Conf copies
of I, one copy, denoted by IZ , for every set Z 2 2Conf . We denote by dZ
the copy in IZ of the individual d in I. Since the disjoint union of two
models of an aluni knowledge base is again a model, I2Conf is a model of
OE(S). Let IZ and IZ0 be two copies of I in I2Conf . We call exchanging Uk(rZ
) with Uk(rZ0) the operation on I2Conf consisting of replacing in (OE(Uk))IZ
the pair (rZ ; Uk(rZ )) with (rZ ; Uk(rZ0)) and, at the same time, replacing
in (OE(Uk))IZ0 the pair (rZ0; Uk(rZ0)) with (rZ0; Uk(rZ )). Intuitively,
by exchanging Uk(rZ ) with Uk(rZ0), the individuals rZ and rZ0 do not induce
conflicts anymore.

We construct now from I2Conf an interpretation IR as follows: For each r
2 Conf and for each Z 2 2Conf such that r 2 Z, we exchange Uk(rZ ) with Uk(rZnfrg).
It is possible to show that all conflicts are thus eliminated while no new
conflict is created. Hence, in IR, condition 8 for R is satisfied. We still
have to show that IR is a model of OE(S) in which CIR 6= ;. Indeed, it is
straightforward to check by induction that for every concept expression C0
appearing in OE(S), for all Z 2 2Conf , d 2 C0I if and only if dZ 2 C0IR.
Thus all assertions of OE(S) are still satisfied in IR and CIR 6= ;.

218

Unifying Class-Based Representation Formalisms With this result, the following
correspondence between legal database states for an ER schema and relation-descriptive
models of the resulting aluni knowledge base can be established.

Proposition 4.8 For every ER schema S = (LS ; _S; att S ; rel S; card S )
there exist two mappings ffS , from database states corresponding to S to
finite interpretations of its translation OE(S), and fiS , from finite relation-descriptive
interpretations of OE(S) to database states corresponding to S, such that:

1. For each legal database state B for S, ffS(B) is a finite model of OE(S),
and for each

symbol X 2 ES [ AS [ RS [ DS , XB = (OE(X))ffS (B).

2. For each finite relation-descriptive model I of OE(S), fiS(I) is a legal
database state for

S, for each entity E 2 ES , (OE(E))I = EfiS(I), and for each symbol X 2 AS
[ RS [ DS, ]OE(X)I = ]XfiS(I).

Proof. (1) Given a database state B, we define the interpretation I = ffS(B)
of OE(S) as follows:

ffl Delta I = Delta B [ Delta Bact [ SR2RS RB. ffl For each symbol X 2
ES [ AS [ RS [ DS,

(OE(X))I = XB: (9)

ffl For each relationship R 2 RS such that rel S(R) = [U1: E1; : : : ; Uk:
Ek],

(OE(Ui))I = f(r; e) 2 Delta I Theta  Delta I j r 2 RB; and r[Ui] = eg;
i 2 f1; : : : ; kg: (10)

Let B be a legal database state. To prove claim (1) it is sufficient to show
that I satisfies every assertion in OE(S). Assertions 1 are satisfied since
B satisfies the set inclusion between the extensions of the corresponding
entities. With respect to assertions 2, let E 2 ES be an entity such that
att S(E) = [A1: D1; : : : ; Ah: Dh], and consider an instance e 2 (OE(E))I
. We have to show that for each i 2 f1; : : : ; hg, there is exactly one
element ei 2 Delta I such that (e; ei) 2 (OE(Ai))I , and moreover that ei
2 (OE(Di))I . By 9, e 2 EB, and by definition of legal database state there
is exactly one element ai 2 ABi = (OE(Ai))I whose first component is e. Moreover,
the second component ei of ai is an element of DBDi = (OE(Di))I . With respect
to assertions 3, let R 2 RS be a relationship such that rel S (R) = [U1:
E1; : : : ; Uk: Ek], and consider an instance r 2 (OE(R))I . We have to show
that for each i 2 f1; : : : ; kg there is exactly one element ei 2 Delta
I such that (r; ei) 2 (OE(Ui))I , and that moreover ei 2 (OE(Ei))I . By 9,
r 2 RB, and by definition of legal database state, r is a labeled tuple of
the form [U1: e01; : : : ; Uk: e0k], where e0i 2 EBi , i 2 f1; : : : ; kg.
Therefore r is a function defined on fU1; : : : ; Ukg, and by 10, ei is unique
and equal to e0i. Moreover, again by 9, ei 2 (OE(Ei))I = EBi . Assertions
4 are satisfied, since by 10 the first component of each element of (OE(Ui))I
is always an element of RB = (OE(R))I . With respect to assertions 5, let
R 2 RS be a relationship such that rel S (R) = [U1: E1; : : : ; Uk: Ek],
let E 2 ES be an entity such that E _S Ei, for some i 2 f1; : : : ; kg, and
such that m = cminS (E; R; Ui) 6= 0.

219

Calvanese, Lenzerini, & Nardi Consider an instance e 2 (OE(E))I . We have
to show that there are at least m pairs in (OE(Ui))I that have e as their
second component. Since assertions 4 are satisfied we know that the first
component of all such pairs is an instance of OE(R). By 9 and by definition
of legal database state, there are at least m labeled tuples in RB whose
Ui component is equal to e. By 10, (OE(Ui))I contains at least m pairs whose
second component is equal to e. With respect to assertions 6 we can proceed
in a similar way. Finally, assertions 7 are satisfied since first, by definition
the basic domains are pairwise disjoint and disjoint from Delta B and from
the set of labeled tuples, second, no element of Delta B is a labeled tuple,
and third, labeled tuples corresponding to different relationships cannot
be equal since they are defined over different sets of roles.

(2) Let I be a finite relation-descriptive interpretation of OE(S). For each
basic domain D 2 DS, let fiDDelta  be a function from Delta I to DBD that
is one-to-one and onto. Since Delta I is finite and each basic domain contains
a countable number of elements, such a function always exists. In order to
define fiS (I) we first specify a mapping fiDelta  that associates to each
individual d 2 Delta I an element as follows:

ffl If d 2 (OE(E))I for some entity E 2 ES , then fiDelta (d) = d. ffl If
d 2 (OE(R))I for some relationship R 2 RS with rel S(R) = [U1: E1; : : :
; Uk: Ek], and

there are individuals d1; : : : ; dk 2 Delta I such that (d; di) 2 (OE(Ui))I
, for i 2 f1; : : : ; kg, then fiDelta (d) = [U1: d1; : : : ; Uk: dk].

ffl If d 2 (OE(D))I for some basic domain D 2 DS, then fiDelta (d) = fiDDelta
(d). ffl Otherwise fiDelta (d) = d. For a pair of individuals (d1; d2) 2
Delta I Theta  Delta I, fiDelta ((d1; d2)) = (fiDelta (d1); fiDelta
(d2)), and for a set X, fiDelta (X) = ffiDelta (x) j x 2 Xg.

If I is a model of OE(S) the above rules define fiDelta (d) for every d
2 Delta I. Indeed, by assertions 7, each d 2 Delta I can be an instance
of at most one atomic concept corresponding to a relationship or basic domain,
and if this is the case it is not an instance of any atomic concept corresponding
to an entity. Moreover, if d 2 (OE(R))I for some relationship R 2 RS with
rel S(R) = [U1: E1; : : : ; Uk: Ek], then by assertions 3, for each i 2 f1;
: : : ; kg there is exactly one element di 2 Delta I such that (d; di) 2
(OE(Ui))I . If I is not a model of OE(S) and for some d 2 Delta I, fiDelta
(d) is not uniquely determined, then we choose nondeterministically one possible
value.

We can now define the database state B = fiS(I) corresponding to I:

ffl Delta B = Delta I n iSR2RS (OE(R))I [ SD2DS (OE(D))I j. ffl For each
symbol X 2 ES [ AS [ RS [ DS, XB = fiDelta ((OE(X))I ). It is not difficult
to see, that if I is a model of OE(S), then B defined in such a way is a
legal database state for S with active domain SD2DS (OE(D))I .

220

Unifying Class-Based Representation Formalisms The following theorem allows
us to reduce reasoning on ER schemata to finite model reasoning on aluni
knowledge bases.

Theorem 4.9 Let S be an ER schema, E; E0 be two entities in S, and OE(S)
be the translation of S. Then the following holds:

1. E is satisfiable in S if and only if OE(S) 6j=f OE(E) _ ?. 2. E inherits
from E0 in S if and only if OE(S) j=f OE(E) _ OE(E0).

Proof. (1) ")" Let B be a legal database state with EB 6= ;. By part 1 of
Proposition 4.8, ffS(B) is a finite model of OE(S) in which (OE(E))ffS (B)
6= ;.

"(" Let OE(E) be finitely consistent in OE(S). By Lemma 4.7 there is a finite
relationdescriptive model I of OE(S) with OE(E)I 6= ;. By part 2 of Proposition
4.8, fiS(I) is a database state legal for S in which EB 6= ;.

(2) ")" Let OE(S) 6j=f OE(E) _ OE(E0). Then OE(E) u :OE(E0) is finitely consistent
in OE(S). By Lemma 4.7 there is a finite relation-descriptive model I of
OE(S) with d 2 (OE(E))I and d 62 (OE(E0))I, for some d 2 Delta I . By part
2 of Proposition 4.8, fiS (I) is a database state legal for S in which d
2 EB and d 62 E0B. Therefore E does not inherit from E0.

"(" Assume E does not inherit from E0. Then there is a database state B legal
for S where for an instance e 2 EB we have e 62 E0B. By part 1 of Proposition
4.8, ffS(B) is a finite model of OE(S) in which e 2 (OE(E))ffS (B) and e
62 (OE(E0))ffS (B). Therefore OE(S) 6j=f OE(E) _ OE(E0).

Theorem 4.9 allows us to effectively exploit the reasoning methods that have
been developed for aluni in order to reason on ER schemas. The complexity
of the resulting method for reasoning on ER schemata is exponential. Observe
however, that the known algorithms for reasoning on ER schemata are also
exponential (Calvanese & Lenzerini, 1994b), and that the precise computational
complexity of the problem is still open.

Moreover, by exploiting the correspondence with aluni, it becomes possible
to add to the ER model (and more in general to semantic data models) several
features and modeling primitives that are currently missing, and which have
been considered important, and fully take them into account when reasoning
over schemata. Such additional features include for example the possibility
to specify and use arbitrary boolean combinations of entities, and to refine
properties of entities along ISA hierarchies.

5. Object-Oriented Data Models Object-oriented data models have been proposed
with the goal of devising database formalisms that could be integrated with
object-oriented programming systems (Kim, 1990). They are the subject of
an active area of research in the database field, and are based on the following
features:

ffl They rely on the notion of object identifier at the extensional level
(as opposed to

traditional data models which are value-oriented) and on the notion of class
at the intensional level.

221

Calvanese, Lenzerini, & Nardi ffl The structure of the classes is specified
by means of typing and inheritance.

As in the previous section, we present the common basis of object-oriented
data models with other class-based formalisms by introducing a language for
specifying object-oriented schemata and show that such schemata can be correctly
represented as aluni knowledge bases. In our analysis, we concentrate our
attention on the structural aspects of objectoriented data models. One of
the characteristics of the object-oriented approach is to provide mechanisms
for specifying also the dynamic properties of classes and objects, typically
through the definition of methods associated to the classes. Those aspects
are outside the scope of our investigations. Nevertheless, we argue that
general techniques for schema level reasoning, in particular, type consistency
and type inference, can be profitably exploited for restricted forms of reasoning
on methods (Abiteboul, Kanellakis, Ramaswamy, & Waller, 1992).

5.1 Syntax of an Object-Oriented Model Below we define a simple object-oriented
language in the style of most popular models featuring complex objects and
object identity. Although we do not refer to any specific formalism, our
model is inspired by the ones presented by Abiteboul and Kanellakis (1989),
Hull and King (1987).

Definition 5.1 An object-oriented schema is a tuple S = (CS ; AS ; DS), where:

ffl CS is a finite set of class names, denoted by the letter C. ffl AS is
a finite set of attribute names, denoted by the letter A. ffl DS is a finite
set of class declarations of the form

Class C is-a C1; : : : ; Ck type-is T; in which T denotes a type expression
built according to the following syntax:

T Gamma ! C j

Union T1; : : : ; Tk End j Set-of T j Record A1: T1; : : : ; Ak: Tk End:

DS contains exactly one such declaration for each class C 2 CS.

Example 5.2 Figure 7 shows a fragment of the object-oriented schema corresponding
to the KEE knowledge base of Figure 2.

Each class declaration imposes constraints on the instances of the class
it refers to. The is-a part of a class declaration allows one to specify
inclusion between the sets of instances of the involved classes, while the
type-is part specifies through a type expression the structure assigned to
the objects that are instances of the class.

222

Unifying Class-Based Representation Formalisms Class Teacher type-is

Union Professor, GradStudent End

Class GradStudent is-a Student type-is

Record

degree: String End

Class Course type-is

Record

enrolls: Set-of Student, taughtby: Teacher End

Figure 7: An object-oriented schema 5.2 Semantics of an Object-Oriented Model
The meaning of an object-oriented schema is given by specifying the characteristics
of an instance of the schema. The definition of instance makes use of the
notions of object identifier and value.

Let us first characterize the set of values that can be constructed from
a set of symbols, called object identifiers. Given a finite set O of symbols
denoting real world objects, the set VO of values over O is inductively defined
as follows:

ffl O ` VO. ffl If v1; : : : ; vk 2 VO then fjv1; : : : ; vkjg 2 VO. ffl
If v1; : : : ; vk 2 VO then [[A1: v1; : : : ; Ak: vk]] 2 VO. ffl Nothing
else is in VO.

A database instance J of a schema S = (CS; AS; DS ) is constituted by

ffl a finite set OJ of object identifiers; ffl a mapping ssJ assigning to
each class in CS a subset of OJ ; ffl a mapping aeJ assigning a value in
VOJ to each object in OJ .

Although the set VOJ of values that can be constructed from a set OJ of object
identifiers is infinite, for a database instance one needs only to consider
a finite subset of VOJ .

Definition 5.3 Given an object-oriented schema S and an instance J of S,
the set VJ of active values with respect to J is constituted by:

ffl the set OJ of object identifiers. ffl the set of values assigned by aeJ
to the elements of OJ , including those values that

are not explicitly associated with object identifiers, but are used to form
other values.

The interpretation of type expressions in J is defined through an interpretation
function Delta J that assigns to each type expression a subset of VOJ such
that the following conditions are satisfied:

CJ = ssJ (C)

223

Calvanese, Lenzerini, & Nardi (Union T1; : : : ; Tk End)J = T J1 [ Delta
Delta  Delta  [ T Jk

(Set-of T )J = ffjv1; : : : ; vkjg j k * 0; vi 2 T J ; for i 2 f1; : : :
; kgg

(Record A1: T1; : : : ; Ak: Tk End)J = f[[A1: v1; : : : ; Ah: vh]] j h *
k;

vi 2 T Ji ; for i 2 f1; : : : ; kg; vj 2 VOJ ; for j 2 fk + 1; : : : ; hgg:

Notice that the instances of type record may have more components than those
specified in the type of the class. Thus we are using an open semantics for
records, which is typical of object-oriented data models (Abiteboul & Kanellakis,
1989).

In order to characterize object-oriented data models we consider the instances
that are admissible for the schema.

Definition 5.4 Let S = (CS ; AS ; DS) be an object-oriented schema. A database
instance J of S is said to be legal (with respect to S) if for each declaration

Class C is-a C1; : : : ; Cn type-is T in DS , it holds that CJ ` CJi for
each i 2 f1; : : : ; ng, and that aeJ (CJ ) ` T J .

Therefore, for a legal database instance, the type expressions that are present
in the schema determine the (finite) set of active values that must be considered.
The construction of such values is limited by the depth of type expressions.

5.3 Relationship between Object-Oriented Schemata and aluni We establish
now a relationship between aluni and the object-oriented language presented
above. This is done by providing a mapping from object-oriented schemata
into aluni knowledge bases. Since the interpretation domain for aluni knowledge
bases consists of atomic objects, whereas each instance of an object-oriented
schema is assigned a possibly structured value (see the definition of VO),
we need to explicitly represent some of the notions that underlie the object-oriented
language. In particular, while there is a correspondence between concepts
and classes, one must explicitly account for the type structure of each class.
This can be accomplished by introducing in aluni concepts AbstractClass,
to represent the classes, and RecType and SetType to represent the corresponding
types. The associations between classes and types induced by the class declarations,
as well as the basic characteristics of types, are modeled by means of roles:
the (functional) role value models the association between classes and types,
and the role member is used for specifying the type of the elements of a
set. Moreover, the concepts representing types are assumed to be mutually
disjoint, and disjoint from the concepts representing classes. These constraints
are expressed by adequate inclusion assertions that will be part of the knowledge
base we are going to define.

We first define the function  that maps each type expression into an ALU
N I concept expression as follows:

ffl Every class C is mapped into an atomic concept (C). ffl Every type expression
Union T1; : : : ; Tk End is mapped into (T1) t Delta  Delta  Delta  t
(Tk).

224

Unifying Class-Based Representation Formalisms ffl Every type expression
Set-of T is mapped into SetType u 8member.(T ). ffl Every attribute A is
mapped into an atomic role (A), and every type expression

Record A1: T1; : : : ; Ak: Tk End is mapped into

RecType u 8(A1).(T1) u 9=1(A1) u Delta  Delta  Delta  u

8(Ak).(Tk) u 9=1(Ak):

Using  we define the aluni knowledge base corresponding to an object-oriented
schema. Definition 5.5 The aluni knowledge base (S) = (A; P; T ) corresponding
to the objectoriented schema S = (CS; AS; DS ) is obtained as follows:

ffl A = fAbstractClass; RecType; SetTypeg [ f(C) j C 2 CSg. ffl P = fvalue;
memberg [ f(A) j A 2 AS g. ffl T consists of the following assertions:

AbstractClass ._ 9=1value

RecType ._ 8value.? SetType ._ 8value.? u :RecType

and for each class declaration

Class C is-a C1; : : : ; Cn type-is T in DS, an inclusion assertion

(C) ._ AbstractClass u (C1) u Delta  Delta  Delta  u (Cn) u 8value.(T
):

From the above translation we can observe that inverse roles are not necessary
for the formalization of object-oriented data models. Indeed, the possibility
of referring to the inverse of an attribute is generally ruled out in such
models. However, this strongly limits the expressive power of the data model,
as pointed out in recent papers (see for example Albano, Ghelli, & Orsini,
1991; Cattell, 1994). Note also that the use of number restrictions is limited
to the value 1, which corresponds to existence constraints and functionality,
whereas union is used in a more general form than for example in the KEE
system.

Example 5.2 (cont.) We illustrate the translation on the fragment of object-oriented
schema in Figure 7. The corresponding aluni knowledge base is shown in Figure
8.

225

Calvanese, Lenzerini, & Nardi K = (A; P; T ), where

A = fAbstractClass; RecType; SetType; String;

Course; Teacher; Professor; Student; GradStudentg,

P = fvalue; member; enrolls; taughtby; degreeg, and the set T of assertions
consists of:

Course ._ AbstractClass u

8value.(RecType u 9=1enrolls u 9=1taughtby u

8enrolls.(SetType u 8member.Student) u 8taughtby.Teacher)

Teacher ._ AbstractClass u 8value.(GradStudent t Professor) GradStudent ._
AbstractClass u Student u

8value.(RecType u 8degree.String u 9=1degree)

AbstractClass ._ 9=1value

RecType ._ 8value.? SetType ._ 8value.? u :RecType

Figure 8: The aluni knowledge base corresponding to the object-oriented schema
in Figure 7

Below we discuss the effectiveness of the translation . First of all observe
that the aluni knowledge base (S) resulting from the translation of an object-oriented
schema S may admit models that do not have a direct counterpart among legal
database instances of S. More precisely, both an interpretation of (S) and
a database instance of S can be viewed as a directed labeled graph: In the
case of an interpretation, the nodes are domain individuals and the arcs
are labeled with roles. In the case of a database instance, the nodes are
either object identifiers or active values, and an arc either connects an
object identifier to its associated value (in which case it is labeled with
value), or is part of the sub-structure representing a set or record value
(in which case it is labeled with member or with an attribute, in accordance
with the type of the value). In a legal database instance of S, a value v
is represented by a sub-structure that has the form of a finite tree with
v as root, set and record values as intermediate nodes, and objects identifiers
as leaves. Clearly, such a substructure does not contain cycles. Conversely,
in a model of (S), there may be cycles involving only nodes that are instances
of SetType and RecType and in which all roles are different from value. We
call such cycles bad. A model containing bad cycles cannot be put directly
in correspondence with a legal database instance. Also, due to the open semantics
of records one cannot adopt a different translation for which bad cycles
in the model are ruled out.

Example 5.6 Consider the object-oriented schema S, containing a single class
declaration

Class C type-is Record a1 : Record a2 : Record a3 : C End End End

226

Unifying Class-Based Representation Formalisms o1 v1 v2

o2 v3 v4 v5

C

C RecType

RecType RecType RecType RecType a1

a1 a2

a2

a3 a3

value

value

Figure 9: A model containing cycles which is translated to C ._ AbstractClass
u

8value.(RecType u 9=1a1 u 8a1.(RecType u 9=1a2 u 8a2.(RecType u 9=1a3 u 8a3.C))):

Figure 9 shows a model of (S) represented as a graph. For clarity, we have
named the instances of C, and hence of AbstractClass, with o and the instances
of RecType with v. Observe the two different types of cycles in the graph.
The cycle involving individuals o2; v3; v4, and v5 does not cause any problems
since it contains an arc labeled with value, which is not part of the structure
constituting a complex value. In fact, v3 represents the record value [[a1:
[[a2: [[a3: o2]]]]]]. On the other hand, due to the bad cycle involving v1
and v2, individual v1 represents (together with o2 connected via a3 to v1)
a record of infinite depth.

We can nevertheless establish a correspondence from finite models of (S)
possibly containing bad cycles to legal instances of the object-oriented
schema S. This can be achieved by unfolding the bad cycles in a model of
(S) to infinite trees. Obviously, the unfolding of a cycle into an infinite
tree, generates an infinite number of nodes, which would correspond to an
infinite database state. However, we can restrict the duplication of individuals
to those that represent set and record values, and thus are instances of
SetType and RecType. The instances of AbstractClass, instead, are not duplicated
in the process of unfolding, and therefore their number remains finite. Moreover,
since the set of possible active values associated with each object identifier
is bound by the depth of the schema, we can in fact block the unfolding of
bad cycles to the finite tree of depth equal to the depth of the schema.

Let us first formally define the depth of an object-oriented schema S.

Definition 5.7 For a type expression T we define depth (T ) inductively as
follows:

depth (T ) =

8??!

??:

0; if T = C. max1^i^k(depth (Ti)); if T = Union T1; : : : ; Tk End. 1 + depth(T
0); if T = Set-of T 0. 1 + max1^i^k(depth(Ti)); if T = Record A1: T1; : :
: ; Ak: Tk End.

The depth of an object-oriented schema S is defined as the maximum of depth(T
) for a type expression T in S.

227

Calvanese, Lenzerini, & Nardi o1

C RecType

a3

value v0

2 a

1 a1a1

RecType

a2 a2

v3 v4 v5 C RecType RecType RecType

a1 a2

a3

RecType

: : : RecType

v01 v11 v12 v21

RecType

a3a3 value o2

Figure 10: The unfolded version of the model in Figure 9 We can now introduce
the notion of unfolding of an aluni interpretation. Definition 5.8 Let S
be an object-oriented schema, (S) its translation in aluni and I a finite
interpretation of (S). We call unfolded version of I the interpretation obtained
from I as follows: For each individual v that is part of a bad cycle, unfold
the bad cycle into an (infinite) tree having v as root, by generating new
individuals only for the instances of RecType and SetType. For a nonnegative
integer m, we call m-unfolded version of I, denoted as Ijm, the interpretation
obtained by truncating at depth m each infinite tree generated in the process
of unfolding.

Example 5.6 (cont.) Figure 10 shows the unfolded version of the model in
Figure 9. Notice that only the bad cycle has been unfolded to an infinite
tree, and that all arcs labeled with a3 lead to o2, which is an instance
of AbstractClass and has not been duplicated.

The correctness of (S) is sanctioned by the following proposition. Proposition
5.9 For every object-oriented schema S of depth m, there exist mappings:

1. ffS from instances of S into finite interpretations of (S) and ffV from
active values

of instances of S into domain elements of the finite interpretations of (S)
such that: For each legal instance J of S, ffS (J ) is a finite model of
(S), and for each type expression T of S and each v 2 VJ , v 2 T J if and
only if ffV (v) 2 ((T ))ffS (J ).

2. fiS from finite interpretations of (S) into instances of S and fiV from
domain elements of the m-unfolded versions of the finite interpretations
of (S) into active values of instances of S, such that: For each finite model
I of (S), fiS(I) is a legal instance of S, and for each concept (T ), which
is the translation of a type expression T of S and each d 2 Delta Ijm ,
d 2 ((T ))Ijm if and only if fiV (d) 2 T fiS(I).

Proof. (1) Given a database instance J we define an interpretation ffS (J
) of (S) as follows:

228

Unifying Class-Based Representation Formalisms ffl ffV is a function mapping
every element of VJ into a distinct element of Delta ffS(J ).

Therefore Delta ffS(J ) is defined as the set of elements ffV (v) such that
v 2 VJ . Moreover we denote with Delta id, Delta rec, and Delta set the
elements of Delta ffS(J ) corresponding to object identifiers, record and
set values, respectively.

ffl The interpretation of atomic concepts is defined as follows:

((C))ffS (J ) = fffV (o) j o 2 ssJ (C)g;

for every (C) corresponding to a class name C in S AbstractClassffS(J ) =
Delta id

RecTypeffS(J ) = Delta rec SetTypeffS(J ) = Delta set

ffl The interpretation of atomic roles is defined as follows:

((A))ffS (J ) = f(d1; d2) j d1 2 Delta rec and ffGamma 1V (d1) = [[: :
: ; A: ffGamma 1V (d2); : : :]]g;

for every (A) corresponding to an attribute name A in S memberffS(J ) = f(d1;
d2) j d1 2 Delta set and ffGamma 1V (d1) = fj: : : ; ffGamma 1V (d2);
: : :jgg

valueffS(J ) = f(d1; d2) j (ffGamma 1V (d1); ffGamma 1V (d2)) 2 aeJ g

We prove that for each type T and each v 2 VJ , v 2 T J if and only if ffV
(v) 2 ((T ))ffS (J ). The first part of the thesis then follows from the
definition of ffS(J ). The proof is by induction on the structure of the
type expression.

Base case: T = C (i.e., T is a class name). If o 2 CJ then ffV (o) 2 ((C))ffS
(J ), and vice-versa if d 2 ((C))ffS(J ) then ffGamma 1V (d) 2 CJ .

Inductive case: T = Record A1: T1; : : : ; Ak: Tk End and (T ) = RecType
u 8(A1).(T1) u 9=1(A1) u Delta  Delta  Delta  u 8(Ak).(Tk) u 9=1(Ak).
We assume that v 2 T Ji iff ffV (v) 2 ((Ti))ffS(J ), for i 2 f1; : : : ;
kg, and show that v 2 T J iff ffV (v) 2 ((T ))ffS (J ).

Suppose that v 2 T J , i.e., v = [[A1: v1; : : : ; Ah: vh]] with h * k and
vi 2 T Ji for i 2 f1; : : : ; kg. By induction hypothesis ffV (vi) 2 ((Ti))ffS(J
), for i 2 f1; : : : ; kg, and by definition of ffS , ffV (v) 2 RecTypeffS(J
), (ffV(v); ffV (vi)) 2 ((Ai))ffS(J ) for i 2 f1; : : : ; kg, and all roles
(A) corresponding to attribute names are functional. Therefore, ffV (v) 2
((T ))ffS (J ).

Conversely, suppose that d = ffV(v) 2 ((T ))ffS (J ). Then, for each i 2
f1; : : : ; kg there is exactly one di 2 Delta ffS(J ) such that (d; di)
2 ((Ai))ffS (J ), and moreover di 2 ((Ti))ffS(J ). By definition of ffS we
have v = [[A1: v1; : : : ; Ah: vh]], with h * k and vi = ffGamma 1V (di),
for i 2 f1; : : : ; kg. By induction hypothesis vi 2 T Ji , for i 2 f1; :
: : ; kg, and therefore v 2 (Record A1: T1; : : : ; Ak: Tk End)J .

The cases for T = Union T1; : : : ; Tk End and T = Set-of T 0 can be treated
analogously.

(2) Given a finite model I of (S) of depth m, we define a legal database
instance fiS (I) as follows:

ffl fiV is a function mapping every element of Delta Ijm into a distinct
element of VfiS(I) such

that the following conditions are satisfied:

- OfiS(I) ` VfiS(I) is the set of elements fiV (d) such that d 2 AbstractClassIjm.

229

Calvanese, Lenzerini, & Nardi - If d 2 RecTypeIjm , (d; di) 2 ((Ai))Ijm ,
for i 2 f1; : : : ; kg, and there is no

other individual d0 2 Delta Ijm and attribute A0 such that (d; d0) 2 ((A0))Ijm
, then fiV (d) = [[A1: fiV (d1); : : : ; Ak: fiV (dk)]].

- If d 2 SetTypeIjm, (d; di) 2 memberIjm, for i 2 f1; : : : ; kg, and there
is no

other individual d0 2 Delta Ijm such that (d; d0) 2 (member)Ijm , then fiV
(d) = ffiV (d1); : : : ; fiV (dk)g.

ffl For every class name C, ssfiS(I)(C) = ffiV (d) j d 2 ((C))Ijm g. ffl
aefiS(I) = f(o; v) j fiV (d1) = o; fiV (d2) = v; and (d1; d2) 2 valueIjm
g.

We first prove that for each concept (T ), which is the translation of a
type expression T of S, and each d 2 Delta Ijm, d 2 ((T ))Ijm if and only
if fiV (d) 2 T fiS(I). The proof is by induction on the structure of the
concept expression. Again for the inductive part we restrict our attention
to the case of record types.

Base case: T = C (i.e., (T ) is an atomic concept). If d 2 ((C))Ijm then
fiV (d) 2 CfiS(I), and vice-versa if o 2 CfiS(I) then fiGamma 1V (o) 2 ((C))Ijm
.

Inductive case: (T ) = RecType u 8(A1).(T1) u 9=1(A1) u Delta  Delta  Delta
u 8(Ak).(Tk) u 9=1(Ak) and T = Record A1: T1; : : : ; Ak: Tk End. We assume
that d 2 ((Ti))Ijm iff

fiV (d) 2 T fiS(I)i , for i 2 f1; : : : ; kg, and show that d 2 ((T ))Ijm
iff fiV (d) 2 T fiS(I).

Suppose that d 2 ((T ))Ijm . Then d 2 RecTypeIjm and for each i 2 f1; : :
: ; kg there is an individual di such that di 2 ((Ti))Ijm and (d; di) 2 ((Ai))Ijm
. By construction fiV (d) = [[A1: v1; : : : ; Ah: vh]] for some h * k. Moreover,
by induction hypothesis fiV(di) 2

T fiS(I)i and therefore fiV (d) 2 T fiS(I).

Conversely, suppose that fiV (d) 2 T fiS(I), i.e., fiV (d) = [[A1: v1; :
: : ; Ah: vh]] with h * k

and vi 2 T fiS(I)i for i 2 f1; : : : ; kg. By induction hypothesis di = fiGamma
1V (vi) 2 ((Ti))Ijm , for i 2 f1; : : : ; kg, and by definition of fiV ,
d 2 RecTypeIjm and (d; di) 2 ((Ai))Ijm , for i 2 f1; : : : ; kg. Since all
roles (A) corresponding to attribute names are functional, d 2 ((T ))Ijm
.

It remains to show that for each declaration

Class C is-a C1; : : : ; Cn type-is T

in DS , (a) CfiS(I) ` CfiS(I)i for each i 2 f1; : : : ; ng, and (b) aefiS(I)(CfiS(I))
` T fiS(I).

(a) follows from the fact that (S) contains the assertion (C) ._ (C1) u Delta
Delta  Delta  u (Cn) and from the definition of ssfiS(I).

(b) follows from what we have shown above and from the fact that Ijm still
satisfies the assertion (C) ._ AbstractClass u 8value.(T ). In fact, for
some d 2 ((C))I let d0 be the unique individual such that (d; d0) 2 valueI.
Since I is a model of (S), d0 2 ((T ))I . We argue that also d0 2 ((T ))Ijm
. If d0 is not part of a bad cycle in I, then I and Ijm coincide on the sub-structure
rooted at d0 and formed by the individuals reached via member and roles corresponding
to attributes, and we are done. Otherwise, in Ijm such sub-structure is expanded
into a finite tree. Since by construction the depth of this tree is at least
depth(T ), and the connections between individuals in I are preserved in
Ijm, it

follows that d0 2 ((T ))Ijm .

230

Unifying Class-Based Representation Formalisms The basic reasoning services
considered in object-oriented databases are subtyping (check whether a type
denotes a subset of another type in every legal instance) and type consistency
(check whether a type is consistent in a legal instance). Based on Proposition
5.9, we can show that these forms of reasoning are fully captured by finite
concept consistency and finite concept subsumption in aluni knowledge bases.

Theorem 5.10 Let S be an object-oriented schema, T; T 0 two type expressions
in S, and (S) the translation of S. Then the following holds:

1. T is consistent in S if and only if (S) 6j=f (T ) _ ?. 2. T is a subtype
of T 0 in S if and only if (S) j=f (T ) _ (T 0).

Proof. The proof is analogous to the proof of Theorem 4.9, but it makes use
of Proposition 5.9 instead of Proposition 4.8.

Again, the correspondence with aluni established by Theorem 5.10 allows us
to make use of the reasoning techniques developed for aluni to reason on
object-oriented schemas. Observe that reasoning in object-oriented models
is already PSPACE-hard (Bergamaschi & Nebel, 1994) and thus the known algorithms
are exponential. However, by resorting to aluni, it becomes possible to take
into account for reasoning also various extensions of the object-oriented
formalism. Such extensions are useful for conceptual modeling and have already
been proposed in the literature (Cattell & Barry, 1997). First of all, the
same considerations developed for the ER model with regard to the use of
arbitrary boolean constructs on classes can be applied also in the object-oriented
setting, which provides disjunction but does not admit any form of negation.
Additional features that can be added to object oriented models are inverses
of attributes, cardinality constraints on set-valued attributes, and more
general forms of restrictions on the values of attributes.

6. Related Work In this section we briefly discuss recent results on the
correspondence between class-based formalisms and on techniques for reasoning
in aluni and in class-based representation formalisms.

6.1 Relationships among Class-Based Formalisms In the past there have been
several attempts to establish relationships among class-based formalisms.
Bl"asius, Hedst"uck, and Rollinger (1990), Lenzerini, Nardi, and Simi (1991)
carry out a comparative analysis of class-based languages and attempt to
provide a unified view. The analysis makes it clear that several difficulties
arise in identifying a common framework for the formalisms developed in different
areas. Some recent papers address this problem. For example, an analysis
of the relationships between frame-based languages and types in programming
languages has been carried out by Borgida (1992), while Bergamaschi and Sartori
(1992), Piza, Schewe, and Schmidt (1992) use frame-based languages to enrich
the deductive capabilities of semantic and object-oriented data models.

231

Calvanese, Lenzerini, & Nardi Artale, Cesarini, and Soda (1996) study reasoning
in object-oriented data models by presenting a translation to DLs in the
style of the one discussed in Section 5. However, the proposed translation
is applicable only in the case where the shema contains no recursive class
declarations. This limitation is not present in the work by Bergamaschi and
Nebel (1994), where a formalism derived from DLs is used to model complex
objects and an algorithm for computing subsumption between classes is provided.

A recent survey on the application of DLs to the problem of data management
has been presented by Borgida (1995) . The application to the task of data
modeling of reasoning techniques derived from the correspondences presented
in Sections 4 and 5 is discussed in more detail by Calvanese, Lenzerini,
and Nardi (1998).

Recently, there have also been proposals to integrate the object-oriented
and the logic programming paradigms (Kifer & Wu, 1993; Kifer, Lausen, & Wu,
1995). These proposals are however not directly related to the present work,
since they aim at providing mechanisms for computing with structured objects,
rather than means for reasoning over a conceptual (object-oriented) representation
of the domain of interest.

6.2 Reasoning in aluni and in Class-Based Representation Formalisms aluni
is equipped with techniques to reason both with respect to unrestricted and
with respect to finite models. We briefly sketch the main ideas underlying
reasoning in both contexts. A detailed account of the reasoning techniques
has been carried out by Calvanese (1996c).

6.2.1 Unrestricted Model Reasoning We remind that reasoning on a knowledge
base with respect to unrestricted models amounts to check either concept
consistency, i.e., determine whether the knowledge base admits a (possibly
infinite) model in which a given concept has a nonempty extension, or concept
subsumption, i.e., determine whether the extension of one concept is contained
in the extension of another concept in every model (including the infinite
ones) of the knowledge base.

The method to reason in aluni with respect to unrestricted models exploits
a well known correspondence between DLs and Propositional Dynamic Logics
(PDLs) (Kozen & Tiuryn, 1990), which are a class of logics specifically designed
to reason about programs. The correspondence, which has first been pointed
out by Schild (1991), relies on a substantial similarity of the interpretative
structures of both formalisms, and allows one to exploit the reasoning techniques
developed for PDLs to reason in the corresponding DLs. In particular, since
ALUN I, the description language of aluni, includes the construct for inverse
roles, for the correspondence one has to resort to converse-PDL, a variant
of PDL that includes converse programs (Kozen & Tiuryn, 1990). However, because
of the presence of number restrictions in ALU N I which have no direct correspondence
in PDLs, we cannot rely on traditional techniques for reasoning in PDLs.
Recently, encoding techniques have been developed, which allow one to eliminate
number restrictions from a knowledge base while preserving concept consistency
and concept subsumption (De Giacomo & Lenzerini, 1994a). The encoding is
applicable to knowledge bases formulated in expressive variants of DLs, and
in particular it can be used to reduce unrestricted model reasoning on aluni
knowledge

232

Unifying Class-Based Representation Formalisms bases (both concept consistency
and concept subsumption) to deciding satisfiability of a formula of converse-PDL.
Reasoning in converse-PDL is decidable in EXPTIME (Kozen & Tiuryn, 1990),
and since the encoding is polynomial (De Giacomo & Lenzerini, 1994a) we obtain
an EXPTIME decision procedure for unrestricted concept consistency and concept
subsumption in aluni knowledge bases. A simplified form of the encoding,
which can be applied to decide unrestricted concept consistency in aluni
has also been presented by Calvanese et al. (1994).

6.2.2 Finite Model Reasoning We remind that reasoning on a knowledge base
with respect to finite models amounts to check either finite concept consistency
or finite concept subsumption, for which only the finite models of the knowledge
base must be considered.

For finite model reasoning, the techniques based on a reduction to reasoning
in PDLs are not applicable. Indeed, the PDL formula corresponding to an aluni
knowledge base contains constructs both for converse programs (corresponding
to inverse roles) and for functionality of direct and inverse programs, and
thus is a formula of a variant of PDL which does not have the finite model
property (Vardi, 1985). However, after encoding functionality, one obtains
a converse-PDL formula, and since converse-PDL has the finite model property
(Fischer & Ladner, 1979), this formula is satisfiable if and only if it is
finitely satisfiable. This shows that the encoding of number restrictions
(and in particular the encoding of functionality), while preserving unrestricted
satisfiability does not preserve finite satisfiability (De Giacomo & Lenzerini,
1994a).

For finite model reasoning in aluni one can adopt a different technique,
which is based on the idea of separating the reasoning process in two distinct
phases (see Calvanese, 1996c, for full details). The first phase deals with
all constructs except number restrictions, and builds an "expanded knowledge
base" in which these constructs are embedded implicitly in the concepts and
roles. In the second phase the assertions involving number restrictions are
used to derive from this expanded knowledge base a system of linear inequalities.
The system is defined in such a way that its solutions of a certain type
(acceptable solutions) are directly related to the finite models of the original
knowledge base. In particular, from each acceptable solution one can directly
deduce the cardinalities of the extensions of all concepts and roles in a
possible finite model. The proposed method allows one to establish for aluni
EXPTIME decidability for finite concept consistency and for special cases
of finite concept subsumption. By resorting to a more complicated encoding
one can obtain a 2EXPTIME decision procedure for finite concept subsumption
in aluni in general (Calvanese, 1996a, 1996c).

Reasoning with respect to finite models has also been investigated in the
context of dependency theory in databases. As shown by Casanova, Fagin, and
Papadimitriou (1984) for the relational model, when functional and inclusion
dependencies interact, the dependency implication problem in the finite case
differs from the one in the unrestricted case. While the implication problem
for arbitrary functional and inclusion dependencies is undecidable (Chandra
& Vardi, 1985; Mitchell, 1983), for functional and unary inclusion dependencies
it is solvable in polynomial time, both in the finite and the unrestricted
case (Cosmadakis et al., 1990).

233

Calvanese, Lenzerini, & Nardi Consistency with respect to finite models of
schemata expressed in an enriched EntityRelationship model with cardinality
constraints has been shown decidable in polynomial time by Lenzerini and
Nobili (1990). Calvanese and Lenzerini (1994b) extend the decidability result
to include also ISA relationships, and Calvanese and Lenzerini (1994a) show
EXPTIME decidability of reasoning in an expressive object-oriented model.
An algorithm for computing a refinement ordering for types (the analogue
to a concept hierarchy) in the framework of the O2 object oriented model
in discussed by Lecluse and Richard (1989).

Reasoning in the strict sublanguage of aluni obtained by omitting inverse
roles and number restrictions is already EXPTIME-hard (Calvanese, 1996b).
Therefore, the known algorithms for deciding unrestricted concept consistency
and subsumption and finite concept consistency are essentially optimal.

7. Conclusions We have presented a unified framework for representing information
about class structures and reasoning about them. We have pursued this goal
by looking at various class-based formalisms proposed in different fields
of computer science, namely frame based systems used in knowledge representation,
and semantic and object-oriented data models used in databases, and rephrasing
them in the framework of description logics. The resulting description logic,
called aluni includes a combination of constructs that was not addressed
before, although all of the constructs had previously been considered separately.

The major achievement of the paper is the demonstration that class-based
formalisms can be given a precise characterization by means of a powerful
fragment of first-order logic, which thus can be regarded as the essential
core of the class-based representation formalisms belonging to all three
families mentioned above. This has several consequences.

First of all, any of the formalisms considered in the paper can be enriched
with constructs originating from other formalisms and treated in the general
framework. In this sense, the work reported here not only provides a common
powerful representation formalism, but may also contribute to significant
developments for the languages belonging to all the three families. For example,
the usage of inverse roles in concept languages greatly enhances the expressivity
of roles, while the combination of ISA, number restrictions, and union enriches
the reasoning capabilities available in semantic data models.

Secondly, the comparison of class-based formalisms from the fields of knowledge
representation and conceptual data modeling makes it feasible to address
the development of reasoning tools to support conceptual modeling (Calvanese
et al., 1998). In fact, reasoning capabilities become especially important
in complex scenarios such as those arising in heterogenous database applications
and Data Warehousing. This line of work was among the motivations for developing
systems based on expressive description logics (Horrocks, 1998; Horrocks
& Patel-Schneider, 1999), and has lead to further extending the language
of description logics to support Information Integration and, more specifically,
the conceptual modeling of Data Warehouses (Calvanese, De Giacomo, Lenzerini,
Nardi, & Rosati, 1998).

234

Unifying Class-Based Representation Formalisms References Abiteboul, S.,
Kanellakis, P., Ramaswamy, S., & Waller, E. (1992). Method schemas. Tech.

rep. CS-92-33, Brown University. An earlier version appeared in Proc. of
the 9th Symp. on Principles of Database Systems PODS-90.

Abiteboul, S., & Kanellakis, P. (1989). Object identity as a query language
primitive. In

Proceedings of the ACM SIGMOD International Conference on Management of Data,
pp. 159-173.

Abrial, J. R. (1974). Data semantics. In Klimbie, J. W., & Koffeman, K. L.
(Eds.), Data

Base Management, pp. 1-59. North-Holland Publ. Co., Amsterdam.

Albano, A., Ghelli, G., & Orsini, R. (1991). A relationship mechanism for
strongly typed

Object-Oriented database programming languages. In Proceedings of the Seventeenth
International Conference on Very Large Data Bases (VLDB'91), pp. 565-575
Barcelona.

Artale, A., Cesarini, F., & Soda, G. (1996). Describing database objects
in a concept

language environment. IEEE Transactions on Knowledge and Data Engineering,
8 (2), 345-351.

Atzeni, P., & Parker Jr., D. S. (1986). Formal properties of net-based knowledge
representation schemes. In Proceedings of the Second IEEE International Conference
on Data Engineering (ICDE'86), pp. 700-706 Los Angeles.

Baader, F. (1991). Augmenting concept languages by transitive closure of
roles: An alternative to terminological cycles. In Proceedings of the Twelfth
International Joint Conference on Artificial Intelligence (IJCAI'91) Sydney,
Australia.

Baader, F. (1996). Using automata theory for characterizing the semantics
of terminological

cycles. Annals of Mathematics and Artificial Intelligence, 18, 175-219.

Batini, C., Ceri, S., & Navathe, S. B. (1992). Conceptual Database Design,
an EntityRelationship Approach. Benjamin and Cummings Publ. Co., Menlo Park,
California.

Bergamaschi, S., & Nebel, B. (1994). Acquisition and validation of complex
object database

schemata supporting multiple inheritance. Applied Intelligence, 4 (2), 185-203.

Bergamaschi, S., & Sartori, C. (1992). On taxonomic reasoning in conceptual
design. ACM

Transactions on Database Systems, 17 (3), 385-422.

Bl"asius, K. H., Hedst"uck, U., & Rollinger, C.-R. (Eds.). (1990). Sorts
and Types in Artificial

Intelligence, Vol. 418 of Lecture Notes in Artificial Intelligence. Springer-Verlag.

Borgida, A. (1992). From type systems to knowledge representation: Natural
semantics

specifications for description logics. Journal of Intelligent and Cooperative
Information Systems, 1 (1), 93-126.

Borgida, A. (1995). Description logics in data management. IEEE Transactions
on Knowledge and Data Engineering, 7 (5), 671-682.

235

Calvanese, Lenzerini, & Nardi Borgida, A. (1996). On the relative expressiveness
of description logics and predicate logics.

Artificial Intelligence, 82, 353-367.

Borgida, A., & Weddell, G. E. (1997). Adding functional dependencies to description
logics.

In Proceedings of the Fifth International Conference on Deductive and Object-Oriented
Databases (DOOD'97).

Brachman, R. J., & Levesque, H. J. (1984). The tractability of subsumption
in frame-based

description languages. In Proceedings of the Fourth National Conference on
Artificial Intelligence (AAAI'84), pp. 34-37.

Brachman, R. J., & Levesque, H. J. (Eds.). (1985). Readings in Knowledge
Representation.

Morgan Kaufmann, Los Altos.

Brachman, R. J., McGuinness, D. L., Patel-Schneider, P. F., Alperin Resnick,
L., & Borgida,

A. (1991). Living with CLASSIC: When and how to use a KL-ONE-like language.
In Sowa, J. F. (Ed.), Principles of Semantic Networks, pp. 401-456. Morgan
Kaufmann, Los Altos.

Bresciani, P., Franconi, E., & Tessaris, S. (1995). Implementing and testing
expressive

description logics: Preliminary report. In Borgida, A., Lenzerini, M., Nardi,
D., & Nebel, B. (Eds.), Working Notes of the 1995 Description Logics Workshop,
Technical Report, RAP 07.95, Dipartimento di Informatica e Sistemistica,
Universit`a di Roma "La Sapienza", pp. 131-139 Rome (Italy).

Buchheit, M., Donini, F. M., Nutt, W., & Schaerf, A. (1998). A refined architecture
for

terminological systems: Terminology = schema + views. Artificial Intelligence,
99 (2), 209-260.

Buchheit, M., Donini, F. M., & Schaerf, A. (1993). Decidable reasoning in
terminological

knowledge representation systems. Journal of Artificial Intelligence Research,
1, 109- 138.

Calvanese, D. (1996a). Finite model reasoning in description logics. In Aiello,
L. C., Doyle,

J., & Shapiro, S. C. (Eds.), Proceedings of the Fifth International Conference
on the Principles of Knowledge Representation and Reasoning (KR'96), pp.
292-303. Morgan Kaufmann, Los Altos.

Calvanese, D. (1996b). Reasoning with inclusion axioms in description logics:
Algorithms

and complexity. In Wahlster, W. (Ed.), Proceedings of the Twelfth European
Conference on Artificial Intelligence (ECAI'96), pp. 303-307. John Wiley
& Sons.

Calvanese, D. (1996c). Unrestricted and Finite Model Reasoning in ClassBased
Representation Formalisms. Ph.D. thesis, Dipartimento di Informatica e Sistemistica,
Universit`a di Roma "La Sapienza". Available at http://www.dis.uniroma1.it/pub/calvanes/thesis.ps.gz.

Calvanese, D., De Giacomo, G., Lenzerini, M., Nardi, D., & Rosati, R. (1998).
Description

logic framework for information integration. In Proceedings of the Sixth
International

236

Unifying Class-Based Representation Formalisms Conference on Principles of
Knowledge Representation and Reasoning (KR'98), pp. 2-13.

Calvanese, D., & Lenzerini, M. (1994a). Making object-oriented schemas more
expressive.

In Proceedings of the Thirteenth ACM SIGACT SIGMOD SIGART Symposium on Principles
of Database Systems (PODS'94), pp. 243-254 Minneapolis. ACM Press and Addison
Wesley.

Calvanese, D., & Lenzerini, M. (1994b). On the interaction between ISA and
cardinality

constraints. In Proceedings of the Tenth IEEE International Conference on
Data Engineering (ICDE'94), pp. 204-213 Houston (Texas). IEEE Computer Society
Press.

Calvanese, D., Lenzerini, M., & Nardi, D. (1994). A unified framework for
class based representation formalisms. In Doyle, J., Sandewall, E., & Torasso,
P. (Eds.), Proceedings of the Fourth International Conference on the Principles
of Knowledge Representation and Reasoning (KR'94), pp. 109-120 Bonn. Morgan
Kaufmann, Los Altos.

Calvanese, D., Lenzerini, M., & Nardi, D. (1998). Description logics for
conceptual data

modeling. In Chomicki, J., & Saake, G. (Eds.), Logics for Databases and Information
Systems, pp. 229-264. Kluwer Academic Publisher.

Casanova, M. A., Fagin, R., & Papadimitriou, C. H. (1984). Inclusion dependencies
and

their interaction with functional dependencies. Journal of Computer and System
Sciences, 28 (1), 29-59.

Cattell, R. G. G. (Ed.). (1994). The Object Database Standard: ODMG-93. Morgan
Kaufmann, Los Altos. Release 1.1.

Cattell, R. G. G., & Barry, D. K. (Eds.). (1997). The Object Database Standard:
ODMG

2.0. Morgan Kaufmann, Los Altos.

Chandra, A. K., & Vardi, M. Y. (1985). The implication problem for functional
and inclusion

dependencies is undecidable. SIAM Journal on Computing, 14 (3), 671-677.

Chen, P. P. (1976). The Entity-Relationship model: Toward a unified view
of data. ACM

Transactions on Database Systems, 1 (1), 9-36.

Cosmadakis, S. S., & Kanellakis, P. C. (1986). Functional and inclusion dependencies
- A

graph theoretical approach. In Kanellakis, P. C., & Preparata, F. P. (Eds.),
Advances in Computing Research, Vol. 3, pp. 163-184. JAI Press.

Cosmadakis, S. S., Kanellakis, P. C., & Vardi, M. (1990). Polynomial-time
implication

problems for unary inclusion dependencies. Journal of the ACM, 37 (1), 15-46.

De Giacomo, G., & Lenzerini, M. (1994a). Boosting the correspondence between
description logics and propositional dynamic logics. In Proceedings of the
Twelfth National Conference on Artificial Intelligence (AAAI'94), pp. 205-212.
AAAI Press/The MIT Press.

237

Calvanese, Lenzerini, & Nardi De Giacomo, G., & Lenzerini, M. (1994b). Concept
language with number restrictions and

fixpoints, and its relationship with _-calculus. In Proceedings of the Eleventh
European Conference on Artificial Intelligence (ECAI'94), pp. 411-415.

Di Battista, G., & Lenzerini, M. (1993). Deductive entity-relationship modeling.
IEEE

Transactions on Knowledge and Data Engineering, 5 (3), 439-450.

Donini, F. M., Lenzerini, M., Nardi, D., & Nutt, W. (1997). The complexity
of concept

languages. Information and Computation, 134, 1-58.

Donini, F. M., Lenzerini, M., Nardi, D., Nutt, W., & Schaerf, A. (1994).
Queries, rules and

definitions. In Foundations of Knowledge Representation and Reasoning. SpringerVerlag.

Donini, F. M., Lenzerini, M., Nardi, D., & Schaerf, A. (1996). Reasoning
in description

logics. In Brewka, G. (Ed.), Principles of Knowledge Representation, Studies
in Logic, Language and Information, pp. 193-238. CSLI Publications.

Donini, F. M., Nardi, D., & Rosati, R. (1995). Non-first-order features in
concept languages. In Gori, M., & Soda, G. (Eds.), Proceedings of the Fourth
Conference of the Italian Association for Artificial Intelligence (AI*IA'95),
Vol. 992 of Lecture Notes in Artificial Intelligence, pp. 91-102. Springer-Verlag.

Ferg, S. (1991). Cardinality concepts in entity-relationship modeling. In
Proceedings of the

Tenth International Conference on the Entity-Relationship Approach (ER'91),
pp. 1-30.

Fikes, R., & Kehler, T. (1985). The role of frame-based representation in
reasoning. Communications of the ACM, 28 (9), 904-920.

Fischer, M. J., & Ladner, R. E. (1979). Propositional dynamic logic of regular
programs.

Journal of Computer and System Sciences, 18, 194-211.

Grant, J., & Minker, J. (1984). Numerical dependencies. In Gallaire, H.,
Minker, J., &

Nicolas, J.-M. (Eds.), Advances in Database Theory II. Plenum Publ. Co.,
New York.

Hayes, P. J. (1979). The logic of frames. In Metzing, D. (Ed.), Frame Conceptions
and Text

Understanding, pp. 46-61. Walter de Gruyter and Co. Republished in (Brachman
& Levesque, 1985).

Horrocks, I. (1998). Using an expressive description logic: FaCT or fiction?.
In Proceedings

of the Sixth International Conference on Principles of Knowledge Representation
and Reasoning (KR'98), pp. 636-647.

Horrocks, I., & Patel-Schneider, P. F. (1999). Optimizing description logic
subsumption.

Journal of Logic and Computation, 9 (3), 267-293.

Hull, R. B., & King, R. (1987). Semantic database modelling: Survey, applications
and

research issues. ACM Computing Surveys, 19 (3), 201-260.

238

Unifying Class-Based Representation Formalisms Karp, P. D. (1992). The design
space of knowledge representation systems. Tech. rep. SRI

AI Technical Note 520, SRI International, Menlo Park, CA.

Karp, P. D., Myers, K. L., & Gruber, T. (1995). The generic frame protocol.
In Proceedings

of the Fourteenth International Joint Conference on Artificial Intelligence
(IJCAI'95), Vol. A, pp. 768-774 Montreal, Canada.

Kifer, M., Lausen, G., & Wu, J. (1995). Logical foundations of Object-Oriented
and framebased languages. Journal of the ACM, 42 (4), 741-843.

Kifer, M., & Wu, J. (1993). A logic for programming with complex objects.
Journal of

Computer and System Sciences, 47, 77-120.

Kim, W. (1990). Introduction to Object-Oriented Databases. The MIT Press.
Kim, W., & Lochovsky, F. H. (Eds.). (1989). Object-Oriented Concepts, Databases,
and

Applications. ACM Press and Addison Wesley, New York.

Kozen, D., & Tiuryn, J. (1990). Logics of programs. In van Leeuwen, J. (Ed.),
Handbook of

Theoretical Computer Science - Formal Models and Semantics, pp. 789-840.
Elsevier Science Publishers (North-Holland), Amsterdam.

Lecluse, C., & Richard, P. (1989). Modeling complex structures in object-oriented
databases.

In Proceedings of the Eighth ACM SIGACT SIGMOD SIGART Symposium on Principles
of Database Systems (PODS'89), pp. 362-369.

Lehmann, F. (Ed.). (1992). Semantic Networks in Artificial Intelligence.
Pergamon Press,

Oxford.

Lenzerini, M., Nardi, D., & Simi, M. (Eds.). (1991). Inheritance Hierarchies
in Knowledge

Representation and Programming Languages. John Wiley & Sons, Chichester.

Lenzerini, M., & Nobili, P. (1990). On the satisfiability of dependency constraints
in entityrelationship schemata. Information Systems, 15 (4), 453-461.

Mitchell, J. C. (1983). The implication problem for functional and inclusion
dependencies.

Information and Control, 56, 154-173.

Motschnig-Pitrik, R., & Mylopoulous, J. (1992). Classes and instances. Journal
of Intelligent and Cooperative Information Systems, 1 (1).

Nebel, B. (1991). Terminological cycles: Semantics and computational properties.
In Sowa,

J. F. (Ed.), Principles of Semantic Networks, pp. 331-361. Morgan Kaufmann,
Los Altos.

Piza, B., Schewe, K.-D., & Schmidt, J. W. (1992). Term subsumption with type
constructors. In Yesha, Y. (Ed.), Proceedings of the International Conference
on Information and Knowledge Management (CIKM'92), pp. 449-456 Baltimore.

239

Calvanese, Lenzerini, & Nardi Schild, K. (1991). A correspondence theory
for terminological logics: Preliminary report.

In Proceedings of the Twelfth International Joint Conference on Artificial
Intelligence (IJCAI'91), pp. 466-471 Sydney, Australia.

Schild, K. (1994). Terminological cycles and the propositional _-calculus.
In Doyle, J.,

Sandewall, E., & Torasso, P. (Eds.), Proceedings of the Fourth International
Conference on the Principles of Knowledge Representation and Reasoning (KR'94),
pp. 509-520 Bonn. Morgan Kaufmann, Los Altos.

Schmidt-Schauss, M., & Smolka, G. (1991). Attributive concept descriptions
with complements. Artificial Intelligence, 48 (1), 1-26.

Sowa, J. F. (Ed.). (1991). Principles of Semantic Networks. Morgan Kaufmann,
Los Altos. Teorey, T. J. (1989). Database Modeling and Design: The Entity-Relationship
Approach.

Morgan Kaufmann, Los Altos.

Thalheim, B. (1992). Fundamentals of cardinality constraints. In Pernoul,
G., & Tjoa,

A. M. (Eds.), Proceedings of the Eleventh International Conference on the
EntityRelationship Approach (ER'92), pp. 7-23. Springer-Verlag.

Thalheim, B. (1993). Fundamentals of the Entity Relationship Model. Springer-Verlag.
Vardi, M. Y. (1985). The taming of converse: Reasoning about two-way computations.

In Parikh, R. (Ed.), Proc. of the 4th Workshop on Logics of Programs, Vol.
193 of Lecture Notes in Computer Science, pp. 413-424. Springer-Verlag.

Woods, W. A., & Schmolze, J. G. (1992). The KL-ONE family. In Lehmann, F.
W. (Ed.),

Semantic Networks in Artificial Intelligence, pp. 133-178. Pergamon Press.
Published as a special issue of Computers & Mathematics with Applications,
Volume 23, Number 2-9.

Ye, X., Parent, C., & Spaccapietra, S. (1994). Cardinality consistency of
derived objects in

DOOD systems. In Loucopoulos, P. (Ed.), Proceedings of the Thirteenth International
Conference on the Entity-Relationship Approach (ER'94), Vol. 881 of Lecture
Notes in Computer Science, pp. 278-295 Manchester (UK). Springer-Verlag.

240