Optimizing Queries with Object Updates.
Object-oriented databases (OODBs) provide powerful data abstractions and modeling facilities but they usually lack a suitable framework for query processing and optimization. Even though there is an increasing number of recent proposals on OODB query optimization, only few of them are actually focused on query optimization in the presence of object identity and destructive updates, features often supported by most realistic OODB languages. This paper presents a formal framework for optimizing object-oriented queries in the presence of side effects. These queries may contain object updates at any place and in any form. We present a language extension to the monoid comprehension calculus to express these object-oriented features and we give a formal meaning to these extensions. Our method is based on denotational semantics, which is often used to give a formal meaning to imperative programming languages. The semantics of our language extensions is expressed in terms of our monoid calculus, without the need of any fundamental change to our basic framework. Our method not only maintains referential transparency, which allows us to do meaningful query optimization, but it is also practical for optimizing OODB queries since it allows the same optimization techniques applied to regular queries to be used with minimal changes for OODB queries with updates.
Introduction
One of the key factors for OODB systems to successfully compete with relational systems as well as to
meet the performance requirements of many non-traditional applications is the development of an effective
query optimizer. Even though there are many aspects to the OODB query optimization problem that can
benefit from the, already successful, relational query optimization research, there many key features of
OODB languages that make this problem unique and hard to solve. These features include object identity,
methods, encapsulation, user-defined type constructors, large multimedia objects, multiple collection
types, arbitrary nesting of collections, and nesting of query expressions.
There is an increasing number of recent proposals on OODB query optimization. Some of them
are focused on handling nested collections [OW92, Col89], others on converting path expressions into
joins [KM90, CD92], others on unnesting nested queries [CM95b, CM95a], while others are focused on
handling encapsulation and methods [DGK + 91]. However, there very few proposals on query optimization
in the presence of object identity and destructive updates, features often supported by most realistic
OODB languages.
In earlier work [FM98, FM95b, FM95a], we proposed an effective framework with a solid theoretical
basis for optimizing OODB query languages. Our calculus, called the monoid comprehension calculus, has
already been shown to capture most features of ODMG OQL [Cat94] and is a good basis for expressing
various optimization algorithms concisely, including query unnesting [Feg98] and translation of path
expressions into joins [Feg97]. In this paper, we extend our framework to handle object identity and
object updates.
1.1 Object Complicates Query Optimization
Object-oriented programming is based on side-effects, that is, on the modification of the object store.
Even though modern OODBs provide declarative query languages for associative access of data, queries
in those languages are allowed to invoke any method, including those that perform side effects. Object
creation itself, which is very common in OODB queries, is a side effect since it inserts a new object in a
class extent. Consider for example the following OQL query:
select Person(e.name,e.address) from e in Employees
which creates a new person from each employee. Even though this query seems to be free of side effects
at a first glance, it is not: it modifies the extent of the class Person by inserting a new person. If this
query were a part of another query and this other query were scanning the extent of the class Person,
this extent would have to be modified accordingly before it is used in the outer query. Therefore, the
semantics of the above query must reflect the fact that the Person extent is modified during the execution
of the query. Failure to do so may result to incorrect optimizations, which may lead to invalid execution
plans.
The problem of assigning semantics to object-oriented queries becomes even worse if we allow object
state modifications in arbitrary places in a query, like most OODB languages do. For example, the OQL
query
select (e.salary := e.salary*1.08)
from e in Employees
where e.salary?50000
gives an 8% raise to all employees earning over $50000. The semantics of this query should reflect the
fact that a salary is modified at each iteration.
The situation where queries are mixed freely with updates occurs more frequently in OODB languages,
such as O++ [AG89], that support set iteration embedded in a computational complete programming
language. Even though these languages are beginning to disappear in favor to more declarative languages,
such as OQL, there is a surge of interest to provide more computational power to existing declarative
query languages without sacrificing performance. Consider for example the following O++ query (taken
from [LD92]):
for (D of Divisions)
for (E of Employees)
suchthat (E!division==D) f
totpay
These types of queries allow any kind of C++ code inside a for-loop, including code that modifies the
database. Earlier research on query optimization [LD92] has shown that queries in this form are very
hard to optimize.
Another problem to consider when sets and bags are combined with side effects is that the results
may be unpredictable due to commutativity. For example, in the following O++ query
for (e of Employees)
the value of x at the end of the execution of this program would depend on the way Employees are scanned.
To understand the extent of this problem, consider the function f(n) which contains the assignment x:=n in
its body and returns n. Is the value of x, after the execution of ff(1); f(2)g, 1 or 2? (Since fx;
That is, is ff(1); f(2)g equal to ff(2); f(1)g?
Given that side effects may appear at any place in a program, proving equivalences between OODB
expressions becomes very hard. This makes the task of expressing and verifying optimization rules
difficult to accomplish. For example, the well known transformation x ./ y ! y ./ x, for any terms x
and y, is not valid any more since x and y may be queries that perform side effects and the order of
execution of the side effects would be changed if this transformation were applied, thus changing the
semantics of the program. One way to patch this error is to attach a guard to the above transformation
rule to prevent its execution when both terms x and y contain side effects. Unfortunately, this approach
is too conservative and it may miss some optimizations (e.g., when the side effects of x and y do not
interfere to each other). Furthermore, there is a more fundamental problem with algebraic operations
with side effects. For example, x ./ y cannot appear in a valid translation of a declarative query, since a
declarative query does not define an execution order.
Consequently, when optimizing a realistic OODB query language, we need to address the problem of
object identity properly and handle the implicit or explicit side effects due to the use of object identity.
It is also highly desirable to use the existing optimization techniques with minimal changes if possible.
To do so, it is necessary to capture and handle object identity in the same framework as that for regular
queries with no side effects. Unfortunately, such extensions are very difficult to incorporate to an existing
optimization framework. To understand the level of difficulty, consider the following equality predicate:
Person("Smith","Park
This predicate must be evaluated to false since the left object has a different
identity than the right one. On the other hand, given a function g(x) that computes the predicate x=x,
the function call g(Person("Smith","Park Av")) should return true. But if we unfold the call to g, we get
the previous false expression. Consequently, substituting the body of a function definition for a function
call is not a valid transformation any more.
Our goal is to give a formal meaning to OODB queries with side effects, and more importantly, to
provide an equational theory that allows us to do meaningful query optimization. It is highly desirable for
this theory to be seamlessly incorporated into the monoid comprehension calculus, possibly by discovering
a new monoid that captures the meaning of object identity. Another goal is, whenever there are no object
updates in a query, we would like this query be treated in the same way as it is currently treated by our
basic optimizer without the object extensions.
1.2 Our Approach
This paper presents a framework that incorporates impure features, namely object identity, into the
monoid comprehension calculus. According to our earlier discussion, it is important to give semantics to
such extensions to preserve referential transparency. We have referential transparency when we are able
to substitute equal subexpressions in a context of a larger expression to give equal results [Rea89]. If a
query language lacks this property, then the transformation rules of a query optimizer would depend on
the context of the expression on which they apply.
Researchers in programming languages often use formal methods, such as denotational semantics, to
solve such problems. In the denotational semantics approach, the impure features of a language can be
captured by passing the state (here the object store) through all operations in a program. If a piece
of a program does not update the state, then the state is propagated as is; otherwise it is modified
to reflect the updates. When we say "the state is modified", we mean that a new copy of the state
is created. This approach may become quite inefficient: for each destructive update, no matter how
small it is, a new object store (i.e., an entire database) must be created. Obviously, this technique is
unacceptable for most database applications. There is a solution to this problem. We can allow the state
to be manipulated by a small number of primitives that not only preserve referential transparency, but
have an efficient implementation as well. More specifically, even though these primitives are defined in
a purely functional way, their implementations perform destructive updates to the state. That way we
derive efficient programs and, more importantly, we maintain referential transparency, which allows us
to do meaningful query optimization.
But there is a catch here: this solution works only if the state is single-threaded [Sch85]. Roughly
speaking, a state is single-threaded through a program if this program does not undo any state modification
at any point, that is, if there is a strict sequencing of all the state updates in the program. In
that case, the state can be replaced by access rights to a single global variable and the state operations
can be made to cause side effects while preserving operational properties. The following is an example
of a non single-threaded program:
assume x:=2 in y := x+1;
The statement assume S1 in S2 executes the statement S1 locally. That is, the state modifications in S1
are used in S2 exclusively and then are discarded. Thus, the value of x and y after the completion of this
program are 1 and 3 respectively (since the binding x:=2 is discarded after it is used in y:=x+1). This
statement requires a local copy of the state during execution (probably in the form of a stack of states to
handle nested assume statements), since it needs to backtrack to the previous state after the completion
of execution. A rollback during a database transaction is another example of a non single-threaded
operation.
There are two common ways to guarantee single-threadedness. The first is to allow any state manipulation
in the language but detect violation of single-threadedness by performing a semantic analysis,
i.e., a kind of abstract interpretation [Sch85], such as using a linear type system [SS95], to detect these
violations during type-checking. The second approach, which we adopt in our framework, is to restrict
the syntax of the language in such a way that the state is guaranteed to always be single-threaded.
There is another serious problem with the above mentioned denotational semantics approach: to pass
the state through the operations of a program, we need to sequentialize all operations. This restriction
is not a good idea for commutative operations, since we may miss some optimization opportunities. For
example, for ranging over R, the assignment x := r can be evaluated during the
scanning of R in two ways; one will set x to 1 at the end and the other to 2, depending on the way
R is scanned. Both solutions are valid and should be considered by the optimizer. We address this
problem by generating all possible solutions generated by these alternatives at a first stage. It is up
to the optimizer to select the best one at the end (by performing a cost analysis). Even though this
approach may generate an exponential number of solutions when applied to constant data, in practice
it does not do so, provided that the query does not contain a large number of union operations. Each
alternative solution corresponds to a typically different final database state. At the end, only one solution
is chosen by the optimizer. So there is a "collection semantics" for queries - for each query there is a
collection of possible correct answers. We decided to consider all solutions instead of reporting an error
when more than one solution exists because most useful programs fall into this category. Considering all
alternatives during query optimization is necessary for proving program equivalences (such as proving
that ff(1); f(2)g is equal to ff(2); f(1)g). Only at the plan generation phase, i.e., when optimization is
completed, should we select an alternative.
Our framework is inspired by Ohori's work on representing object identity using monads [Oho90].
Our contribution is that we mix state transformation with sets and bags and that we apply this theory
to a database query language that satisfies strong normalization properties. Normalization removes any
unnecessary state transformation, thus making our approach practical for optimizing programs in our
object-oriented calculus. The most important contribution of our work is the development of a method
to map programs in which state transformation cannot be removed by normalization into imperative
loops, much in the same way one could express these programs using a regular imperative language, such
as C. The resulting programs are as efficient as those written by hand.
The rest of the paper is organized as follows. Section 2 describes our earlier results on the monoid
comprehension calculus. Section 3 describes our object extensions to the monoid calculus. Section 4 proposes
a new monoid that captures object identity and side effects. Section 5 describes our framework for
handling object identity using denotational semantics. Section 6 addresses some practical considerations
when building an optimizer based on our framework. Section 7 presents a prototype implementation of
our framework. Finally, Section 8 extends our framework to capture database updates and discusses how
this theory can be applied to solve the view maintenance problem.
Background: The Monoid Comprehension Calculus
This section summarizes our earlier work on the monoid calculus. A more formal treatment is presented
elsewhere [FM98, FM95b, FM95a].
The monoid calculus is based on the concept of monoids from abstract algebra. A monoid of type T
is a pair (\Phi; Z \Phi ), where \Phi is an associative function of type T \Theta T !T (i.e., a binary function that takes
two values T and returns a value T ), called the accumulator or the merge function of this monoid, and
Z \Phi of type T , called the zero element of the monoid, is the left and right identity of \Phi. That is, the zero
element satisfies Z \Phi \Phi every x. Since the accumulator function uniquely identifies
a monoid, we will often use the accumulator name as the monoid name. Examples of monoids include
([;f g) for sets, (];ffgg) for bags, (++; [ ]) for lists, (+; 0), ( ; 1), and (max; 0) for integers, and (-; false)
and (-; true) for booleans. The monoids for integers and booleans are called primitive monoids because
they construct values of a primitive type. The set, bag, and list monoids are called collection monoids.
Each collection monoid (\Phi; Z \Phi ) requires the additional definition of a unit function, U \Phi , which, along
with merge and zero, allows us the construction of all possible values of this type. For example, the unit
function for the set monoid is -x: fxg, that is, it takes a value x as input and constructs the singleton set
fxg as output. All but the list monoid are commutative, i.e., they satisfy x \Phi
y. In addition, some of them ([, -, and max) are idempotent, i.e., they satisfy x \Phi
A monoid comprehension over the monoid \Phi takes the form \Phif e j r g. Expression e is called the head
of the comprehension. Each term r i in the term sequence is called a qualifier,
and is either a generator of the form v / e 0 , where v is a range variable and e 0 is an expression (the
generator domain) that constructs a collection, or a filter p, where p is a predicate. We will use the
shorthand f e j r g to denote the set comprehension [f e j r g.
A monoid comprehension is defined by the following reduction rules:
(\Omega is a collection monoid,
possibly different than \Phi)
ae
U \Phi (e) if \Phi is a collection monoid
e otherwise (D1)
Rules (D2) and (D3) reduce a comprehension in which the leftmost qualifier is a filter, while Rules (D4)
through (D6) reduce a comprehension in which the leftmost qualifier is a generator. The let-statement
in (D5) binds v to e 0 and uses this binding in every free occurrence of v in \Phif e j r g.
The calculus has a semantic well-formedness requirement that a comprehension be over an idempotent
or commutative monoid if any of its generators are over idempotent or commutative monoids. For
example, is not a valid monoid comprehension, since it maps a set monoid (which
is both commutative and idempotent) to a list monoid (which is neither commutative nor idempotent),
while +fx j x / ff1; 2gg g is valid (since both are commutative). This requirement can be easily
checked during compile time.
When restricted to sets, monoid comprehensions are equivalent to set monad comprehensions [BLS
which capture precisely the nested relational algebra [FM95b]. Most OQL expressions have a direct translation
into the monoid calculus. For example, the OQL query
select distinct hotel.price
from hotel in ( select h from c in Cities, h in c.hotels
exists r in hotel.rooms: r.bed
and hotel.name in ( select t.name from s in States, t in s.attractions
is translated into the following comprehension:
f hotel.price - hotel / f h - c / Cities, h / c.hotels, c.name="Arlington" g,
-f r.bed num=3 - r / hotel.rooms g,
We use the shorthand x j u to represent the binding of the variable x with the value u. The meaning
of this construct is given by the following reduction:
where e[u=x] is the expression e with u substituted for all the free occurrences of x (i.e., e[u=x] is
equivalent to let In addition, as a syntactic sugar, we allow irrefutable patterns in place of
lambda variables, range variables, and variables in bindings. Patterns like these can be compiled away
using standard pattern decomposition techniques [PJ87]. For example, is
equivalent to f a:fst a:snd:fst retrieves the first/second element
of a pair. Another example is -(x; which is a function that takes three parameters and
returns their sum. It is equivalent to -a: a:fst a:snd:fst
The monoid calculus can be put into a canonical form by an efficient rewrite algorithm, called the
normalization algorithm. The evaluation of these canonical forms generally produces fewer intermediate
data structures than the initial unnormalized programs. Moreover, the normalization algorithm improves
program performance in many cases. It generalizes many optimization techniques already used in relational
algebra, such as fusing two selections into one selection. The following are the most important
rules of the normalization algorithm:
reduction (N2)
pred j r for idempotent \Phi (N4)
The soundness of the normalization rules can be proved using the definition of the monoid comprehension
[FM98]. Rule (N3) flattens a comprehension that contains a generator whose domain is another
comprehension (it may require variable renaming to avoid name conflicts). Rule (N4) unnests an existential
quantification.
For example, the previous OQL query is normalized into:
c.name="Arlington", r.bed num=3, s.name="Texas", t.name=h.name g
by applying Rule (N3) to unnest the two inner set comprehensions and Rule (N4) to unnest the two
existential quantifications.
3 The Object Monoid Calculus
In this section, the monoid calculus is extended to capture object identity. The extended calculus is
called the object monoid calculus. For example, one valid object-oriented comprehension is
which first creates a list containing two new objects (new(1) and new(2)). Then, variable x ranges over
this list and the state of x is incremented by one (by x := !x+1). Here x is a reference to the object x while
!x returns the state of the object x. The result of this computation is the list [2; 3]. An object-oriented
comprehension is translated into a state transformer that propagates the object heap (which contains
bindings from object identities to object states) through all operations in an expression, and changes
it only when there is an operation that creates a new object or modifies the state of an object. This
translation captures precisely the semantics of object identity without the need of extending the base
model. It also provides an equational theory that allows us to do valid optimizations for object-oriented
queries.
We introduce a new type constructor obj(T ) that captures all objects with states represented by values
of type T . In addition, we extend the monoid calculus with the following polymorphic operations [Oho90]
(in the style of SML [Pau91]):
ffl new, of type T !obj(T ). Operation new(s) creates a new object with state s;
ffl !, of type obj(T )!T . Operation !e dereferences the object e (it returns the state of e);
ffl :=, of type obj(T )!T !bool. Operation e := s changes the state of the object e to s and returns
true.
Many object-oriented languages have different ways of constructing and manipulating objects. For exam-
ple, OQL uses object constructors to create objects and does not require any explicit object dereferencing
operator. These language features can be easily expressed in terms of the primitives mentioned above.
When giving formal semantics, our primitives are a better choice since they do not deal with details
about object classes, inheritance, etc. When optimizing a real object-oriented language, though, these
"details" should be addressed properly.
Our object-oriented operators may appear at any place in a monoid comprehension. The following are
examples of comprehensions with object operations (called object comprehensions): (Recall that v j e
defines the new variable name v to be a synonym of the value e while e1 := e2 changes the state of the
object whose OID is equal to the value of e1 into the result of e2 .)
true
The first example indicates that different objects are distinct while the second example indicates that
objects may have equal states. The ninth example computes the cardinality of the set f1; 2; 2;
and indicates that duplicates in a set do not count. The last example is the most interesting
one: since there is no order in the set f1; 2; 2; 3g, there are as many results as the permutations of the
set (namely, f1; 3; 6g; f1; 4; 6g; f2; 3; 6g; f2; 5; 6g; f3; 4; 6g and f3; 5; 6g). We consider all these results
valid but the optimizer will construct a plan at the end that generates one result only. A more practical
example is the query
!e:department := !(!e:manager):department g
which sets the department of each employee to be the department of the employee's manager.
4 The State Transformation Monoid
One way of handling side effects in denotational semantics is to map terms that compute values of type
into functions of type S ! (T \Theta S), where S is the type of the state in which all side effects take
place. That is, a term of type T is mapped into a function that takes some initial state s0 of type S as
input and generates a value of type T and a new state s1 . In denotational semantics, these functions
of type \Theta S) are called state transformers [Wad92, Wad90]. If a term performs side effects, the
state transformer maps s0 into a different state s1 to reflect these changes. Otherwise, the state remains
unchanged. For example, the constant integer, 3, is mapped into the state transformer -s:(3; s) which
propagates the state as is. Note that not only the new state, but the computed value as well, may depend
on the input state. That way, side effects are captured as pure functions that map states into new states.
Unfortunately, if we add side effects to our calculus, our programs may have multiple interpretations,
mainly due to the commutativity of monoids, which results to non-determinacy. It is highly desirable
to capture all these interpretations and let the optimizer select the best one at the end. To handle
this type of non-determinism in a functional way, given an input state, our state transformer must be
able to return multiple values and multiple states, or in other words, it must be able to return multiple
value-states pairs. Consequently, our state transformer should be of type S ! set(T \Theta S) to capture all
possible interpretations of a program.
Transformer) The state transformer \Phi(T ) of a type T and a state type S is the
As we will show shortly, given a monoid \Phi for a type T , we can always define a primitive monoid, \Phi,
for the state transformer \Phi(T ). In contrast to the monoids described earlier, this monoid must be a
higher-order monoid, i.e., instances of this monoid are functions.
The definition of \Phi described below is very important for proving the correctness of various transformation
rules. It can be safely skipped if the reader is not interested in such proofs. We will first
present a simple definition that works well for non-commutative, non-idempotent, monoids and then we
will extent it to capture all monoids.
Transformation Monoid) The state transformation monoid of a monoid (\Phi; Z \Phi )
is the primitive monoid (\Phi; Z \Phi ), defined as follows:
That is, Z \Phi is a function that, when applied to a state s of type S, it constructs a value f(Z \Phi ; s)g. The
merge function \Phi propagates the state from the first state transformer to the second and merges the
resulting values using \Phi. It is easy to prove that for n ? 0:
State monoid comprehensions are simply monoid comprehensions over a state transformation monoid.
For example,
+f -s: f(v; s)g j v / [1; 2; 3] g s0
((-s: (-s: f(3; s)g)) s0
The state can be of any type. Suppose that the state is an integer that counts list elements. Then the
following state comprehension increments each element of the list [1; 2; 3] and uses the state to count the
list elements:
++f -s: f([v
((-s:
For the state transformer monoid \Phi to be effective, it must have the same properties as the monoid
\Phi. Otherwise, it may introduce semantic inconsistencies. That is, if \Phi is a commutative or idempotent,
so must be \Phi. To capture this property, we redefine \Phi to behave in the same way as \Phi:
where F and G are defined as follows:
ae
if \Phi is commutative
f g otherwise
ae
g. That is, if \Phi is commutative, then OE 1 \Phi OE 2 has two interpretations:
one propagates the state from OE 1 to OE 2 and the other from OE 2 to OE 1 (this is the contribution of the factor
G). If \Phi is idempotent, then all elements of x are removed from y when x \Phi y is evaluated. For example,
for an integer state that counts set elements we have:
then f(Z \Phi ; s1)g
else
where G propagates the state from right to left and it is equal to f(f1g; s 1)g. That is, the counter
counts the list element 1 once, even though it appears twice.
We prove in the Appendix (Theorem 1) that, under these extensions, not only \Phi is a valid monoid,
but it is also compatible with the \Phi monoid (i.e., if \Phi is commutative and/or idempotent, then so is \Phi).
Capturing Object
So far we have not discussed what the state type, S, should be. Indeed, S can be of any type. If we
wished to capture database updates, for example, the state would have to be the entire database. Here,
though, we are interested in capturing object identity. The state s of a state transformer that captures
object identity can be viewed as a pair (L; n) [Oho90]. The value L, called the object store, maps objects
of type T (i.e., instances of the type obj(T into values of type T . That is, it maps OIDs into object
states. The integer n is a counter used for computing the next available OID.
There are four primitives to manipulate the state, which have the following types:
lookup
ref T (n) maps the integer n into an OID that references an object of type T , emptyStore is the initial
object store value (without any objects), ext T (L; o; v) extends the object store L with the binding from
the OID o to the state value v, and lookup T (L; o) accesses the object store L to retrieve the state of the
object with OID o. For example,
lookup int (ext int (L; ref int (100); 1); ref int (100))
returns 1, the state of the object (of type obj(int)) with OID 100.
The abover primitives satisfy the following equivalences:
ext
ext
lookup
lookup

Figure

1 presents the denotational semantics of the most important constructs of the monoid calculus
without the object extensions (i.e., without new, !, and :=). Without the object extensions, the state

Figure

1: Denotational Semantics of the Monoid Calculus Using State Transformers
should be propagated as is, not changed. The semantics of the object extensions form a non-standard
interpretation and is given later. In these equations, the semantic brackets, give the meaning of the
syntax enclosed by the brackets in terms of the pure monoid comprehension calculus. The type of
is the domain of all type-correct terms in the object monoid calculus that have a
monotype T (a non-function type). In general, if e is of type t, then the type of [[e]], denoted by t   , is
defined as follows:
Recall also that a state s of type S is a pair (L; n); but for convenience, we will only use the notation
(L; n) whenever either of the components L or n needs to be accessed.
Rule (S7) in Figure 1 handles functional terms. For example,
is translated into f(-v:-s 0 :f(v; s 0 )g; s)g when applied to a state s. Rule (S8) assumes a call-by-value
interpretation [Rea89]: e2 in e1(e2) is evaluated before e1 is applied. Rules (S13) and (S14) translate
monoid comprehensions. Rule (S14) uses a monoid comprehension over the monoid \Phi to propagate
the state through every element of the collection u. Notice that the comprehension head here is a state
transformer and all these state transformers are merged using \Phi. This comprehension is valid for any type
of collection u, since the monoid \Phi is compatible with the monoid \Phi. This higher-order comprehension
is necessary since the term u may modify the object store each time a new object is constructed. In most
cases, though, the state is propagated but not changed. If it is not changed, the following rule can be
applied to eliminate state propagation (the correctness of this rule is straightforward and is omitted):
The following rules give the denotational semantics of the object extensions:
The operation new(e) takes an available OID, n, and uses it as the OID of the new object with state e.
In addition, the object store is extended with the binding from ref T (n) to the state value. Rule (S16),
instead of destructively changing the object store, extends the store with a new binding from the OID
of the left part of := to the value of the right part. Rule (S17) simply looks up the object store for the
requested OID.
The Appendix provides a proof of a theorem (Theorem 2) that indicates that, if we have no state
modification operations in the calculus, the output state is the same as the input state and that the
canonical form we derive after normalization is similar to the canonical form we get in the pure monoid
calculus. This theorem basically guarantees that, even though state transformation sequentializes all
operations, if a program does not perform any state modification, the normalization algorithm can
remove all unnecessary state transformations.
The following are examples of translation and normalization of some terms in the object monoid
calculus (where the state s is (L; n)):
A more interesting example is incrementing all elements of a set of integers (of type set(obj(int))):
Set cardinality can be expressed with the help of a counter x:
We can now support bags and sets of objects without inconsistencies. For example, ffnew(1); new(2)gg is
a valid expression and it is equal to ffnew(2); new(1)gg:
Similarly, assignments can be freely moved inside set constructions:
6 Translating Object Comprehensions into Efficient Program

We have seen in the previous section that object-oriented comprehensions can be expressed in term
of the basic monoid comprehension calculus using the denotational semantics rules of Figure 1. The
resulting programs are usually inefficient since they manipulate the state even when the state is not used
at all. These inefficiencies can be reduced with the help of the normalization algorithm and the algebraic
equalities for the object primitives (Rules (O1) through (O5)). In fact, most parts of the resulting
programs can be normalized to first-order programs that look very similar to the programs one might
write using the four object primitives directly. This section is focused on the efficient execution of the
programs that cannot be reduced to first-order programs by the normalization algorithm.
When translating the object monoid calculus to the basic calculus we consider all possible alternatives
due to the commutativity of some operations. This is absolutely necessary for proving program equalities.
After the normalization is completed and the algebraic equalities have been used to check program
equivalences, the optimizer can safely discard all but one alternative. The following function, choose,
selects a random alternative. In practice the choice can be made with the help of a cost function. Given a
program P in the object calculus and an initial state s0 , our system evaluates choose(normalize([[P
That is, P is first translated, then normalized, and finally an alternative is selected (which is a pair of a
value and a state). The choose function is defined as follows:
The rules in Figure 1 guarantee that there will always be at least one choice. The only case missing from
the above rules is choosing an alternative from a state monoid comprehension. These are the state monoid
comprehensions that cannot be removed by the normalization algorithm. Efficient implementation of such
comprehensions is very crucial when considering system performance. The default implementation of a
state monoid comprehension is a loop that creates a state transformer (i.e., a function) at each iteration
and then composes these state transformers using the merge function of the state transformation monoid.
This approach is obviously inefficient and we would like to find better algorithms to evaluate state
comprehensions faster. One possible solution is to actually compile these comprehensions into loops with
updates, like the ones found in imperative languages. In particular,
choose( \Phif -s: e j v /R g s0 )
is translated into the following loop (in a Pascal-like syntax):
initialize the state
res := Z \Phi ; initialize the result value
for each v in R do
retrieve one of the possible value-state pairs
res := res \Phi x.fst; update the result
s := x.snd; update the state
return
For example, as we have previously shown, set cardinality is translated into the following state monoid
comprehension:
which is mapped into the following loop:
res := 0;
for each a in R do
f res := max(res; lookup(L; ref(n))
return (res; (L; n));
Even though this loop has the right functionality, it is still inefficient since it manipulates the object
store L at every step of the loop.
The resulting programs can be implemented efficiently if the store is a global array and the object
primitives are programs that directly manipulate the global array. Rules (S15) and (S16) are single-threaded
(since no object creation is undone at any point). Rule (S17) can enforce a single array pointer
by fetching the state first (using lookup) and then by returning the pointer to L. Consequently, there
will always be only one pointer to the store, and therefore, this store can be implemented as a global
store and all updates as in-place (destructive) updates.
Any primitive operation on the object store can be done destructively. More specifically, let Store be
the global array mentioned above whose domain of elements is of any type (e.g., Store can be defined as
void[ ] in C). The object primitives can be implemented as follows:
lookup
where s 0 is the implementation of s and (s1 ; evaluates the statements in that
order and returns e. For example, lookup T (ext T (ext T (s; x; a);
Under this implementation, the resulting programs after state transformation can be evaluated as efficiently
as real object-oriented programs.
For example, the previous loop that corresponds to set cardinality becomes:
res := 0;
for each a in R do
f res := max(res,Store[n]+1);
return
if we use the global array implementation of the object primitives.
7 Implementation
We have already built a prototype implementation of our framework. The translations of the OODB
queries shown in this paper were generated by this program. The source code is available at:
http://www-cse.uta.edu/~fegaras/oid/
The following examples illustrate the translation of five object queries by our system. The notation
used in these examples is a little bit different than that used in our theoretical framework. Here
executes the statements in sequence and returns the value of v, loop(iterate(x;
executes the statements for each value x of X, access(n) returns the value of Store[n], and
update(n; v) evaluates Store[n] := v. Every object query of type T is translated into an expression of
type T \Theta (void \Theta int). The T value is the returned value, the void value corresponds to the state which is
ignored, and the int value is the new OID counter (we assume that the value of the OID counter before
the execution of the query is equal to n). For example, if an object query e does not contain any object
operation, the translation would be pair(e,pair(null,n)), where pair constructs a pair of two values and
null is of type void.
assign(res,0),
loop(iterate(e,E),
assign(res,max(res,plus(access(n),e))),
assign(s,pair(block(update(n,plus(access(n),e)),null),snd(s)))),
assign(e,struct(bind(name,project(deref(e),name)),
assign(res,0),
loop(iterate(e,Employees),
assign(res,plus(res,if(gt(project(access(e),salary),50000),1,0))),
assign(s,if(gt(project(access(e),salary),50000),
bind(salary,times(project(access(e),salary),1.08)))),
snd(s)),

Figure

2: Denotational Semantics of Database Updates
The first query, new(1), assigns 1 to Store[n] (the store for the next available OID), sets n to n + 1, and
returns the old value of n. The second query executes Store[x] := Store[x] while the third query,
which corresponds to +f !x generates a block that contains both Store[n] := 1
(the old value) and Store[n] := 2 (the new value) that are executed in sequence. The fourth query
generates a state monoid comprehension, which, in turn, is translated into a loop. It returns the sum of
all elements in E. The last query gives an 8% raise to all employees earning over $50000 and returns the
number of employees who got this raise (for simplicity, we assume that each employee has a name and a
salary only).
8 Database Updates and View Maintenance
The monoid state transformer can also be used for expressing destructive database updates in terms
of the basic algebra. That way database updates and queries can be optimized in a single framework.
Let db be the current database state and let DB be its type. Typically, db is the aggregation of all
persistent objects in an application. Following the analysis of the previous section, we want to translate
updates into the monoid algebra in such a way that the propagated state (i.e. the entire database) is
single-threaded. Database updates can be captured using the state transformer
which propagates, and occasionally changes, the entire database. That is, updates are captured as
pure functions that map the existing database into a new database. To make this approach practical,
we can define a set of update primitives to express updates, similar to the ones for object updates.
These primitives, even though have a pure interpretation, they have an efficient implementation. This
approach does not require any significant extension to the formal framework, and normalization and
query optimization can be used as is to improve performance.
Database updates can be expressed using the following comprehension qualifiers [Feg]: qualifier
path := u destructively replaces the value stored at path by u, qualifier path += u merges the singleton
u with path, and qualifier path -= u deletes all elements of path equal to u. The := qualifier is
the only fundamental construct since the other two can be defined as follows:
path += u j path := (U \Phi (u) \Phi path)
path -= u j path := \Phif a j a/path; a 6= ug
For example, the comprehension
c.hotel num += 1 g
inserts a new hotel in Arlington and increases the total number of hotels.
The denotational semantics of an expression e that may contain updates is ae is a binding
list that binds range variables and s is the current database state. Rules (S1) through (S13) in Figure 1
need to be slightly modified to include the binding list ae: every mapped into
example, Rule (S13) in Figure 1 is mapped into the Rule (S13) in Figure 2. Rule (S14) in Figure 1,
though, is mapped into the Rule (S14) in Figure 2, which changes ae to include the binding from v (the
range variable) to v1 (the generator domain). The binding list ae is used in Rule (S15), which gives the
semantics of an update qualifier.
Expression reconstructs the database state s by copying all its components except the
one reached by path, which is replaced by v. It is defined as follows:
and ae(v) is of type T \Phi (t)
where s is of type
where path is a possibly empty path (a sequence of projections). Expression [s=db]ae(v) replaces all
occurrences of db in ae(v) by s. The second rule above applies when the state is a collection type while
the third rule applies when the state is a record. The second rule uses the condition to force
the comprehension, which reconstructs the collection value, to replace the element v (bound before the
update) by the new value e.
For example, at the point of the update c.hotels += . in the previous example, the binding list ae
binds c into db.cities. In that case,
The predicate guarantees that only the hotels of the city c (i.e. Arlington) are changed.
One implementation of P[[path]] ae v s is path := v, which destructively modifies the part of the database
reached by path into v. But we can do better than that. As it was explained in the introduction, our
motivation for using denotational semantics is not to simply give a formal meaning to the destructive
constructs but to use the semantics as the actual translation of these constructs and, more importantly,
to use this translation in query optimization. To do so, we need to define the inverse function, I[[s]],
of P[[path]]. The P[[path]] function is needed to translate updates into programs so that they can be
optimized, while the inverse function, I[[s]], is needed to generate destructive updates after optimization.
Given a reconstruction of a state s, say s 0 , which is a copy of s except of a number of places where new
values v i are used instead, I[[s]] s 0 generates a list of destructive updates of the form path i := v i such
that the composition of all P[[path i constructs the state s 0 . The function I[[e]] is defined as follows:
(++ is list concatenation)
For example, returns [c:hotels := e], which is the original update. Under this
approach, first, the semantics of a program is given in terms of state transformers and the P[[path]] state
reconstructions are expanded; then, normalization and query optimization take place, which eliminate
unnecessary updates; finally, the reconstructed state is transformed into a number of destructive updates
to the database using I[[e]]. We leave it for a future work to demonstrate that this framework is as
effective as the framework for handling object updates.
Our optimization framework for destructive updates can also be used to handle the view maintenance
problem [GM95, CKL97]. In its general form, a view is a function f from the database state db to
some value domain. A materialized view, v / f(db), stores the view f into the database component, v.
Recognizing cases where v can be used directly instead of computing the possibly expensive view f in
a query becomes easier after the query is normalized and unnested (since unnesting flattens a query).
When the database is updated, the new database becomes u(db), where u is the functional interpretation
of the update. Thus, the view maintenance problem is equivalent to expressing f(u(db)) in terms of
the materialized view v (this is the view recognition problem mentioned above), and transforming all
the update primitives in f(u(db)) to apply over v instead of db (easily attainable by expressing our
state transformations in terms of the update primitives and normalizing the resulting forms). That
way, f(u(db)) will compute the new materialized view in terms of the old one, v. If we apply the same
techniques we used for database updates, the new materialized view f(u(db)) can be generated efficiently
using destructive updates to v. We are planning to show in a future research that this framework not
only requires minimal extensions to our basic framework, but is practical and effective as well.
9 Conclusion
We have presented a formal framework for handling object updates during OODB query optimization.
Even though this framework was applied to the monoid comprehension calculus, it can be adapted to
work with any optimization framework because many types of object manipulation constructs can be
expressed in terms of the basic language constructs by using denotational semantics. Consequently,
query optimization applicable to the basic language constructs can be used with minimal changes to
remove inefficiencies due to the compositional way of translating programs in denotational semantics. If,
in addition, we implement the object store primitives using side effects, the resulting programs can be
evaluated as efficiently as programs written by hand.

Acknowledgements

: The author is grateful to David Maier for helpful comments on the paper. This
work is supported in part by the National Science Foundation under grants IRI-9509955 and IIS-9811525.



--R

Rationale for the Design of Persistence and Query Processing Facilities in the Database Programming Language O
Comprehension Syntax.
The Object Database Standard: ODMG-93
A General Framework for the Optimization of Object-Oriented Queries
Efficient Evaluation of Aggregates on Bulk Types.
Nested Queries in Object Bases.
A Recursive Algebra and Query Optimization for Nested Relations.
Supporting Multiple View Maintenance Policies.
Query Optimization in Revelation
A Uniform Calculus for Collection Types.
An Experimental Optimizer for OQL.
Query Unnesting in Object-Oriented Databases
An Algebraic Framework for Physical OODB Design.
Towards an Effective Calculus for Object Query Languages.
Optimizing Object Queries Using an Effective Calculus.
Maintenance of Materialized Views: Problems
Advanced Query Processing in Object Bases Using Access Support Relations.
A Transformation-Based approach to Optimizing Loops in Database Programming Languages
Representing Object Identity in a Pure Functional Language.
A Keying Method for a Nested Relational Database Management System.
ML for the working programmer.
Peyton Jones.
Elements of Functional Programming.
Detecting Global Variables in Denotational Specifications.
Extending Functional Database Languages to Update Completeness.
Comprehending Monads.
The Essence of Functional Programming.


--TR
Detecting global variables in denotational specifications
A recursive algebra and query optimization for nested relations
Comprehending monads
Advanced query processing in object bases using access support relations
Rationale for the design of persistence and query processing facilities in the database programming language O++
Query optimization in revelation, an overview
Representing object identity in a pure functional language
ML for the working programmer
Elements of functional programming
A transformation-based approach to optimizing loops in database programming languages
A general framework for the optimization of object-oriented queries
The essence of functional programming
Comprehension syntax
Towards an effective calculus for object query languages
Supporting multiple view maintenance policies
Query unnesting in object-oriented databases
Optimizing object queries using an effective calculus
A Keying Method for a Nested Relational Database Management System
Extending Functional Database Languages to Update Completeness
An Algebraic Framework for Physical OODB Design

--CTR
Hiroaki Nakamura, Incremental computation of complex object queries, ACM SIGPLAN Notices, v.36 n.11, p.156-165, 11/01/2001
G. M. Bierman, Formal semantics and analysis of object queries, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Leonidas Fegaras , David Maier, Optimizing object queries using an effective calculus, ACM Transactions on Database Systems (TODS), v.25 n.4, p.457-516, Dec. 2000
query optimization;monoid comprehensions;denotational semantics;object identity