Relational Database

Relational Calculus (RC)

Below are mainly confusing because of notation. In practice, just look at the examples, and it will be a lot clearer. However, it’s still good to know theory, see Theory vs. Practice.

Query Conditions

The idea of query conditions is to use variables and valuations to generalize conditions.

• For example: AUTHOR(x, y) will be true of any valuation $\{x\mapsto v_1,y\mapsto v_2,...\}$ exactly when the 2-tuple of values $(v_1,v_2)$ occurs in AUTHOR.

Valuation \theta

A valuation is a function $\theta$ that maps variable names to values in the universe: $\theta :\{x_1,x_2,...\}\to \text{D}$ To denote a modification to $\theta$ in which variable $x$ is instead mapped to value $v$, one writes: $\theta [x\mapsto v]$

These allow more complex conditions to be built from simpler conditions with logical connectives ($\wedge ,\vee ,\neg$) and quantifiers ($\exists ,\forall$).

Queries

Relational Calculus (RC) Query

A query in the relational calculus is a set comprehension of the form $\{(x_1,...,x_k)\mid \phi \},$ where $\{x_1,...,x_k\}=Fv(\phi )$ (are the free variables of $\phi$). Also:

• a conjunctive query is where $\phi$ is a conjunctive formula, and
• a positive query is where $\phi$ is a positive formula.

Query Answers

The answers to a query $\{(x_1,...,x_k)\mid \phi \}$ over $DB$ is the relation $\{(\theta (x_1),...,\theta (x_k))\mid DB,\theta \models \phi \}$

In other words, answers to queries are valuations applied to tuples of variables that make the formula true with respect to a database.

Some basic examples

Safety

Integrity Constraints aren’t enough for a RDBMS. We also need to have following properties:

• The extension of any relation in a signature should be finite
• Queries should be safe: their answers should be finite when database instances are finite

Look at the following queries, which would have infinite answers:

Domain Independence

An RC query $\{(x_1,...,x_k)\mid \phi \}$ is domain independent when, for any pair of instances $D{B}_1=(D_1,\approx ,R_1,...,R_k)$ and $D{B}_2=(D_2,\approx ,R_1,...,R_k)$ and any $\theta ,D{B}_1,\theta \models \phi$ if and only if $D{B}_2,\theta \models \phi$

Theorem

Let $(R_1,...,R_k)$ be the signature of a relational database. Answers to domain independent queries contain only values that occur in the extension Ri of any relation $R_i$.

safety ⇔ domain independence and finite database instances

Range-Restricted RC