# Relational Model

## Tuples

A tuple is an unordered set of triplets (also called *components*) consisting
of attribute names, types, and values . It loosely corresponds to the
concept of a “row” in SQL. A tuple is also a functional mapping from attributes
to their respective values.

Given a tuple :

- Attribute names are unique:
- The values of each triplet are of the right type:

A pair is an *attribute* of a tuple if the tuple has a
matching triplet: . The set of all
attributes of a tuple is the *heading* of .

The type of a tuple of determined by its heading. Two tuples and are of the same type iff .

Every subset of a tuple is also a valid tuple, including the empty set (the zero-tuple).

### Degree (or Arity)

The arity or degree of a tuple is its set cardinality, which corresponds to the number of triplets it contains.

Notice that the degree of a tuple is also equal to the set cardinality of its heading: .

### Equality

Two tuples and are considered equal if they share the same heading and attribute values:

### Zero Tuple

The unique tuple with arity zero is called the *nullary* or *zero* tuple. Its
heading is the empty set: .

## Attributes

An attribute is a pair where is the attribute name and corresponds to its type.

### Closure

Given a relation and a set of attributes , the
closure of under a set of functional dependencies is the
family union of all the attributes that are *dependent* of in :
.

If then is a *super key* for .

## Headings

A heading is a set of attributes . The heading of a tuple determines the type of the tuple and its equal to its set of attributes: .

Given a heading :

- Attribute names are unique:
- All subsets of a heading are also valid headings

## Relations

A relation is an object containing a *heading* and a *body* where
the body is an unordered set of *tuples* (which means no duplicates), and where
and . The type of a relation is
determined by the type of its heading.

Given a relation :

- Each tuple’s heading matches the relation heading:
- Every subset of is also a valid body

### Keys

#### Super Keys

Given a relation , a set of attributes is a
*super key* for if all the attributes of are funtionally dependent
on . More formally: .

In terms of candidate keys, super keys are sets of attributes that contain some candidate key as a subset.

#### Candidate Keys

A candidate key is an *irreducible* super key. Given a relation , a set of
attributes is a *candidate key* for it is the
minimal such that .

### Operations

#### Cardinality

The cardinality of a relation is equal to the cardinality of its body: .

#### Degree (or Arity)

The arity or degree of a relation is equal to the arity of its heading: .

#### Membership

Given relation and tuple , we may use the set membership operator to express that a relation contains a tuple in its body: .

#### Equality

Two relations and are considered equal if they have the same heading (i.e. they are of the same type) and the same body: .

#### Subset

A relation is a subset of another relation if they have the same type (i.e. they share the same heading) and the body of is a subset of the body of : .

### Special Relations

#### Dum

The special relation contains an empty heading and an empty body:

#### Dee

The special relation contains an empty heading and a body containing the empty tuple, which matches the type of the empty heading:

The relation can only have at most the empty tuple as an element.

## Functional Dependency

Given a relation and two sets of attributes
and , the functional dependency
means that in the values of are determined by the values of .
The set of attributes at the left hand side of the arrow () is called the
*determinant*, and the other set of attributes () is called the
*dependent*.

### Trivial Dependencies

A functional dependency is *trivial* if its *dependent* is
a subset of its *determinant*: . For example: .

### Armstrong’s Axioms (Inference Rules)

Also called *inference rules*, are a set of primary rules to infer new
functional dependencies from an existing set of functional dependencies. Given
relation and :

**Reflexivity**: If , then**Augmentation**: If , then**Transitivity**: If and , then

The following additional inference rules are derived from the primary rules:

**Decomposition**: If , then and**Union**: If and , then**Composition**: If and , then**Self-determination**:

#### General Unification Theorem

The theorem states that if and , then .

### Closure

The *closure of functional dependency* of a set of functional dependencies
is denoted , and it corresponds to the union of and the
functional dependencies that are derived from .

### Cover

Given two sets of functional dependencies and for a given relation,
is a *cover* for if .

### Equivalence

Given two sets of functional dependencies and for a given relation,
is *equivalent* to if , which means that is
a cover for and is a cover for .

### Irreducibility

A set of functional dependencies is *irreducible* (also called *minimal*)
if and only if:

- The dependent of every functional dependency in involves only one attribute (has cardinality 1)
- Removing any functional dependency from affects
- All the functional dependencies are
*left irreducible*, which means that removing any attributes from their determinant affects

Every set of functional dependencies has *at least* one equivalent set that is
irreducible. These sets are called *irreducible equivalents*.