The Internet Encyclopedia (Volume 3)

P1: IML/FFX P2: IML/FFX QC: IML/FFX T1: IML

SQL ̇OLE WL040/Bidgolio-Vol I WL040-Sample.cls June 20, 2003 13:16 Char Count= 0

354 STRUCTUREDQUERYLANGUAGE(SQL)

Relational Algebra

Relational algebra “is a collection of operations that are

used to manipulate entire relations....The result of each

operation is a new relation, which can be further manip-

ulated by the relational algebra operations” (Elmasri &

Navathe, 1989, p. 148). This is consistent with the math-

ematical definition of set operators. Relational operators

are often separated into two groups. The first “group in-

cludes set operations from mathematical set theory....

The others consist of operations developed specifically

for relational databases....” (Elmasri & Navathe, 1989,

pp. 148–149).

The set of relational algebra operators includes the

SELECT (σ), PROJECT (π), UNION (∪), DIFFERENCE

(−), and CROSS-PRODUCT (×) operators. “It has been

shown that the set of relational algebra operations{σ,π,

∪,−,×}is acompleteset; that is, any of the other rela-

tional algebra operations can be expressed as asequence

of operations from this set” (Elmasri & Navathe, 1989,

p. 159). An example of a complex relational operator (one

made from this minimal set) is the intersection operator

(∩), which is defined as

R∩S≡(R∪S)−((R−S)∪(S−R))

(Elmasri & Navathe, 1989, p.159).

“The select operation is used to select a subset of

tuples (tuples represent rows in a table) in a relation.

These tuples must satisfy aselection condition” (Elmasri

& Navathe, 1989, p. 149). The general form for the

SELECT operation is σ<selectioncondition>(<relation

name>), where the SELECTIONCONDITION is a

boolean expression made up of clauses of the form

<attribute name><comparison op><constant value>

or <attribute name><comparison op><attribute

name>, where ATTRIBUTE NAME is the name of an

attribute of the<relation name>(Elmasri & Navathe,

1989, p. 149). For ordered domains, such as integer or

date domains,<comparison op>is from the set{=,<,

>,<=,>=,=}. For unordered domains, such as color

={red, blue, green}, the only valid<comparison op>is

from the set{=,=}. Boolean operators AND, OR, and

NOT are used to connect the selection condition clauses

together. An example of a table of tuples is as follows:

name sex address

Smith M Lexington Park

Taylor M Detroit

Burr M Lusby

Malcolm M Akron

Tefft M Ridge

Carpenter M Lexington Park

Lucas M Hollywood

An example of the selection operation is as follows:

Give me all candidates who are male.

[select] σ(sex="M")(CANDIDATE)

The PROJECT operation is used to select a subset

of attributes in a relation. The general form for the

projection operator isπ<attributelist>(<relation name>).

Only attributes that are part of the relation are valid in

the attribute list. If duplicate tuples appear in the result

relation, all but one instance of the tuple will be removed,

enforcing the mathematical set definition, which allows

no duplicate items.

An example of the projection operation:

Where do the candidates live?

[project]πAddress(CANDIDATE)

address

Lexington Park

Washington DC

Detroit

Hollywood

Lusby

Pittsburgh

Cherry Valley

Akron

Ridge

As stated previously, all relational operators may oper-

ate on the results of previous relational operators.

Examples involving both select and project operators:

Give me all of the names and addresses of

the candidates that live in Hollywood.

πName,Address(σ(address="Hollywood")(CANDIDATE))

name address

Rupert Hollywood

Day Hollywood

Lucas Hollywood

The above relational operators are unary, operating on

only one relation at a time. The rest of the relational op-

erators are binary, operating on two relations at a time.

The UNION and DIFFERENCE operators require that

the relations also be union-compatible. The UNION op-

eration returns all tuples (rows) that are either in R or

S, or in both R and S. Enforcement of the set defini-

tion eliminates duplicate tuples. The difference operation

returns all tuples that are in R but not S. The CARTE-

SIAN PRODUCT operation returns all possible tuple com-

binations between R and S. The resulting relation has

all attributes from both relations and the new tuples are

of the form (tuple (^1) R, tuple (^1) S), (tuple (^1) R, tuple (^2) S), (tuple (^2) R,
tuple (^1) S), (tuple (^2) R, tuple (^2) S),...(tuplemR, tuplenS).
The JOIN operator (ξ) is used to combine related tuples
from two relations into single tuples (Elmasri & Navathe,
1989, p. 157). The JOIN returns all possible tuple combi-
nations from R and S where the combination satisfies the
JOIN CONDITION. An example JOIN is RξS.
JOIN CONDITIONS are of the form ARθAS, where ARand