Database Reference
In-Depth Information
•
Projection
. This operation is applied to a single
n
-ary relation and only keeps some of
the columns. More precisely, if
i
1
,...,
i
k
is a set of numbers between 1 and
n
,and
U
is
an
n
-ary relation, then
π
i
1
,...,
i
k
(
U
) is a
k
-ary relation defined as follows:
π
i
1
,...,
i
k
(
U
)=
{
(
c
i
1
,...,
c
i
k
)
|
(
c
1
,...,
c
n
)
∈
U
}
.
•
Selection
. This operation is applied to a single
n
-ary relation and only keeps tuples that
satisfy some conditions. The basic conditions are of the form
i
=
j
or
i
=
c
;theseare
true in a tuple (
c
1
,...,
c
n
) if
c
i
=
c
j
or
c
i
=
c
, respectively. A condition is a conjunction
of basic conditions. Given such a condition
θ
, the selection operation
σ
θ
is defined as
σ
θ
(
U
)=
{
(
c
1
,...,
c
n
)
∈
U
|
(
c
1
,...,
c
n
) satisfies
θ
}
.
•
Cartesian product
. This is the standard Cartesian product that takes an
n
-ary relation
U
and an
m
-ary relation
U
and produces an
n
+
m
-ary relation
U
×
U
=
(
c
1
,...,
c
n
,
c
n
+1
,...,
c
n
+
m
)
.
(
c
1
,...,
c
n
)
U
(
c
n
+1
,...,
c
n
+
m
)
∈
U
∈
U
of two relations of the same arity.
•
Union
. This is the union
U
∪
U
has
•
Difference
. Again, this operation is applied to relations of the same arity:
U
−
tuples that occur in
U
but do not occur in
U
.
Relational algebra is a procedural language: its queries transform data, to obtain answers
to queries written declaratively. For example, the declarative query
(2.1)
, written in logical
notation, is equivalent to the following relational algebra query:
π
2
σ
2=6
(
R
R
)
.
×
By taking the product
R
R
, we create a relation with six attributes. If we look at the
logical query, the variable
x
occurs in positions 2 and 6, so we must ensure they are equal.
Then only variable
x
is kept in the output.
The operation obtained by taking the product of two relations, and then selecting tuples
that satisfy some condition - typically equality of attributes - is usually referred to as a
join
. For example,
×
R
) is a join of two copies of
R
.
The classical result of database theory states that relational calculus and relational alge-
bra queries are equivalent: that is, for each relational calculus query there exists an equiva-
lent relational algebra query, and vice versa. That is, declarative queries written in relational
calculus have procedural implementation in relational algebra.
σ
2=6
(
R
×
Conjunctive queries
This is an extremely important subclass of relational calculus/algebra queries. They are the
basic building block for most queries run by relational DBMSs, and they play a special
role in data exchange.
Formally, conjunctive queries are defined as the
∃
,
∧
-fragment of relational calculus:
