Relational Algebra

Attribute

An atomic value.

Domain

Allowed values for a given attribute. null is a special value which is an element of all domains.

Relation Schema

A set of attributes. Denoted as $R(A_1, A_2, \ldots, A_n)$ .

Relation

Given a set of relation schemas $D_1, D_2, \ldots, D_n$ , a relation is a subset of $D_1 \times D_2 \times \ldots \times D_n$ .

r \subseteq D_1 \times D_2 \times \ldots \times D_n

A set of n-tuples.

Tuple

Represents a record. Element of a relation.

t = (a_1, a_2, \ldots, a_n)\;\text{where} a_i \in D_i

Relation Instance

Current values of a relation. Represented by a table.

Keys

Let $K \subseteq R$ .

Superkey

$K$ is a superkey iff values for $K$ are sufficient to identify a unique tuple of each possible relation $r(R)$ .

$K$ is a superkey iff:

\forall t_1, t_2 \in r, t_1[K] = t_2[K] \implies t_1 = t_2

No two different tuples have the same values for attributes in $K$ .

Candidate Key

A minimal superkey. $K$ is a candidate key iff:

$K\,\text{is a superkey}$ AND
$\nexists\, K' \subset K, K'\,\text{is a superkey}$

Primary Key

A superkey that is chosen as the main identifier of tuples in $R$ . Depends on the attributes.

Foreign Key

Value in one relation must appear in another.

A theoritical procedural query language. Defines a set of operations that take one or more relations as input and produce a new relation as output.

Selection

Extracts tuples (rows) satisfying a specified condition. Denoted by $σ$ .

σ_{\text{condition(s)}}(R)

Projection

Extracts specific attributes (columns) from a relation. Denoted by $π$ .

π_{\text{attribute list}}(R)

Duplicates are removed by default, as it is a set. Useful for narrowing down the output to required columns.

Union

Combines tuples from two relations. Denoted by $\cup$ .

R \cup S

Result includes all tuples that appear in either or both relations. Both relations must be union-compatible.

Union Compatible

2 relations are union-compatible iff both have the equal number of attributes and associated attributes have equivalent domains.

Set Difference

Finds tuples that appear in one relation but not in another. Denoted by $-$ .

R − S

Requires union compatibility. Used to find “exclusive” records.

Cartesian Product

Combines every tuple of one relation with every tuple of another. Denoted by $\times$ .

R \times S

If $R$ has $m$ tuples and $S$ has $n$ tuples, result has $m × n$ tuples. Attributes of both relations are concatenated.

Rename

Assigns new names to relations or attributes. Denoted by $\rho$ .

\rho_{\text{newName(attribute-list)}}(R)

Used to avoid ambiguity, especially in self-joins or nested queries.

Natural Join

Combines tuples from two relations based on matching attribute names and matching values. Denoted by $⋈$ .

R ⋈_{\text{condition}} S

Division

Finds tuples in one relation associated with all tuples in another. Denoted by $\div$ .

R \div S

Typically, $R$ has attributes $(A, B)$ and $S$ has attributes $(B)$ . Result contains those $A$ values that appear with every $B$ value in $S$ .