The logical data model.
We propose an object-oriented data model that generalizes the relational, hierarchical, and network models. A database scheme in this model is a directed graph, whose leaves represent data and whose internal nodes represent connections among the data. Instances are constructed from objects, which have separate names and values. We define a logic for the model, and describe a nonprocedural query language that is based on the logic. We also describe an algebraic query language and show that it is equivalent to the logical language.
Introduction
Research in database theory during the 1970's and the early 1980's has focused
mainly on the relational model [Cod70], due to its elegance and mathematical
simplicity. This very simplicity, however, has gradually been recognized
as one of the major disadvantages of the relational model: it forces
the stored data to have a flat structure that real data does not always have
[SS77, Cod79]. This has motivated a great deal of research during the past
decade on structured data models: the so-called semantic data models (cf.
[?, ?]), nested relations (cf. [?, ?]), and complex objects (cf. The reader
is referred to [?, ?, ?] for excellent surveys.
Two works that we found in particular inspiring are by Jacobs [Jac79,
Jac82] and by Hull and Yap [HY82]. Jacobs describes "database logic," a
mathematical model for databases that claims to generalize all three principal
data models. Hull and Yap [HY82] describe the "format model," which
generalizes the relational and hierarchical models. In the format model,
database schemes are viewed as trees, in which each leaf represents data,
and each internal node represents some connection among the data.
Both these models are unsatisfactory in their ability to restructure data,
i.e., the ability to query the database. While Hull and Yap ignore the issue
of a data manipulation language, Jacobs' treatment is an overkill-his query
language enables one to write noncomputable queries [Var83].
Furthermore, both approaches fail to model a significant aspect of hierarchical
and network database management systems, which is the ability to use
virtual records. Virtual records are essentially pointers to physical records,
and they are used to avoid redundancy in the database [Ull82]. Note that
virtual records introduce cyclicity not only in the schema level but also at
the instance level.
In the model we propose here, a database scheme is an arbitrary directed
graph. As in the format model, leaves (i.e., nodes with no outgoing edges)
represent data, and internal nodes represent connections among the data.
While it is not hard to model cyclicity at the schema level, it is not quite
apparent how to do it at the instance level, without running into cyclic defini-
tions. Our solution is to distinguish between object names and object values,
or, equivalently, between the address space and the data space. This distinction
goes back to Codd's notions of surrogates [Cod79]. Thus, instances in
our model consist of objects, which have separate names and values. This
enables us to give semantics to instances in a well-defined way.
A data model consists of several components [TL82]. The first is the
database structure mentioned above, which describes the static portion of
the database. The second component is a way to specify integrity constraints
on the database, that restrict the allowed instances of the schema. We shall
describe a logic in which integrity constraints can be specified. Our logic
is inspired by Jacob's database logic [Jac82], but unlike database logic, our
logic is effective. That is, given a database and a sentence in the logic, one
can test effectively whether the sentence is true in the database or not.
The third component is a way to restructure data, in order to describe
user views, queries, etc. We describe two such mechanisms, a logical, i.e.,
nonprocedural, query language and an algebraic, i.e., procedural, query language
that are analogous to Codd's relational calculus and relational algebra,
and we prove that these two languages are equivalent. These languages have
a novel feature: not only can they access a nonflat data structure, e.g., a
hierarchy, but the answers they produce do not have to be flat either. Thus,
the language really does have the ability to restructure data and not only to
retrieve it, as opposed to the other approaches cited above.
2. Introduction to the Logical Data Model
The logical data model (LDM) is a generalization of Hull and Yap's format
model [HY82]. The format model fails to model an important part of network
and hierarchical database systems, namely the ability to use virtual records.
We model this by introducing cyclicity into the database schemas. An LDM
schema is a labeled directed multigraph. 1 Each node has a particular type.
The leaves of the schema (i.e., nodes with no outgoing edges) are all of the
basic type, denoted graphically by . The instance of each node contains
the data values stored in the database. Each interior node has one of the
following types:
1. Product, denoted graphically by h
\Theta . The domain of such a node is the
Cartesian product of the domains of its children.
2. Power, denoted graphically by h
. Such a node has exactly one child.
1 In a multigraph one can have more than one edge between two nodes.
The domain of such a node is the set of all finite subsets of the domain
of its child.
3. Union, denoted graphically by h
[ . The domain of such a node is the
disjoint union of the domains of its children.
Person Parent
Rehoboam Solomon
Solomon David
Solomon Batsheba
David Jesse

Figure

1: The Person-Parent
relation
\Theta

Figure

2: The Person-Parent
relation as an LDM schema
Example 1: Fig. 1 shows a genealogy database as a relation. We can represent
the structure of this relation by the LDM schema in Fig. 2. It consists
of two nodes u and v of type that correspond to the Person and Parent
attributes respectively, and one node w of type h
\Theta that contains pairs of
related attributes.
For the moment, an instance I of an LDM schema will be an assignment
to each node u of a set I(u) of values from the corresponding domain. An
instance corresponding to the data in Fig. 1 consists of the following assignments

Person
oe

Figure

3: The genealogy as a
network

Figure

4: LDM schema corresponding
to Fig. 3
Example 2: The genealogy could be represented by the network in Fig. 3.
In this network there are two record types, Person containing the names of
the people in the database, and a dummy record PP. There are two links
(sets) that connect each dummy record to a person and his parents.
The idea behind the mapping from the network to the LDM schema in
Fig. 4 is as follows. Each record type R i is mapped into a product node v R i
For each field of R i , v R i
has a child of type . For each link (set) in the
network with R i as a member, let R j be the owner of the link. Then v R j
is
a child of v R i
In Fig. 4, w is v PP and v is v Person . u corresponds to the field of the Person
record, i.e., the person's name, and the two arcs from w to v correspond to
the two links.
If the network had the same contents as the relation in Fig. 1, the corresponding
instance of the LDM schema in Fig. 4 would be
Virtual
Person
Person

Figure

5: The genealogy as a
hierarchy

Figure

corresponding
to the hierarchy
Example 3: Fig. 5 shows a hierarchical representation of the genealogy. In
this hierarchy, each Person record is related to the linked list of his parents.
Even though the hierarchical model uses linked lists, this is really just a
matter of the implementation. Intuitively, the user should see only the connection
between a person and the set of his parents. We therefore map each
record type R i into a product node v R i
as we did for the network model, with
a child of type corresponding to each of R i 's fields. However, if R i is a
member of the link (R i ; R j ), then instead of connecting v R i
to v R j
directly, we
connect them through a node of type
. The corresponding LDM schema
is then the cyclic schema in Fig. 6.
When we have cyclic schemas, such as this one, we cannot define an
instance in the same way. Writing down the instance, in this example, is
very complicated, and in general, when the data as well as the schema is
cyclic, we cannot write it down at all. This is similar to one of the problems
with Jacobs' database logic. The mathematical theory we develop to deal
with this problem is closely related to the non-well-founded sets of [Acz85].
Our approach to defining an instance of a schema is to separate the concepts
of object name and object value. Intuitively, an object name is an address
and the object value is the content of that address. An instance I then
consists of:
1. an assignment of a set I(u) of object names to each node u of the
schema, and
2. an assignment of an object value val(l) to each name l in I(u).
The names are taken from a fixed infinite set L which will usually be the
set of natural numbers. Values are taken from a fixed infinite set D of data
values, or are built up from object names.
We now show what some of the instances in the previous examples look
like when we use names and values.
Example 4: The relational instance in Example 1 consists of the following
assignment of names to nodes.
and
We then assign a value val(l) to each of these names. This assignment is
shown in Fig. 7.
l val(l)
3 David
l val(l)
6 Batsheba
7 Jesse
l val(l)
9 (2; 5)

Figure

7: Instance of the LDM schema that corresponds to a relation
Example 5: In Fig. 8 we show the instance that corresponds to the hierarchy
of Example 3.
l val(l)
3 David
5 Jesse
l val(l)
9 (4;
l val(l)

Figure

8: Instance of the LDM schema that corresponds to a hierarchy
3. Formal Description of the Logical Data Model
Definition 1: A schema is a tuple
1. (V; E) is a directed multigraph.
2. ! is a total order on E.
3. - is a function from V to the set of types f ;
[ g, that satisfies
the following conditions (see Fig.
(a) is a leaf.
(b) If
, then v has exactly one child.
(c) If
then the children of v are distinct nodes (if
\Theta ,
however, there can be multiple edges from v to a node w).
The order on the edges is used to induce an order on the components
of tuples. -(v) is called the type of v. For readability, we use the following
abbreviations
1.
w) is an abbreviation for
and its child is w."
2. (a)
n) is an abbreviation for
\Theta and v has n
children."
s
s
s
s
s

Figure

9: Nodes in LDM schemas
is an abbreviation for
\Theta , there
are exactly n edges e 1
, . , e n with tail v, these edges are in the
their heads are v 1
, . , v n ."
3. (a)
n) is an abbreviation for
[ and v has n
children."
is an abbreviation for
[ , there
are exactly n edges e 1
, . , e n with tail v, these edges are in the
their heads are v 1
, . , v n ."
We are really overloading the symbol -, but in practice this will not cause
any confusion. Some other abbreviations that we use include referring to
elements of V and E as nodes and edges, respectively, of S, and referring
to ! as an order on the children of a node of S. We shall ignore the order
when it is clear from the context, and we shall often refer to a schema as
An instance of S consists of two parts: An assignment of a set of object
names to each node of S, and an assignment of an object value to each object
name.
Proviso: We assume a fixed infinite set L of object names and a fixed infinite
set D of data values.
Definition 2: An instance of S is a tuple I = hI; vali that satisfies the
is an assignment of sets of object names to nodes. We
require that I(v) and I(w) be disjoint whenever v and w are distinct
nodes of S.
2. val is a mapping with domain [ v2V I(v), i.e., from the set of all the
names that are in the instance. The mapping val must satisfy:
(a) If -(v) = and l 2 I(v), then val(l) is a member of the set D of
data values.
(b) If
then val(l) is a tuple
(l such that for each i, 1 - i - n, l i is an element of
(c) If
; w) and l 2 I(v), then val(l) is a finite subset of
I(w).
(d) If
Definition 3: A finite instance of S is an instance I = hI; vali of S such
that for each node v of S, I(v) is finite.
We shall be interested here mostly in finite instances, since these correspond
to real databases. If l is in [ v2V I(v), we say that it is a name in I,
and val(l) is called its value. The set [ v2V val[I(v)] is called the set of values
in I.
Definition 4: Let I be an instance of the schema S, and let v be a node of
S of type (
l be any name in I(v). If 1
will be the i th component of val(l). We shall also use the notation
(l) for this component, whenever this does not result in any ambiguity.
The following definition says when it is meaningful to compare two names,
i.e., if v and w are nodes of S, l 1
2 I(w), is it possible for l 1
and l 2
to have the same value?
Definition 5: We say that two nodes v and w in a schema S are similar
iff they are of the same type and have the same children, i.e., if one of the
following holds:
1.
2. For some node u,
3. For some n and nodes u 1
4. For some n and nodes u
A query on an LDM schema S will involve the addition of some nodes to
S. For this we need the following definitions.
Definition -i be a schema. S is an
extension of S iff
1.
2. (a)
(b) If (v
is in V 0 , i.e. all new edges are either
between new nodes, or from a new node to a node in V .
3. conservative extension of !.
4. - conservative extension of -.
The intuition behind (1) and (2) is that the schema S 0 adds some extra
nodes adds some edges E) to E, but it does not
change the schema S, i.e., it does not add edges between nodes in V , or from
nodes in V to new nodes.
be an extension of S. We define an extension of I to an instance
of S 0 as follows.
Definition 7: Let S 0 be an extension of S, and let I = hI; vali be an instance
of S. We say that an instance I is an extension of I to S 0 iff
1. For all v in V , I 0
2. If v is a node of S and l 2 I(v), then val 0
The proof of the following lemma is straightforward.
Lemma 1: Let S 0 be an extension of S, and let I 0 be an instance of S 0 . Then
there is a unique instance I of S such that I 0 is the extension of I to S 0 . This
instance is called the restriction of I 0 to S.
We conclude this section with a definition of isomorphism. Two instances
are isomorphic if they are essentially the same, i.e., if they differ only by
renaming. As we shall want to show that the result of a query is well-defined
up to isomorphism, we give a stronger definition of isomorphism. Let I be
an instance of S, let S 0 be an extension of S and let I 1
and I 2
be extensions
of I to S 0 . We shall say that I 1
and I 2
are isomorphic relative to S, if there
is an isomorphism between I 1
and I 2
that leaves the objects of I fixed. In
the case of a query, this means that an isomorphism relative to the database
leaves the contents of the database fixed.
Definition 8: Let S 0 be an extension of S and let I = hI; vali be an instance
of S. Let I 1
i be two extensions of I to S 0 . We
say that I 1
and I 2
are isomorphic relative to S iff there is a mapping
g:
I 1
(v) 1-1
\Gamma! onto
I 2
(v)
such that
1. For each node v of S, g is the identity on I(v).
2. For each node v of S 0 , g maps I 1
(v) onto I 2
(v).
3. If v is a node of S 0 and l 2 I 1
(v), then
(a) If v is of type , then val 2
(l).
(b) If v is of type (
val 2
val 1
(l)
val 1
(l)
(c) If v is of type
(l)).
(d) If v is of type
, then g[val 2
[g(l)].
As a special case of this definition we get the definition of ordinary isomorphism

Definition 9: Let I 1
i be instances of S. We
say that I 1
and I 2
are isomorphic iff they are isomorphic relative to the empty
schema, i.e., the schema with
4. LDM Logic
In this section we define the LDM logic. The logic is similar to the relational
tuple calculus, and will be used as part of the logical query language. The
logic can also be used to specify integrity constraints on LDM schemas, and
to define views. Throughout this section will be a fixed schema,
and I = hI; vali a fixed instance of S.
Each variable in the logic has a fixed sort, where the sorts are the elements
of V . The sorts define the domains over which the variables range. For
example, if x is a variable of sort v, then x ranges over I(v). The analogue
to this in the relational calculus is a tuple variable that ranges over a specific
relation. We shall usually write a variable with its sort as a subscript, e.g.,
x v . Variables with different subscripts denote distinct variables, so that x u is
a different variable from x v . Even though variables range over object names,
we think of them as ranging over objects. Thus, we shall refer to "the name
of x v " and to "the value of x v ".
Definition 10: The atomic formulas over S are the following:
1. x v - t y w , where w is a node of type
\Theta and v is its t th child.
2. x v ae y w , where w is a node of type
[ and v is one of its children.
3. x v 2 y w , where w is of type (
4. x
5. x and w are similar nodes.
d, where d is a data element in D, and v is of type .
The atomic formula x v - t y w means that the name of x v is the t th component
of the value of y w . Note that we have to mention which component of w
we are referring to, since there may be multiple edges from w to v. However,
we shall also write x v - y w when this is unambiguous. The atomic formula
means that the value of y w is x v . Since there is only one edge from
w to v, we use ae rather than ae t . The atomic formula x v 2 y w means that x v
is a member of the value of y w .
There are several kinds of equality. The atomic formula x means
that the names of x v and y v are equal. Since I(v) and I(w) are disjoint
whenever v 6= w, we do not need atomic formulas of the form x
means that the values of x v and y w are
equal. This is meaningful only when v and w are similar nodes. Finally, the
atomic formula x means that the data value of x v is equal to the data
element d.
Definition 11: A well-formed LDM formula over a schema S is:
1. An atomic formula
2. OE 1
, where OE 1
and OE 2
are well-formed formulas.
3.
, where OE 1
is a well-formed formula.
4. (8x v )OE 1
, where OE 1
is a well-formed formula.
The free variables of OE are defined in the same way as in first-order logic.
We use OE 1
and OE 1
with the standard meanings.
Another useful abbreviation is the following.
Definition 12: The formula "x
vn
)" where v is a node of type
We now define satisfaction of LDM formulas. Let OE(x 1
vn
) be an
, . , x n
vn . Let l 1
, . , l n be an
assignment of object names to the free variables in the formula, i.e., each
l i is a member of the corresponding I(v i ). means that OE is
satisfied by l in the instance I. When I is clear from the context, we
shall write j= instead of
Definition 13: Let OE(x 1
vn ) be a formula with free variables x 1
, . ,
vn
, and let l
following hold:
1. If OE is x i
, then
2. If OE is x i
, then
3. If OE is x i
4. If OE is x i
5. If OE is x i
, then
6. If OE is x i
7.
or
8. does not hold.
9. If OE is a formula with free variables x 1
I
(l
Definition 14: Let OE be an LDM sentence. We say that I satisfies OE iff
I OE holds.
Example This example and the next one will be over the LDM schema
of Fig. 6 with the instance of Fig. 8. The LDM formula OE(x
says that the name of x u is equal to the first component of the value of y v .
holds for the (l 1
Example 7: The following constraint says that each name in u is related to
exactly one set in w. For example, '8' and `9' as parents of '2' must be in
one set rather that in two different sets. The constraint is
In other words, each name in u (x u ) has at most one name in w (z 1
and z 2
associated with it. This association is through y 1
and y 2
Note that this constraint says that each name in u is associated with at
most one set in w, rather than saying that each person in the database is
associated with at most one such set. There could still be duplication in u,
e.g., two names with the data value "Solomon." One way to prevent this is
through the constraint
The following lemma shows that a slightly restricted logic has the same
power. This restricted logic does not have atomic formulas that compare
data values of internal nodes. This lemma makes subsequent proofs and
definitions simpler.
Lemma 2: Let OE(x 1
vn
) be an LDM formula whose free variables are
the variables x 1
, . , x n
vn
. There is an LDM formula /(x 1
vn
) with the
that does not contain any atomic subformula of the form
x different from , such that / is equivalent to OE.
That is, for all instances I of S and all l 1
iff
Proof: The proof is by induction on the size of OE. We show how to construct
for formulas of the form x are similar and not of
type . The result then follows immediately.
We distinguish between the possible types of v and w.
1. If u and v are of type (
is a new variable. Let I be an instance of S. Then
I
, For all l in I(w); l 2 val(l 1
and therefore OE , / is valid.
2. If u and v are of type (
wn
wn - n x u , z n
wn
, . , z n
wn are n distinct new variables. Let I be an instance
of S. Then
is equivalent to val(l 1
If val(l 1
n) and val(l 2
equivalent to the conjunction of l i= l i, for In other
words, val(l 1
I
Therefore
is equivalent to
wn
wn - n x u , z n
wn
(l 1
i.e., OE , / is valid.
3. If u and v are of type (
ae x u - z 1
ae y v
wn )(z n
wn ae x u - z n
wn ae y v );
, . , z n
wn
are n distinct new variables. Let I be an instance
of S. Then
is equivalent to val(l 1
This holds iff for some case
I
ae x u - z i
ae y v )
and once more OE , / is valid.
From now on, we shall assume that x can appear as a subformula
only when as proofs are concerned, but shall be
able to use the more general form when convenient.
The proof of the following lemma, that says that satisfaction is preserved
under isomorphism, is straightforward.
Lemma 3: Let S 0 be an extension of S, and let I 1
and I 2
be extensions
of I to S 0 . Let g be an isomorphism from I 1
to I 2
relative to S, and let
vn ) be an LDM formula. Then
OE
Finally, we show that our logic is effective over finite instances.
Lemma 4: Let OE(x 1
vn ) be an LDM formula over S whose free variables
are the variables x 1
vn
. Let I be a finite instance and let l
for all
can be determined effectively.
Proof: We show this by induction on the size of the formula. For atomic
formulas testing for satisfaction is straightforward. Testing for disjunction
and negation is also clearly effective. For quantification we make use of the
finiteness of I. In order to test whether
test
whether for each l in the finite set I(w).
5. The Logical Query Language
In the relational model the result of a query is a relation. A natural generalization
would be for the result of a query in our model to be another
LDM schema, called henceforth the query schema, together with an instance
of that schema. We modify this slightly, by not requiring that the query's
schema be an independent schema, but instead allowing the successors of
nodes in the query to be nodes in the database schema.
Continuing the analogy with the relational calculus, the natural thing to
do would be to let the query be some LDM formula OE. The resulting instance
would then consist of those objects that satisfy OE.
There are two problems with this approach. First, while it is clear how
an LDM formula can select objects that satisfy certain conditions, it is not
clear how an LDM formula can construct new objects. One solution would
be to prevent the query from referring directly to object names, but rather
have the query refer only to object values. We could then find all possible
values than might appear in the result, assign them arbitrary names, and
show that the result is unique up to isomorphism.

Figure

10: LDM schema
I 1
l val(l)
I 1
(v)
l val(l)
4 (2)

Figure

11: A possible result of the query
This still does not solve the second problem, which is how to deal with
cyclicity. Not only do we need the ability to refer directly to object names in
order to deal with cycles, but even then the result of the query is not always
l val(l)
I 2
(v)
l val(l)
3 (2)

Figure

12: Another possible result of the query
defined uniquely. For example, if the query schema is that of Fig. 10, and the
query specifies that I(u) and I(v) each contain at least two different names,
then there is no way to choose between the two incomparable instances in
Fig. 11 and 12. Our solution to this problem is to restrict the queries to
ones not that do not contain cycles, while allowing cyclicity in the database.
Furthermore, we allow the query to refer explicitly to names only in nodes
of the database. For a more detailed discussion of the motivation underlying
our approach see [Kup85]. More recent work, e.g. IQL ([?]), has shown how
query languages could be defined to allow cyclic queries.
5.1. The Query Language
Definition 15: Let be an LDM schema. A query on S consists
of a tuple
1. SQ is an extension of S.
2. OE Q is a topological order on the nodes in VQ \Gamma V , i.e., OE Q is a linear
order such that if v is a child of w then v OE Q w.
3. \Phi Q is a set of pairs hv; OE v i that assigns a formula OE v to the node v, for
each node v in . The formula OE v that corresponds to the node
(a) OE v has only one free variable, and it is of sort v.
(b) All other variables in OE v are bound. Each of their sorts is either a
node of the database schema S or is a query node that precedes v
under OE Q .
The order OE Q is used to specify the order in which we define the result of
the query. Each formula OE v specifies the contents of v in terms of database
nodes, and of query nodes that precede v.
Before continuing with the formal details we give several examples of
queries. The database schema in all these examples is the genealogy schema
of Fig. 6 with the instance of Fig. 8.
Example 8: The schema of Q 1
is shown in Fig. 13. The formula OE u
In other words we want I(u 0 ) to be a copy of I(u). (We eliminate, however,
any duplication that may be in I(u).) The result of the query is shown in
Fig. 14. 2

Figure

13: Schema of Q 1
Example 9: The schema of Q 2
is shown Fig. 15. We want v 0 to contain the
set of parents of Solomon, so we have the formulas
OE
and OE v 0
In all these examples, the result is defined only up to isomorphism relative to S, i.e.,
the choice of names is arbitrary
19 David
Jesse

Figure

14: Result of Q 1
The intuition behind this is that OE u that there is some name
with the value "Solomon," and another name (y 1
equal to x u 0 . The rest of the formula says that y 1
is a parent of y 2
. OE v 0
says that I(v 0 ) contains all the names in I(u 0 ) in one set. The result of the
query is shown in Fig. 16.

Figure

15: Schema of Q 2
We now formally define the result of a logical query. We start by looking
at queries that add just one node to the schema. We shall call such queries
simple queries.
query Q is called a simple query if jV
shall use the notation Q v for a simple query with
Let Q v be a simple query on a schema S and let I be an instance of S.
The result of Q v on I is an extension I v of I to SQv . In order to define I v
l val(l)

Figure

we have to define what names I v (v) contains, and what the values of these
names are. We would like I v (v) to contain all the objects that satisfy OE v (x v ).
The problem with using this as a definition of I v is that OE v
names and since I v (v) has not yet been defined it is meaningless to talk about
the objects that satisfy OE v . It might seem that this is really a trivial problem,
but suppose that OE v included the conjunct (8y v )(8z v )(y
can contain at most one name. If the rest of OE v allowed several possibilities
for the value of this name, there would be no way to choose which one should
be in the result.
The reason this is not a problem for us is that such a formula is not
allowed in our query language-all bound variables in our language must
refer to database nodes or to nodes that precede v, but cannot refer to v
itself. As a result of this restriction, it turns out that although OE v refers to
names, OE v is actually a statement about values. We can therefore find the
values that satisfy OE v and pick the names arbitrarily.
Definition 17: Let val be a value (i.e., anything that could be the value of
We say that val is a candidate value for v 3 if the following holds. Let
l be some new name, i.e., a name that does not appear in I. Let I v be the
extension of I to SQv with I v
By using this arbitrary name we are able to express the fact that val is
one of the objects that should be in the result of the query. Note that this
definition is where we make use of the fact that the query is acyclic.
We first show that the particular choice of name is unimportant.
Lemma 5: Let val be an data value and let I 1 and I 2 be two extensions of I
to SQv defined by, respectively, I 1
3 This really depends on Q and I as well, but they should be clear from the context.
val
Proof: By definition OE v has only one free variable of sort v, i.e., the variable
x v . By inspection we can see that the only atomic formulas that can contain
x v are xw - . The
last of these is always true, and it is easy to see that the truth of the others
depends only on the value of x v and not on its name. The proof is then a
straightforward induction.
We now define the result of SQv . Take all the candidate values for v,
pick a new name for each one of them and put all of these names into I v (v).
Notice that the set of candidate values can be infinite in principle, even when
I is a finite instance. Queries with the property that the set of candidate
values is finite correspond to the safe queries in the relational model. In the
next section we look at this issue in more detail.
Definition 18: The result of Q v is the extension I v of I to SQv defined as
follows. Let R be the set of all the candidate values for v and let fl val j
val 2 Rg be a set of new names, i.e., names that do not appear in I. I v (v) is
defined as the set fl val j val 2 Rg with val v (l val val for each val 2 R.
We now show that this definition has the desired properties. In other
words, the result is well defined up to isomorphism relative to S, everything
in the result satisfies OE v and we cannot add anything else that satisfies OE v to
the result without introducing duplication.
The proof of the following lemma is similar to the proof of Lemma 5.
Lemma I 1 be an extension of I to SQv . Let l be an element of
I 1 (v) and let I 2 be the extension of I to SQv defined by I 2
val
Lemma 7:
1. Let I 1 and I 2 be two results of Q v . Then I 1 and I 2 are isomorphic
relative to S.
2. Let I v be the result of SQv . Then for each l in I v (v),
Proof:
1. Let l 1 be an element of I 1 (v). Since val 1 (l 1 ) is a candidate value for v,
there must be some l 2 in I 2 (v) with val 2 (l 2 by the
definition of the result of the query, both I 1 (v) and I 2 (v) have no dupli-
cation, we immediately get a 1-1 correspondence between the names of
I 1 (v) and I 2 (v). It is straightforward to show that this correspondence
is an isomorphism.
2. Let l be an arbitrary element of I v (v), and let I  be the
extension of I to SQv defined by I
Lemma 6
Since val(l) is a candidate value for v, we can extend I to an instance
I    of SQv by defining I    We then have
I    OE v (l    ). By Lemma 5, I   OE v (l) and therefore
We now define the result of an arbitrary query Q. To do this, we first
define composition of queries.
Definition 19: Let Q 1 be a query and let Q 2 be a query on SQ 1
.
the query on S that we get by composing them in the following way.
consists of SQ 2 ffiQ 1
and
Lemma 8: a query on S.
Let the nodes added by the query Q be
We define a sequence of simple queries Q
, . , Q vn , as
follows. Each Q v i is a query on the schema of Q v i\Gamma1 . Q adds the node
v i to that schema, and the formula for v i is OE v i
. It is easy to see that
and we use this to define the result of Q.
Definition 20: The result of the query Q on I is the result of applying the
queries
, . , Q vn successively to I.
Lemma 9: The result of Q is unique up to isomorphism. In other words,
different choices of names at each step yield isomorphic results.
Proof: This is a straightforward application of the first part of Lemma 7.
Theorem 10: Let I Q be the result of the query Q on the instance I.
1. Let v be a node added by Q and let l be an element of I Q (v). Then
I Q
2. Let v is a node added by Q and let l 1 and l 2 be two different names in
I(v). Then val(l there is no duplication in the result.
3. I Q is a maximal extension of I to SQ that satisfies 1-2. This means
that there is no extension I
Q with I
satisfies 1-2 and such that for at least one v the inclusion is proper.
Proof:
1. Let Q   be the query Q
be the
result of Q   . By Lemma 7,
OE v (l). It is easy to see that I Q is an
extension of an isomorphic image of I Q   and that extending I Q   to I Q
does not affect the satisfaction of OE v .
2. Obvious.
3. Assume that such an I   exists. Let be the first of the nodes v 1 ,
. , v n for which I
be the query Q
From 1 and 2 it follows immediately that both I Q and I
restricted
to SQ   are results of Q   . Lemma 9 then implies that I
Q and I Q are
isomorphic, a contradiction.
5.2. Safe Queries
In the previous section we observed that the set of candidate values at a query
node can be infinite in principle, even over finite instances. For example:
Example 10: OE u This query is unsafe since the
set of candidate data values is fDavidg, an infinite set.
Definition 21: A query Q on a schema S is safe on a finite instance I of S
if the set of candidate data values at each node is finite. Q is safe if it is safe
on every finite instance I of S.
Let v be a query node. Assume that we have defined the result of Q on
all the nodes that precede v, and that each of these preceding nodes contains
a finite set of names. If
\Theta , h
or h
[ , the set of candidate values for v
is a subset of, respectively, the Cartesian product, powerset or union of the
instances of v's children and therefore is finite. The only case when the set of
candidate values may be infinite is when since the set D of data
values is infinite.
Lemma 11: Q is safe on I iff for every query node of type the set of
candidate data values for v is finite.
The following two examples use the database and query schema of Fig. 13
and the database instance of Fig. 8.
Example 11: OE u
is safe since the set of candidate data values is
Solomon, Rehoboam, Absalomg.
Testing safety of relational queries can be reduced to testing safety of
LDM queries [Kup85]. As a consequence, testing for safety is, in general,
undecidable. It is decidable, however, to test whether a given query Q on
a schema S is safe on a given instance I. We now describe the decision
procedure.
Lemma 12: Let w be all of the nodes of the database schema S
that are of type , and let fd be the constants that occur in the
formula of Q. Q is safe on I iff for each query node v of type , each
candidate value for v is either a) the value of an element of some I(w i ) or b)
one of the d j 's.
Proof: One direction is obvious-if this condition holds then Q is safe on I.
We prove the converse by induction on the query nodes
be a query node of type , and assume
that the lemma holds for the nodes that precede v i and that Q is safe on I.
Let I i\Gamma1 be the result of Q v i\Gamma1
is safe on I the set of candidate data values for v is a finite set
R. We have to show that
Call the right hand of this equation S. If the lemma is false, then there is
some element val in R \Gamma S. By the induction hypothesis
I
Since val is a candidate data value for v, if we extend I i\Gamma1 to an instance I 1
of SQv by defining I 1
be an arbitrary element of D \Gamma S, and extend I i\Gamma1 to an instance I 2
i of SQv
by defining I 2
val and val 0 do not appear
either in the database, in preceding query nodes, or in the query formulas,
an induction on the size OE v shows that
The key point in the induction is that x v can occur in OE v
1. Atomic formulas of the form x is a node
of type that is either in V or is one of the nodes v 1 , . , v i\Gamma1 . Such
a formula is false whenever the data value of x v is not in S.
2. x v are x These formulas are always true.
We have therefore shown that all the elements of the infinite set D \Gamma S are
candidate values, contradicting the assumption that Q is safe on I.
The technique of the proof gives us an effective procedure for determining
whether a simple query Q v is safe on a finite instance I. Take some data
value d 0 2 D that does not occur anywhere in the database or in the query
formulas. Test if d 0 is a candidate value (it is not difficult to see that this can
be done effectively). In a similar way to the proof of this lemma, we can show
that Q v is safe on I iff d 0 is not a candidate value for v. Intuitively, if some
such d 0 is in the result, the result is infinite since d 0 cannot be distinguished
from any other such data value. This proves the following theorem.
Theorem 13: Let Q be a query on S and let I be a finite instance of S.
There is a decision procedure to test whether Q is safe on I. If Q is safe on
I, then the result can be computed effectively.
6. The Algebraic Query Language
6.1. The Algebraic Operators
In this section we define a set of algebraic operators. We then show that
any safe logical query is equivalent to some sequence of algebraic operations,
and, conversely, each sequence of algebraic operations is equivalent to a safe
logical query.
Since a logical query adds some nodes to the database schema and leaves
the instance of the database schema unchanged, each algebraic operator must
do the same. Therefore, a selection operator, for example, should not delete
tuples that do not satisfy the selection condition, but should rather create a
copy of the database node. That copy should contain only those tuples that
satisfy the condition. In fact this copying of tuples is what is really done in the
relational model-a query does not throw away those tuples in the database
that do not meet a selection condition, but rather copies those tuples that
do. This issue is not addressed explicitly in relational database theory, since
the theory does not deal with what happens to temporary relations that are
created while computing the result of a query. As we shall see in the next
section, it will be necessary to delete nodes, in certain circumstances. We
would still like to make the deletions explicit, rather that hide them in other
algebraic operations.
In this section S will be a database schema with instance I. The algebra
consists of operations of the form w Here ff is the name
of the operator, and its arguments v 1 , . , v n are nodes in the schema S. ff
adds the node w to the schema, and extends I to the new schema. We define
each operator as a simple logical query, by giving
1. The types of its arguments.
2. The type of w and the list of its children.
3. An LDM formula OE w that specifies the contents of I(w).
6.1.1. Operators that Copy and Combine Existing Nodes

Figure

17: The algebraic operation


Figure

18: The algebraic operation
(v)
1. w / (v) creates a copy of the node v, as is shown in Fig. 17. (In all
these figures the schema S is shown in the box on the right, and the
node that is created by the operation is on the left.) For each distinct
data value in I(v), I(w) contains exactly one name with this data value.
Note that duplication in I(v) is eliminated in I(w).
(a) v is a node of S that has type .
(b) w is of type .
(c) OE w
2. w / (d) creates a node of type that contains just the data value
d.
(a) d is a data value in the data domain D.
(b) w is of type .
(c) OE w
3. w / h
(v) creates a node that contains all finite subsets of I(v) (see
Fig. 18).
(a) v is any node in the schema S.
(b) w is of type ( h
\Theta
s

Figure

19: The algebraic operation
\Theta (v
s

Figure

20: The algebraic operation
(c) OE w
4. w / h
\Theta (v creates a node that contains the Cartesian product
Fig. 19).
(a) are any n nodes in the schema S.
(b) w is of type ( h
(c) OE w
5. w / h
creates a node that contains the disjoint union
Fig. 20).
(a) are n distinct nodes of the schema S.
(b) w is of type ( h
(c) OE w
6.1.2. Selection Operators The LDM algebra has two selection operators

1. The operation w / oe i ' j (v) is similar to the selection operation in the
relational algebra. This operator selects those tuples in v whose i th
and j th components are related by ' (see Fig. 21).
(a) v is a node of S of type ( h
is one of the
relations
(b) w is of type ( h
(c) OE w
Alternatively, the selection condition may be of the form
d is a data value in D. Then OE w
\Theta
s
~
\Theta

Figure

21: The algebraic operation
s
s u
R q

Figure

22: The algebraic operation
w / oe in (u; v)
2. w / oe in (u; v). Here u is a child of v, and w will contain those objects
of I(u) that actually appear in I(v) (see Fig. 22). For example, if v is
to type h
, each element of I(v) will be a set of elements from I(u).
The result of oe in (u; v) will select from I(v) those elements that are in
at least one of these sets.
(a) u and v are nodes of S and u is a child of v.
(b) w is of the same type as u and has the same children.
(c) OE w depends on the type of v. Note that v cannot be of type
since it has a child u.
i. If v is of type h
\Theta with u as its i th child then OE w
(Strictly speaking, oe in (u; v) is under-specified here, in case
there are multiple edges from v to u, since we have to specify
the edge to which we are referring. In this case we shall use
the notation oe in (u; v; i) to mean: use the i th edge with tail
ii. If v is of type h
iii. If v is of type h
, then OE w
6.1.3. Union, Difference and Projection
1. The union operator is similar to the relational union. The syntax we
use is w Fig. 23).
(a) are n nodes of S that are of the same type and have the
same children.
(b) w has the same type and the same children as the v i 's.
(c) OE w
s
s
s

Figure

23: The algebraic operation
\Theta
s
s
\Theta v
~~

Figure

24: The algebraic operation
2. For difference we shall use infix notation, i.e., we shall write w
rather than \Gamma(v
(a) v 1 and v 2 are nodes of S that are of the same type and have the
same children.
(b) w has the same type and the same children as v 1 and v 2 .
(c) OE w
3. The projection operation is similar to projection in the relational alge-
bra. The syntax we use is w / \Pi A (v), where A is an ordered multiset
of edges with tail v.
(a) v is a node of S of type ( h
A is an ordered
multiset of edges with tail v.
(b) Let is the edge (v; v i j ). Then w is of
(c) OE w
When it does not cause any ambiguity, we shall use a set A of nodes
rather than of edges, as in Fig. 24.
6.2. Equivalence of the Logical and Algebraic
Query Languages
We now use these algebraic operators to define an algebraic query language.
An algebraic query is a sequence fff g, where each ff i is an algebraic
operator on the result of ff i\Gamma1 . We would like to be able to show that this
query language is equivalent to the logical query language. In other words, for
each logical query on a schema S, there should exist a sequence of algebraic
operations, and vice versa, with the property that the schemas created by
these two queries are identical, and for every database instance I, the results
are isomorphic relative to S. Unfortunately, as the next example shows, this
is not quite true.
Example 12: Let S consist of a node u of type and let Q be the logical
query that adds a node v of type to S. Let d 1 and d 2 be two data values,
and let OE v The candidate values for v are then
g. There is no algebraic query equivalent to Q. If there was such a
query, it would consist of one algebraic operation alone, since each operator
adds a new node to the schema. By inspection we can see that no single
algebraic operator is equivalent to Q.
How can we modify the definition to get an equivalent query? If QA is
the algebraic query that consists of the operations w 1 / (d 1
clear that the instance of v is what we are after. If
we were then to restrict the result of the query to the schema that consists
of the nodes u and v we get the instance we want. We have essentially used
the two nodes w 1 and w 2 for temporary storage while computing the result
of the query. In fact the same thing occurs in the relational model, since
temporary relations are used there for subexpressions and then deleted at
the end. It is therefore reasonable to expect the same thing to happen in the
logical data model.
To be able to use temporary nodes, we extend the algebraic query language
by adding a "delete" operator. This operator deletes a node from the
schema and restricts the instance of the original schema to the new schema.
We have to make sure that we never delete a node that is the child of some
other node, since in that case the result would not be a legal schema. The
operator that deletes the node v will be written D(v).
Definition 22: Let S be an LDM schema with instance I. The algebraic
operator D(v) is legal when v is a node with no parent. The result of D(v) is
the schema S 0 that consists of deleting v from S, together with the instance
that we get by restricting I to S 0 .
In the algebraic query language we must take care not to delete database
nodes, i.e., we must only allow the user to delete nodes that have been constructed
by his query. We shall call the language with the deletion operator
the extended algebraic query language.
Definition 23: Let S be an LDM schema. An extended algebraic query on
S is a sequence each ff i is either
1. An operation of the form w
is an algebraic
operator other than the deletion operator and v 1
are either
node of S or are nodes that were created by some previous fi j and have
not been deleted.
2. The operator D(v i ), where v i is a node that was created by a previous
algebraic operator in the sequence fi 1 , . , fi i\Gamma1 and has not yet been
deleted.
Definition 24: Let QA be an extended algebraic query on S, and let QB
be an extended algebraic query on the result of QA . The query QB ffi QA is
the composition of QA and QB , formed simply by concatenating the lists of
algebraic operators.
Obviously, the delete operator itself is not equivalent to any logical query,
since every logical query adds nodes to the schema. This by itself does
not necessarily mean that we cannot find a logical query equivalent to any
extended algebraic query. After all, an extended algebraic query does not
delete database nodes, since the only nodes that are deleted are those that
were constructed by previous algebraic operations. It might still be the case
(as in Example 12) that there is an equivalent logical query that does not
use temporary nodes. Nevertheless, in [Kup85] it is shown that the extended
algebraic query language is strictly more powerful than the logical query
language. In order to get an equivalent query language, we modify the logical
language to include temporary nodes as well.
Definition 25: Let S be an LDM schema. An extended logical query on S
is a tuple
1. is a logical query on S.
2. DQ is the set of temporary nodes used in the query. DQ is a subset
of the query nodes that we can delete and still get an LDM
schema. In other words, there is no edge with tail outside DQ and head
in DQ , i.e., if
Definition 26: Let Q be the extended logical query hS
let I be an instance of S. The result of this query consists of
1. The schema S
Q consisting of
(a) The nodes in VQ \Gamma DQ .
(b) The relevant edges, i.e., all those edges of SQ whose head and tail
are both in VQ \Gamma DQ .
(c) The restriction of the type assignment - to VQ \Gamma DQ .
2. The result of Q on I is defined as follows. Let I Q be the result of
I. The result of Q on I is then the restriction of I Q
to S
We now show that every extended algebraic query is equivalent to some
extended logical query.
Lemma 14: Let be an extended algebraic query on S.
There exists a safe extended logical query Q L on S such that for every instance
I of S, the results of QA and Q L on I are isomorphic relative to S.
Proof: The schema of Q L consists of all those nodes that are created by the
operations in the query QA . The set of temporary nodes DQL is the set of
nodes deleted in QA , i.e., fv i j The operator ff i is D(v i )g. Since we are only
allowed to delete nodes that are not in S and that have no parent, it is easy
to see that there is no edge whose head is in DQL and whose tail is not. Each
ff i that is not a delete operator must be of the form w
We define an order on the nodes of
) is the formula that was used to define the operator fi j . It is
easy to verify that the results of QA and Q L on any instance I are indeed
isomorphic.
To show the converse, let Q L be a logical query on S. Let I be a fixed
instance of S such that Q L is safe on I. The definition of QA will not depend
on I, but the results of QA and Q L will only be isomorphic on those instances
of S on which Q L is safe. We keep I fixed so that we will be able to prove
various lemmas about the results of the queries as we go along.
We first look at the case when Q L is a simple query Qw . We start by
creating a node w dom , that contains the "domain" of w, i.e., all those objects
that might be candidate values for w, if we were to ignore everything except
the type of w and the fact that Q L is safe on I. We define w dom as follows.
1. If w is of type , let v 1 , . , v t be all the nodes in S that are of type
and let d 1 , . , d k be the constants that occur in OE w
w dom by the algebraic query:
w dom / [(s
2. If
\Theta (v
3. If
(v).
4. If
Call this algebraic query Q dom .
Lemma 15:
1. The schema created by Q dom is equal to the schema of S together with
a node w dom of the same type and with the same children as the node
w in the original logical query Qw .
2. Let I dom be the result of Q dom on I and let I w be the result of Qw on
I. If val is a value of an object in I w (w), then val is also a value of an
object in I dom (w dom ).
Proof: If w is of type h
\Theta , h
[ or h
, the lemma is obvious. If w is of type ,
the first part follows from the fact that all the nodes except w dom that are
created by Q dom are also deleted by Q dom . The second part is an immediate
consequence of Lemma 12 and the definition of Q dom .
We may assume, if necessary by renaming some bound variables, that all
the bound variables in the formula OE w are distinct. Let these variables
be x 1
, . , x k
. The algebraic query Q prod on the result of Q dom consists of
the operation
w prod / h
\Theta (w
For the purpose of defining QA we shall label the edges with tail w prod as
follows. The i th edge with tail w prod will be labeled x i
. These labels are
used only to define the algebraic query, and are not themselves part of the
query. Their purpose is to tell us which bound variable the edge corresponds
to.
In certain cases, when we create a new node using some algebraic oper-
ation, the outgoing edges from the new node will inherit the labels of the
corresponding edges whose head is one of the arguments of the operator. We
only use this inheritance in cases when it is unambiguous, i.e., in cases when
all the arguments have the same labeling. The operations for which labels
will be inherited are oe i ' j , difference and union. When we use the projection
operation the new edges will also inherit the labeling of the corresponding
edges whose head is the argument of the projection.
Arrange all the well-formed subformulas of OE w in a list / 1 , . , /m ,
it is a subformula of / j .
For each such subformula, we define an extended algebraic query Q
on the
result of Q /
. Q
is a query on the result of Q prod . The node w / i
is
of type ( h
intuitively, those tuples
(l
The edges with tail w / will be
labelled with the variables that might be free in /-i.e., those that haven't
yet been bound by /. The definition of Q
is as follows.
1. / i is x a
.
2. / i is x a
is w
/ oe a ' k+1 (w prod )
3. / i is xw ' xw . Q
is w
4. / i is x a
is w
5. / i is
is w
. Let A 1 be the (ordered multi)set of edges with tail w
that have the same label as some edge with tail w
. Let A 2 be the
corresponding set of edges with tail w
. Q / i is the following extended
algebraic query
(w
(w
are different temporary nodes from those used above, and
from similarly named nodes used below.) Note that the way we defined
A 1 and A 2 guarantees that there is no ambiguity in labeling the edges
of the result, at least as long as the labels of the edges in A 1 and A 2
are in the same order. We shall show later that this is indeed the case.
7. / i is :/ j . Let A be the (ordered multi)set of edges with tail w dom that
have the same label as some edge with tail w / j . Q / i is the following
extended algebraic query
(w / dom
As in the previous case we shall show that we can label the edges with
tail w / i without any ambiguity.
8. / i is (9x a
wa )(/ j ). Let A be the (ordered multi)set of all edges with tail
for the edge labeled x a
wa . We show below that there must
be exactly one edge with this label. Q
then consists of the algebraic
operation w
Lemma be one of these well formed subformulas of OE w
Let x a 1
, . , x a j
be those variables in the above list that are not bound in
. Note that some of the x a i
's may not actually occur in / i . Then w / i is
of type ( h
Furthermore, the t th edge with tail
has head w a t
and is labeled with the variable x a t
wa t
. As a consequence of
this, all the labelings of edges are in the same order, and the assumptions
that we made on the labelings when we defined the w / i
's hold.
Proof: The proof is a fairly straightforward induction using the definition
of w / i
. The tricky case is when / i is
. Then the children of w
correspond to the bound variables of OE w that are not bound in / j 1
and the
children of w
to the bound variables of OE w not bound in / j 2
. Since a
variable is not bound in / j 1
iff it is not bound in / j 1
and it is not bound
in
, we see that the result does hold in this case 4 .
Lemma 17: Let w / i be of type ( h
be the
result of Q
on I, let l d be a member of I / i
(w dom ) and let l t be a member
of I / i (w k. Then there exists an l in I / i (w
(l only if
a candidate value iff it satisfies / i .
Proof: A straightforward induction on the structure of / i .
The extended algebraic query Q final on the result of Q OE w
consists of
wA / oe in (w dom ; w OE )
prod )
dom )
We finally define the algebraic query QA as
Lemma 18: Let I 1 be the result of Qw on I and let I 2 the result of the
algebraic query QA on I. Then I 1 and I 2 are isomorphic relative to S.
Proof: First note that the schemas are equal. The only node created but
not deleted by QA is the node wA . This node is similar to the node w dom
and hence to w.
We have to show that the instances of wA and w are isomorphic, i.e., that
at the point in evaluating the queries that we compute the instances of these
nodes, they have the same candidate values. We assume that we are at the
point in the evaluation of QA just before the final round of deletions.
4 Note that "not bound" is not the same as "free." A variable that is not bound in one
of these formulas is either free in this formula, or does not appear in it at all
Let val be a candidate data value for w. Extend I to an instance I w
of SQw by defining I w
I OE w be the result of Q OE w on I. By the second clause of Lemma 15, val is a
candidate data value for w dom and so for some l d in I OE w (w dom ), val(l d
By Lemma 6,
OE w (l d ), and therefore, by Lemma 17,
for some l OE in I OE w (w dom ), val(l OE val is a candidate data value for wA .
For the converse, suppose that val is a candidate data value for wA .
Let I OE w
be the result of Q OE w
on I. Since val is a candidate data value for
wA , for some l OE in I OE w (w OE w ) and some l d in I OE w (w dom ), val(l OE
l OE is in I OE w
(w OE w
implies that
Restrict I OE w
to an instance I dom of the schema of Q dom . Then dom
and so by Lemma 6, val(l d val is a candidate data value for w.
Since an arbitrary logical query can be viewed as a sequence of simple
queries, we can easily extend the above construction to arbitrary queries by
concatenating the algebraic queries for the individual simple queries. If we
have an extended logical query we have to add deletion operations to delete
those nodes in the delete set of the query. This yields the following theorem.
Theorem 19: The extended algebraic query language and the extended logical
query language are equivalent, i.e., for every extended algebraic query
on S there exists a safe extended logical query on S and for every extended
logical query on S there exists an extended algebraic query on S, such that
both queries define the same schema and for every database instance I on
which the logical query is safe, the results of both queries are isomorphic
relative to S.
7. Concluding Remarks
We have described a new model of data, the Logical Data Model, that is
designed to combine the advantages of the existing data models. On the one
hand, it enables the database to describe more of the semantics of the data
than is possible using the relational model of data. On the other hand, we do
not lose the nice properties that relational databases have, in particular the
ability to query the database using equivalent nonprocedural and procedural
languages. The complexity of our query language is studied in [KV85, ?, ?].
Our work unifies and generalizes a long sequence of previous works on
semantic data models [AB84, DB82, FK77, ?, GDB82, Gra79, Har78, ?, ?,
Kob80, Mak77, MP82, OY85, RR83, SP82, ?, SS77, Tsi76]. The preliminary
publication of our results in [KV84], stimulated later work, such [?, ?, ?].
All these models can be viewed as special cases of LDM, designed to make
certain classes of queries easier to express, or more efficient to implement.
Our model incorporates two important object-oriented features: object
identity, captured by the distinction between object names and object values,
and strong typing, our types are built from the product, power, and union
operations. It does not, however, incorporate other features considered to be
important to object-oriented databases, such as "inheritance", "methods",
"encapsulation" etc. (cf. An important feature of our model is the
separation of schema and instance, unlike the models in [?, ?].
While one of the feature of LDM is the ability to describe cyclic data, this
feature is lacking in the query language. This brings up two questions: is it
possible to eliminate cycles from databases? is it possible to add cycles to
queries? The first question is addressed in [KV85]. More recently, [?] shows
how to extend the query language to allow cycles in queries.
The query languages that we have described are based on the paradigm
of first-order logic. It is by now recognized that in the framework of the
relational model first-order languages are too weak for the task of database
querying [AU79]. This motivated the study of more powerful query lan-
guages, based on the paradigm of logic programming [?, ?, Rei78, Ull85].
More recently, similar query languages have been developed for models similar
to LDM [?, ?, ?, ?, ?, ?].

Acknowledgments

We are indebted to Jeff Ullman for some of the basic ideas underlying this
work. We would also like to thank Rick Hull, Paris Kanellakis, and Dave
Maier, for helpful discussions and suggestions, and the anonymous referees
for suggestions for improvements.



--R

Non first normal form relations to represent hierarchically organized data.
Notes on non-well-founded sets
Universality of data retrieval lan- guages
A relational model of data for large shared data banks.
Extending the database relational model to capture more meaning.
On the correct translation of update operations on relational views.
An algebra of quotient relations.
Semantics of net-work data manipulation languages: An object-oriented approach
NETS: Operations and logic.
Ambiguity in processing boolean queries on tdms tree-structures: A study of four different philosophies
The format model: A theory of database organization.
Application of database logic to database design.
On database logic.
An overview of the database mangement technology.
The Logical Data Model: A New Approach to Data-base Logic
A new approach to database logic.
On the expressive power of the logical data model.
A consideration on normal form of not-necessarily normalized relations in the relational data model

A normal form for nested rela- tions
Deductive question answering in relational databases.
A data definition language for a statistical database.
Data structures for an integrated data base management and information retrieval system.
Database abstractions: Aggregation and generalization.
Data Models.
LSL: A link and selector language.
Principles of Database Systems.
Implementation of logical query languages for databases.
Review of
--TR
The Format Model
On compiling queries in recursive first-order databases
Non first normal form relations: An algebra allowing data restructuring
The logical data model: a new approach to database logic
A calculus for complex objects
An amateur''s introduction to recursive query processing strategies
Sets and negation in a logic data base language (LDL1)
Extending relational algebra and relational calculus with set-valued attributes and aggregate functions
database modeling: survey, applications, and research issues
A survey of theoretical research on typed complex database objects
On the complexity of queries in the logical data model
data models
F-logic: a higher-order language for reasoning about objects, inheritance, and scheme
Object identity as a query language primitive
Logic programming with sets
A rule-based language with functions and sets
Object-oriented database systems
On the expressive power of the logical data model
The functional data model and the data languages DAPLEX
Database description with SDM
On the correct translation of update operations on relational views
Implementation of logiclal query languages for databases (abstract only)
Extending the database relational model to capture more meaning
Database abstractions
On Database Logic
A normal form for nested relations
A relational model of data for large shared data banks
An algebra of quotient relations
Principles of Database Systems
Universality of data retrieval languages
Data Models
CQLF---a query language for CODASYL-type databases
A new approach to database logic
Remarks on the algebra of non first normal form relations
Semantics of Network Data Manipulation Languages
Data Structures for an Integrated Data Base Management and Information Retrieval System
Extended Algebra and Calculus for ~1NF Relational Databases

--CTR
Hong-Cheu Liu , Jeffery X. Yu, Algebraic equivalences of nested relational operators, Information Systems, v.30 n.3, p.167-204, May 2005
Evgeny Dantsin , Andrei Voronkov, Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.157-165, May 15-18, 2000, Dallas, Texas, United States
Serge Abiteboul , Sophie Cluet , Tova Milo, Correspondence and translation for heterogeneous data, Theoretical Computer Science, v.275 n.1-2, p.179-213, March 28 2002
Jan Van Den Bussche , Dirk Van Gucht , Marc Andries , Marc Gyssens, On the completeness of object-creating database transformation languages, Journal of the ACM (JACM), v.44 n.2, p.272-319, March 1997
Christoph Koch, On the complexity of nonrecursive XQuery and functional query languages on complex values, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1215-1256, December 2006
Serge Abiteboul , Paris C. Kanellakis, Object identity as a query language primitive, Journal of the ACM (JACM), v.45 n.5, p.798-842, Sept. 1998
Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
relational database;algebra;database schema;logic;tuple calculus