Safe expressions and domain calculus

Why it exists

The tuple relational calculus (tuple calculus) lets a variable stand for a whole tuple. The domain relational calculus lets a variable stand for a single value of an attribute, so a query lists the values it wants: $\{\langle n \rangle \mid \exists d\; (\text{EMP}(n, d) \wedge \dots)\}$. This is the form used by Query-By-Example. Both calculi share a danger: a formula can describe an answer that is infinite or that changes when the set of possible values changes, for example "all values that are not in $R$". Only safe expressions are real queries. GATE asks: which of these calculus expressions is safe, which languages have the same expressive power, write or translate a calculus query.

Prerequisites

You need the tuple relational calculus (tuple calculus) and relational algebra (relational algebra), including division.

Precise definitions

Domain calculus query. A query has the form

where $x_1, \dots, x_n$ are domain variables and $P$ is a formula with exactly these free variables. The atoms of a formula are

• $R(t_1, \dots, t_k)$, written $\langle t_1, \dots, t_k \rangle \in R$ in some books: the values $t_1, \dots, t_k$ (variables or constants), taken in the order of the attributes of $R$, form a tuple of $R$;
• $x \; \theta \; y$ or $x \; \theta \; c$ with $\theta \in \{=, \neq, <, \le, >, \ge\}$.

Formulas are built with $\neg$, $\wedge$, $\vee$, $\Rightarrow$ and the quantifiers $\exists x$, $\forall x$. The answer is the set of all value tuples that make $P$ true.

Active domain. The set of all values that occur in some tuple of the database or as a constant of the query.

Safe (domain independent) expression. An expression is safe if its answer is finite for every database and depends only on the database and the constants of the query, not on which other values the attribute domains contain. Equivalent test: the answer is the same when the variables range over the active domain and when they range over a larger domain. The textbook (Silberschatz et al.) states it as: every value in the answer comes from $\text{dom}(P)$ (the values in $P$ and in the relations mentioned in $P$), and every existential and universal subformula is decided by values of $\text{dom}(P)$ alone (quoted).

Codd's theorem (quoted). Relational algebra, the safe tuple relational calculus and the safe domain relational calculus have the same expressive power.

How it works

The same query in the three languages

The database: $\text{EMP}(\text{ename}, \text{did})$ with five employees and $\text{DEPT}(\text{did}, \text{dname}, \text{floor})$ with four departments. In the formulas the letters $n, d, m, f$ stand for the ename, did, dname and floor.

For the first query, the SQL used in the check is

SELECT DISTINCT ename
FROM EMP e JOIN DEPT d ON e.did = d.did
WHERE d.floor = 2

(it was run in SQLite and the answer compared with the formula, the algebra expression and the tuple calculus query by the generator that built the table). Notice the shape of each calculus formula: a positive atom introduces every variable ($\text{EMP}(n, d)$ binds $n$ and $d$; $\text{DEPT}(d, m, 2)$ binds $m$), and negation and the universal quantifier only filter.

Algebra written as safe formulas

Every operator of relational algebra is a safe formula; the table checks six of them on a small database:

Selection and projection are an atom with a condition and an $\exists$; the join is $\exists y\,(R(x, y) \wedge S(y, z))$; union is $\vee$ of two atoms with the same variables; difference is an atom and the negation of another atom over the same variables; division is the universal quantifier in the form "for all $z$: if $z$ is in $T$ then $R(x, z)$", with the premise restricting $z$.

Unsafe expressions and the test

The first column is a syntactic test that I use on this site (it is a standard idea, called range restriction, but the exact rules are mine): every free variable of the answer, and every variable under a quantifier, must be bound by a positive relation atom in the same conjunction (equalities with constants or with a bound variable also bind), a disjunction binds only the variables bound in both branches, and a universal quantifier must have the form "for all $v$ (an atom that restricts $v$ implies a condition)". A formula that passes is safe. The test is sufficient but not necessary: $\neg\neg R(x, x)$ is safe (it means $R(x, x)$) but fails the test. In general, deciding whether a calculus expression is domain independent is undecidable (quoted).

Causes of unsafety seen in the table:

• Negation without a positive atom ($Q3$: $\neg R(x, x)$): every value not related by $R$ is an answer; the answer grows with the domain.
• A comparison alone ($Q4$: $x < y$, $Q11$: $\exists y\,(x \ne y)$): infinitely many pairs, or a value $x$ is accepted only if the domain happens to have another value.
• A disjunction whose branches bind different variables ($Q5$, $Q10$): in one branch $x$ is unrestricted.
• A universal quantifier without a restricting premise ($Q6$: $\forall y\, R(x, y)$): its truth depends on every value of the domain. On the database of the table both answers happen to be empty, but on a database such as $R = \{(1, 1)\}$ the answer over the active domain $\{1\}$ is $\{1\}$ and the answer over a larger domain is empty. Safety is a property of the formula for all databases, not of one.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The domain calculus is the value-based twin of the tuple calculus and has the same relation to relational algebra (Codd's theorem). The division formula connects to the division operator and the "for all" queries of advanced algebra; in SQL, universal quantification is written with a double NOT EXISTS (nested queries).

PYQs

Consider a database that has the relation schemas
EMP(Empld,
EmpName,
Deptld)
and
DEPT(DeptName, Deptld). Note that the Deptldcan  be
permitted to a NULL in the relation EMP. Consider the
following queries on the database expressed in tuple
relational calculus.

(I) {t|∃u ε EMP(t[EmpName) = u[EmpName] Λ ∀

         ∨ε DEPT(t[Deptld] ≠ V[Deptld]))}

(II) {t|∃u ε EMP(t[EmpName) = u[EmpName] Λ ∃∨ ε
DEPT(t[Deptld] ≠V[Deptld]))}

(III) {t|∃u ε EMP(t[EmpNmae) = u[EmpName] Λ ∃∨ ε
DEPT(t[Deptld] =V[Deptld]))}

Which of the above queries are safe?

Consider the following relation schema

Students(rollno:integer, sname: string)

Courses(courseno:integer,cname: string)

Registration (rollno: integer, courseno: integer, percent:
real)

Which of the following queries are equivalent to this query
in English?

"Find the distinct names of all students who score more
than 90% in the course numbered 107".

(I)  SELECT DISTINCT S.sname

FROM Students as S, Registration as R

WHERE R.rollno = S. rollno AND R.courseno = 107 AND
R.percent> 90

(II) πsname(σcourseno= 107 Λ percent> 90 (Registration ⋈Students))

(III) {T|∃S ε Students, ∃R ε Registration (S.rollno =
R.rollno Λ R.courseno = 107 Λ R.percent> 90 Λ T.sname
= S.sname)}

(IV) {<SN>|∃SR∃RP(<SR,SN>∈Students∧<SR,107,RP>∈
Registration∧ RP>90)}

Which of the following relational query languages have
the same expressive power?
1. Relational algebra
2. Tuple relational calculus restricted to safe
Expressions
3. Domain relational calculus restricted to safe
expressions

Self-check

Revision card

References