Solving Equations in the Relational Algebra.
Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query language for nested relational databases, equivalent to the well-known powerset algebra.  We study sparse equations, which are equations with at most polynomially many solutions.  We look at their complexity and compare their expressive power with that of similar notions in the powerset algebra.
Introduction
Suppose we are allowed to see only a view on
a database B, computed by a relational algebra
expression e. If we still want to find out
what B is, we might try to "invert" e (assum-
ing we know this expression), which will only
work when we also know the finite domain D of
B. Specifically, we can enumerate all databases
over D, and test for each X whether it satisfies
the equation e(B). One of these
solutions will be B of course, so if the set of
all solutions is not too big, it might provide us
with useful information to start our detective
work.
The above simple scenario from database security
led us to wonder what can be said in general
about the solution of equations in the relational
algebra. Generally, if e 1 and e 2 are two
algebra expressions over the database schema
augmented with some relation variables X 1 ,
, we can consider the equation e
A solution of this equation, given a database B
with finite domain D, is a tuple (X
of relations over D such that e 1 and e 2 evaluate
to the same relation on the augmented database
Asking whether there exists a solution of a
relational algebra equation on a database is almost
exactly the same thing as asking whether
an existential second-order logic sentence is true
on that database. Hence, by Fagin's theorem
[Fag74, EF95], the problems that can be formulated
as finding a solution of some relational
algebra equation are nothing but the problems
in NP.
However, in the present paper, we start from
the observation that the set of all solutions of
an equation, being a set of tuples of relations,
is a nested relation. One can therefore consider
the enumeration of all solutions of an equation
as a query language primitive, which can be
added to the nested relational algebra. We introduce
and study this extension of the nested
relational algebra, which we call the equation al-
gebra. The equation algebra is extremely pow-
erful: it is equivalent to the well-known power-set
algebra for nested relations. Our particular
interest, however, is in what can be expressed
in the equation algebra by using only equations
that have a solution set of polynomial size on
each database. We call such equations sparse.
Our interest in sparse equations does not
stem from time efficiency considerations. In-
deed, it is not obvious how knowing that an
equation is sparse would help in actually finding
even one solution more quickly. It is neither
obvious, however, that it would not help. For
example, consider the problem of checking on
a given database whether some fixed sparse relational
algebra equation has a solution. Using
an extension of Fagin's theorem to nested relational
databases, we show that this problem
can be NP-hard only if every problem in NP
can already be decided by a polynomial-time
non-deterministic Turing machine that has only
polynomially many accepting computations on
each input. The latter is one of the many unresolved
questions in computational complexity
theory [All86].
Nevertheless, sparse equations are still interesting
from a space efficiency standpoint. In-
deed, for the natural evaluation strategy for
equation algebra expressions to run in polynomial
space, it is necessary that all equations
occurring in the expression are sparse. Interest
in fragments of powerful query languages
for which the natural evaluation strategy is
polynomial-space is not new to database theory
research. For example, Abiteboul and Vianu
[AV91] showed that the parity query is not expressible
in the polynomial-space fragment of
various computationally complete query languages

Closer to our topic is the work of Suciu
and Paredaens [SP97], who showed that queries
such as transitive closure and parity are not expressible
in the polynomial-space fragment of
the powerset algebra for nested relations. 1 This
fragment consists of all powerset algebra expressions
where all intermediate results are of
polynomial size, on each database. We also
mention Grumbach and Vianu [GV95], who
also studied a sparsity notion in connection
with queries over nested relational databases,
although they considered sparsity as a property
of databases rather than of query language expressions

Suciu and Paredaens conjectured in general
that the polynomial-space fragment of the powerset
algebra has no more power than the nested
relational algebra without powerset. (This
conjecture has been confirmed for monadic
database schemas [VdB].) At first sight, the
operator that we add to the nested relational
algebra, to enumerate all solutions of an equa-
tion, does not seem to be that different from
the powerset operator. After all, both operators
perform some kind of potentially exponential
enumeration.
Yet, as we will point out, the analogue of
the Suciu-Paredaens conjecture does not hold
for the sparse fragment of the equation alge-
bra. Specifically, using sparse equations only,
we can express transitive closure; in fact, we can
express any fixpoint query. This complements
a result by Abiteboul and Hillebrand [AH95],
who showed that transitive closure becomes
This fragment does make sense: there are expressions
that always produce a result of logarithmic size.
Applying the, exponential, powerset operator to such
expressions produces a result of polynomial size.
expressible in the powerset algebra in polynomial
space, provided we use a more clever
"pipelined" evaluation strategy. Actually, every
fixpoint query is already expressible using
equations that are not just sparse, but even
unambiguous: they have a unique solution on
each database. Unambiguous equations in the
relational algebra are known as implicit definitions
in first-order logic, and were studied in
the context of finite model theory by Kolaitis
[Kol90]. Kolaitis already showed that every fixpoint
query can be implicitly defined. We offer
a straightforward, direct proof.
Another example is given by the well-known
nesting operator of the nested relational alge-
bra. This operator becomes redundant once
we extend the algebra with the solution operator
or with the powerset operator. How-
ever, the original nesting operator never blows
up exponentially. We show that, without using
the nesting operator itself, nesting is expressible
in the equation algebra using sparse equations
only, but that the same is not possible with a
polynomial-space powerset algebra expression.
However, there are also similarities between
the two fragments. Specifically, we prove an
analogue to the Suciu-Paredaens result, to the
effect that the parity query is not expressible
in the sparse fragment of the equation algebra
either. This is our main technical contri-
bution. The proof involves an elegant argu-
ment, in the style of Liebeck [Lie83], invoking
Bochert's theorem on the order of primitive permutation
groups.
This paper is organized as follows. Section
2 recalls the nested relational data model.
Section 3 introduces relational algebra equa-
tions. Section 4 introduces the equation al-
gebra. Section 5 introduces sparse equations,
as well as the natural evaluation strategy for
equation algebra expressions. Section 6 studies
the time complexity of sparse equations. Fi-
nally, Section 7 presents the comparison with
the polynomial-space powerset algebra.
An appendix with additional details complements
the main body of the paper.
Preliminaries
We quickly recall the nested relational data
model and algebra [TF86, AHV95].
Relation types are defined as follows. The
are types,
then so is (-
set D of atomic values, the relations of type -
on D are inductively defined as follows. A relation
of type 0 on D is just an element of D
(this serves merely as the base case for the in-
duction). A relation of type (-
is a set of k-tuples
a relation of type - i on D, for
A database schema is a finite set S of relation
names, where each relation name has an associated
type different from 0. A database B over
S consists of a non-empty finite domain D of
atomic values, together with, for each relation
name R in S, a relation R B of type - on D,
where - is the type of R.
The operators of the nested relational algebra
are those of the standard relational algebra
(union [ and difference \Gamma of relations of
the same type; cartesian product \Theta; projection
selection oe for equality), plus the operators
nesting - and unnesting -, defined as follows.
Let R be a relation of type (-
kg. Then the nesting
(R) equals the relation
ni
and x each
of type (-
)).
Let R be as above, and let i
that - i 6= 0; so - i is of the form (!
Then the unnesting - i (R) equals the relation
of type (-
The expressions of the nested relational algebra
over a schema S are now built up using the
above operators from the relation names in S
and the symbol D, which stands for the finite
domain of the input database. The relation to
which an expression e evaluates on a database
B is denoted by e(B).
One can extend the nested relational algebra
to the powerset algebra by adding the power-set
operator, defined as follows. Let R be a
relation of type (- Then the powerset
\Pi(R) equals the relation f(S) j S ' Rg of type
Equations
Let S and X be disjoint database schemas; S is
the actual database schema, while X is thought
of as a set of additional relation variables. Let
e 1 and e 2 be two expressions over the expanded
We define
Definition 3.1. Given a database B over S, a
solution to the equation e database A
over X with the same finite domain as B, such
that e 1 (B;
Here, (B; A) denotes the expansion of B with
A, i.e., the database over S [ X that has the
same finite domain as B, that equals B on S,
and that equals A on X .
Example 3.2. For a very simple example, let
has the
same type as R. Then X is an equa-
tion. Given a database B over S, a database A
over fXg is a solution if and only if X A ' R B .
For another example, let X be a relation variable
of type (0; 0). One can write a relational
algebra expression e such that on any database
A over fXg with finite domain D, e(A) is empty
if and only if X A is one-to-one, the projections
are disjoint, and their
union equals D. Then the equation
a solution on a database B with finite domain
D if and only if the cardinality of D is even.
(Technically, is not an equation because
the symbol ; is not an expression, but we can
easily take ; here to stand for some arbitrary
expression that always evaluates to the empty
relation.)
Remark 3.3. In the above example, we used an
equation of the special form e = ;. Actually,
this form is not so special at all, because any
equation can be brought in this form as
stands for
Alternatively, one might wonder about the
use of disequations, of the form e 6= ;. These
are nothing but equations in disguise, because
they can also be written as - 1 (D \Theta
Conversely, any equation e can also be
written as the disequation (D \Theta (e 1 \Delta
4 The equation algebra
We are now ready to extend the nested relational
algebra with a solution operator for equa-
tions. We refer to the resulting algebra as the
equation algebra.
To allow for an elegant definition, we do not
fix a schema S in advance. Rather, we assume
a sufficiently large supply of relation names of
all possible types. Any relation name can now
occur in an expression. Like in logic formu-
las, some will occur free and others will occur
Bound relation names are bound by
the solution of an equation, and serve as the
variables of the equation. Within the equation,
however, they are still free. We denote the set
of relation names that occur free in an equation
algebra expression e by free(e).
For the constructs of the nested relational al-
gebra, this is all straightforward: for a relation
name R, we have free(R) := fRg; for expressions
e of the form (e 1
we have free(e) := free(e 1 )[free(e 2 ); for expressions
e of the form oe(e 0
we have free(e) := free(e 0 ). For the expression
D, we have free(D) := ;.
The definition of the new solution operator is
now the following:
Definition 4.1. Let e 1 and e 2 be expressions,
and let be a sequence of distinct relation
names. Then
is also an expression. We define its free set as
g. We say that
the
Note that this is a recursive definition, in the
sense that e 1 and e 2 can contain solution operators
in turn. To avoid clutter, we disallow equation
algebra expressions in which a free relation
name at the same time becomes bound in some
subexpression, as in X \Theta f(X)
An expression e in the equation algebra can
be evaluated on databases B over any schema
that contains free(e). We already know how
this evaluation is defined for the constructs of
the nested relational algebra. So we only have
to define
Definition 4.2. For a solution expression, e,
of the form f(X
database B, the evaluation e(B) equals the re-
lation
A is a database over fX
and is a solution of
This relation is of type (-
the type of X i for
Example 4.3. Recall the simple example equation
3.2. We can
turn this equation in the following equation algebra
expression e:
that fRg. On any database B over
fRg, the relation e(B) equals \Pi(R B ) (recall
the powerset operator \Pi from Section 2). In
other words, the equation algebra expression e
is equivalent to the powerset algebra expression
\Pi(R).
The equation algebra allows equations to be
used inside equations. For example, if we want
to compute the powerset of the powerset of R,
we can write:
As a third example, let R and T be relation
names of the same binary type (-
One can write a relational algebra expression
e tc such that on any database C over fR; Tg,
e tc is empty if and only if R C ' T C and T C is
transitively closed. One can also write a nested
relational algebra expression e min that selects,
out of a set of binary relations, the minimal ones
w.r.t. set inclusion. Then the following equation
algebra expression computes the transitive
closure of relation R:
In the above example we saw that the power-set
operator is expressible in the equation alge-
bra. Conversely, the solution operator is easily
expressed in the powerset algebra. Hence,
Proposition 4.4. The equation algebra is
equivalent to the powerset algebra.
5 Sparse equations
So far, the equation algebra is merely another
syntax for the powerset algebra, or, if you want,
higher-order logic. However, when we consider
a natural evaluation strategy for equation algebra
expressions, we start to notice some differences

By the natural strategy to evaluate a solution
expression of the form f(X
we mean the following. Enumerate
all databases A over fX g, on the finite
domain of the given input database, one
by one, reusing the same space. For each A we
test whether it is a solution (by recursively evaluating
e 1 and e 2 ), and if so, we include it in the
result.
For the constructs of the nested relational al-
gebra, the natural evaluation strategy is clear:
if we have to evaluate an expression of the form
create two intermediate
results by recursively evaluating e 1 and
apply \Theta to these two intermediate
results. Similarly, if we have to evaluate an expression
of the form '(e), with ' 2 f-; oe; -g,
we create an intermediate result by recursively
evaluating e, and then apply ' to this intermediate
result.
In view of this natural evaluation strategy,
we now define
Definition 5.1. An equation is called sparse
if all its relation variables are of flat type, i.e.,
of type of the form and the number
of solutions on any given database is at most
polynomial in the size of that database.
Example 5.2. The two equations from Example
3.2 are not sparse. Probably the simplest
example of a non-trivial sparse equation is the
following. Let X be a relation name of type
(0). One can write a relational algebra expression
e over fXg such that on any database A
over fXg, e(A) is empty if and only if X A is a
singleton. Then the equation
taken as the relation variable to be solved for,
is sparse. Indeed, given any database B with
finite domain D, the solutions are precisely all
singleton subsets of D. There clearly are only
a linear (and thus at most polynomial) number
of possible solutions.
Remark 5.3. One may wonder whether the notion
of sparsity would change if, in Definition
5.1, we would look only at databases over
the schema consisting of the relation names that
actually occur free in the equation. The answer
is easily seen to be negative.
Sparse equations are connected to the natural
evaluation strategy in the following way:
Proposition 5.4. The natural strategy to evaluate
an equation algebra expression e runs in
polynomial space, if and only if all equations
occurring in e are sparse.
Here, we count not only the space occupied
by the intermediate results stored during eval-
uation, but also the size of the final result. The
if-direction of this Proposition is clear; the only-if
direction is proven in the Appendix.
6 Time complexity of equation
nonemptiness
The time complexity of solving sparse equations
is closely linked to an open question from computational
complexity theory. Unlike the previous
section, in this section we are not talking
about the natural evaluation strategy, whose
time complexity is clearly at least exponential
as soon as there are equations to be solved.
Instead, we will be looking at the time complexity
of the nonemptiness problems of equa-
tions. The nonemptiness problem of an equation
over a schema S with relation variables X
is the problem of deciding, given a database
over S, whether the equation has a solution
on that database. In the present section we
will only consider equations that do not contain
equations inside.
Let us begin by considering equations that
are not necessarily sparse, but that still have
only flat variables. The nonemptiness problem
of such a flat-variable equation is clearly in
NP. Now suppose, moreover, that the database
schema S is also flat; then S[X (the expansion
of S with the relation variables of the equation)
is an entirely flat schema. Of course, the equation
still in general in the nested
relational algebra, i.e., e 1 and e 2 can contain
- and - operators. A result by Paredaens and
however, implies that the
nested relational algebra condition e
also be expressed in the form e 6= ;, with e a flat
relational algebra expression. The nonemptiness
problem of the equation thus amounts to
asking whether f(X on a
given database B over S. Equivalently, we
ask whether the existential second-order logic
sentence is true on B,
where ' e is a first-order logic sentence expressing
that e 6= ;. Moreover, by the equivalence of
relational algebra and first-order logic, any 9SO
property can be obtained in this way. Now, Fa-
gin's theorem [Fag74, EF95] states that 9SO
captures exactly the NP properties of flat relational
databases. Hence, the class of nonemptiness
problems of flat-variable equations over flat
database schemas is exactly the class of NP
properties of flat relational databases.
What if S is not necessarily flat? We next
show that we still get exactly NP. In essence,
this is an extension of Fagin's theorem to nested
relational databases.
Proposition 6.1. Every property of nested relational
databases over some fixed schema S,
which is in NP and closed under isomorphism,
corresponds to the nonemptiness problem of
some flat-variable equation over S.
The crux of the proof of this Proposition,
given in the Appendix, is a representation of
nested relational databases by "pseudo-flat"
ones, also used by Gyssens, Suciu, and Van
Gucht [GSVG95].
We are now ready to turn to sparse equations.
Their nonemptiness problem is not just in
but actually in the complexity class FewP
[All86], consisting of all problems that can be
decided by a polynomial-time non-deterministic
Turing machine that has at most polynomially
many accepting computations on each input.
Clearly, but the strictness
of these inclusions remains open.
The obvious question to ask is whether
Proposition 6.1 remains true if we focus on
sparse equations, and replace 'NP' by `FewP.'
The answer is an easy "yes," but then we
must restrict attention to ordered databases:
databases that include a total order on their
finite domain as one of their relations. In-
deed, the usual proof of Fagin's theorem yields
the FewP version of that theorem, restricted
to ordered databases, for free. This is for
flat databases; for general nested relational
databases we use the same representation technique
as in the proof of Proposition 6.1. As a
corollary, we get
Corollary 6.2. There exists a sparse equation
whose nonemptiness problem is NP-complete, if
and only if
7 Sparse equations versus
sparse powerset expressions
Naturally, we call an equation algebra expression
sparse if all equations occurring in it are
sparse, cf. Proposition 5.4. Inspired by that
Proposition, we can also define a sparsity condition
on powerset algebra expressions: call a
powerset algebra expression sparse if its natural
evaluation strategy (defined in the obvious
way) runs in polynomial space.
Remark 7.1. Using standard techniques one
can show that sparsity is undecidable, for equation
algebra expressions as wel as powerset algebra
expressions. Related questions are also typically
undecidable, for example, testing whether
a given expression is equivalent to a sparse one.
Suciu and Paredaens [SP97] showed that
transitive closure of a flat binary relation is not
expressible by a sparse powerset expression. In
Example 4.3, we gave an obvious equation algebra
expression for transitive closure, but that
expression was not sparse. We can do better:
Proposition 7.2. Transitive closure of a flat
relation is expressible by a sparse equation algebra
expression.
Proof. Given a binary relation R and a natural
number n - 1, we define the relation R n as
is the classical
composition operator of binary relations: S ffi
Further, define R -n as
that R -jRj equals the transitive closure of R,
and that for n ? jRj, R -n
Now consider the following 6-ary relation
Run:
Run :=
R -i \Theta R -i+1 \Theta R =i+1 :
In the Appendix, we show that there is an equation
whose only solution, given R, is Run. This
proves the Proposition, because all we then
have to do is unnest the solution set and project
on the middle two columns to get the transitive
closure. (The only exception is when Run is
empty, in which case the transitive closure of R
is R itself, but this can also easily be tested in
the nested relational algebra.)
Remark 7.3. The equation constructed in the
above proof is not only sparse, it is unam-
biguous: it has a unique solution on each input
database. Moreover, the same proof works
more generally for any fixpoint query [AHV95]
on flat databases. The only difficulty is that
fixpoint queries start from the empty relation,
while in our proof of Proposition 7.2 we start
from R, but that is easily dealt with. As already
explained in the Introduction, we thus basically
rediscovered an earlier result by Kolaitis to the
effect that every fixpoint query is implicitly definable
in first-order logic [Kol90]. But note the
directness of our proof, straightforwardly specifying
the run of the fixpoint computation in
an unambiguous way. The original proof (also
presented by Ebbinghaus and Flum [EF95]) is
a bit more roundabout, specifying the "stage
comparison" relation instead.
Another, perhaps a bit frivolous, example of
a query that is expressible using sparse equations
but not using sparse powerset expressions
is the nesting operator -. It is easy to express
- in the powerset algebra using the powerset
operator and the other operators, but not - it-
self; so - is not primitive in the powerset al-
gebra. As a consequence (Proposition 4.4), -
is not primitive in the equation algebra either.
We next observe that when we restrict to sparse
expressions, nesting remains imprimitive in the
equation algebra, but becomes primitive again
in the powerset algebra.
Proposition 7.4. Nesting is not expressible by
a sparse powerset expression without using the
- operator itself.
The proof of this Proposition, given in the
Appendix, is a standard argument in finite
model theory, involving quantifier elimination
on monadic structures.
Proposition 7.5. Nesting is expressible by a
sparse equation expression without using the -
operator itself.
Proof. Let R be a relation name of type (0; 0),
and let X and Y be relation variables of type
(0). We can write a relational algebra expression
e such that on any database C over
fR; X;Y g, e(C) is empty if and only if X is a
singleton fxg with x
Rg. Hence, the expression
is a sparse equation expression equivalent to
The construction for general nesting operations
is analogous.
Our final, and main technical, contribution
concerns the parity query. Suciu and Paredaens
showed that the parity of the cardinality of a finite
set is not expressible by a sparse powerset
expression. We show the analogue for the equation
algebra:
Proposition 7.6. The parity query is not expressible
by a sparse equation expression.
Proof. Suppose, to the contrary, that we have a
sparse equation expression to express the parity
of the cardinality of a finite domain D. We may
assume that the input schema is empty, i.e., an
input database consists of D and nothing else.
Consider the innermost equation occurring in
our expression. As in Section 6, it can be written
in the form f(X
e is a flat relational algebra expression over the
flat schema fX g.
Now let A be a solution, given an input D of
size n. Then for every permutation f of D, f(A)
is also a solution. The number of different such
is precisely n!=jAut(A)j, where Aut(A) is
the group of automorphisms of A. Since the
equation is supposed to be sparse, this number
is at most n ' for some fixed ', or, equivalently,
Putting
sufficiently large
n.
We thus need to know more about large permutation
groups. The following crucial lemma,
proved in the Appendix, will give us the information
we need. The group of permutations of
a finite set D is denoted by Sym(D), and its
alternating subgroup of even permutations by
Alt(D). If G is a subgroup of Sym(D), a fixed
set for G is a subset \Delta ' D, such that every
maps \Delta to \Delta. The action of G on a fixed
set \Delta (as a subgroup of Sym(\Delta)) is denoted by
G \Delta .
Lemma 7.7. Let k be a fixed natural number.
Let G be a subgroup of Sym(D),
sufficiently large. Then jGj - (n \Gamma k)! implies
the existence of a fixed set \Delta with
such that G \Delta contains Alt(\Delta).
Invoking this Lemma for
get a fixed set \Delta of size n \Gamma k such that any
even permutation of \Delta can be extended to an
automorphism of A.
Now let X be one of the relation variables
of the equation, of arity, say, r, and consider
any r-tuple t whose components are either the
or are in D \Gamma \Delta. Let r 0 be the number
of components that are the symbol  . Further,
let - be an equality type of r 0 -tuples. Denote
by Neighbors A
(t; -) the set of r 0 -tuples over \Delta
of equality type - such that, if we replace the
-components of t by the components of the r 0 -
tuple (from left to right), we get a tuple in A X .
The following claim is proven in the Appendix:
7.8. Neighbors A
(t; -) is either empty,
or consists of all r 0 -tuples over \Delta of equality
type -.
We call (t; -) an r-ary pattern. If
Neighbors A
(t; -) is nonempty (and thus full),
we say that the pattern is instantiated in X A .
Note also that the extreme cases, where t consists
exclusively of stars or where t has no star
at all, are also allowed and make sense.
By the above, we thus see that any solution
A can be generated by the following non-deterministic
procedure:
1. Initialize all relations of A to empty.
2. Choose k different elements from D, playing
the role of the elements outside \Delta.
3. For every relation variable X (of arity r,
say), run through all r-ary patterns, and
for each of them, non-deterministically instantiate
it in X A , or not.
are fixed, the number
of possible patterns is also fixed. Hence,
we can write an expression in the nested relational
algebra that, given D, constructs the
set of all possible outputs A of the above non-deterministic
procedure. This set is a superset
of the solution set of the equation. Selecting
these solutions using the nested relational algebra
is also an easy matter.
Hence, we can get rid of the innermost equa-
tion. Repeating this process, we can get rid of
all equations, so that in the end we are left with
a standard nested relational algebra expression
for the parity query. But this is well known to
be impossible [AHV95].

Acknowledgment

We are indebted to L'aszl'o Babai, who pointed
us to Liebeck's paper.



--R

Space usage in functional query lan- guages
Foundations of Databases.
The complexity of sparse sets in P.
Generic computation and its complexity.
Finite Model Theory.
Generalized first-order spectra and polynomial-time recognizable sets
The restricted and the bounded fixpoint closures of the nested relational algebra are equivalent.
Tractable query languages for complex object databases.
Implicit definability on finite structures and unambiguous computations.
On graphs whose full automorphism group is an alternating group or a finite classical group.
Converting nested algebra expressions into flat algebra expressions.
The complexity of the evaluation of complex algebra expressions.
Nested relational structures.

Finite Permutation Groups.
--TR
sparse expression;parity;equation;fagin's theorem;relational algebra;nested relation