Skip to content

Introduction of notation

What is \(R\)?

\(R\) is a relation scheme, i.e., a set of attributes. In simple terms, it is the set of column names in a database table.

Example

\(R = \{A, B, C, D\}\)

What are tuples and relations?

A tuple is an ordered set of values corresponding to the attributes in a relation scheme R. It is an element of a relation (a table with the real data) of scheme R.

Example

Given \(R = \{A, B, C\}\), a relation could be:

A B C
"Mark" 2 3
"Anna" 5 6

Here, \((\text{"Mark"}, 2, 3)\) is a tuple in the relation.

What is \(F\)?

\(F\) is a set of functional dependencies (FDs) on \(R\).

Example

\(F = \{A \to B, B \to C\}\). It means that the value of attribute A uniquely determines the value of attribute B, and the value of attribute B uniquely determines the value of attribute C.

Formally:

\(\large{\forall t_1, t_2 \in r, t_1[A] = t_2[A] \implies t_1[B] = t_2[B]}\)

What are superkeys and keys?

A superkey is a set of attributes that can uniquely identify a tuple in a relation. A key is a minimal superkey, meaning that no proper subset of it is a superkey.

Formally: Given \(K\), a set of attributes of \(R\):

  • Superkey:

    \(K\) is a superkey if \(K^+ = R\), where \(K^+\) is the closure of \(K\) with respect to \(F\). - Key:

    \(K\) is a superkey and \(\nexists K' \subset K\) such that \(K'\) is a superkey.

Example

Given \(R = \{A, B, C\}\) and \(F = \{A \to B, B \to C\}\):

  • Superkeys: \(\{A\}, \{A, B\}, \{A, C\}, \{A, B, C\}\)
  • Keys: \(\{A\}\)

A relation instance \(r\) of scheme \(R\) is legal with respect to a set of functional dependencies \(F\) if it satisfies all the functional dependencies in \(F\).