When should you use the existential and universal quantifiers for Relational Calculus?

Question

Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus?

Given this schema:

Hotel(hotelNo, hotelName, city)

The expression below gets all hotel names based in London (expressed in Domain Relational Calculus)

$$\mathrm{HotelName|(\exists hNo,cty)(Hotel(hNo,hotelName,cty)\wedge cty=\,\,"\!\!London\!")}$$

Why does the existential quantifier required for this example? Wouldn't this be the equivalent {hotelName | (Hotel(hNo, hotelName, cty) AND cty='London')}

And why is only hNoand cty selected for the existential quantifier? What about the hotelName?

Source: Herts University - Advanced Database Course

Answer 1

This question is related to the very basics of database theory, finite model theory and logics. I would strongly suggest Abiteboul's book on Foundations of Databases, or Libkin's book on Finite Model Theory.

Very roughly stated, a database is a collection of facts, and a query is a logical formula, which is used to specify certain patterns to be matched against the database. The most common database query language is unions of conjunctive queries, which is simply a disjunction of conjunctive queries. These are existentially quantified queries and there is NO universal quantification at all. The query in the question is indeed the simple conjunctive query

$\exists \ x \ {Hotel(x, y, london)} $

where $x$ and $y$ are logical variables and $london$ is a constant. Intuitively, the $x$ variables are to be matched to hotel numbers, and $y$ variables to hotel names. Now, in this formula, $y$ is a free variable, i.e. it is not bound to any quantifier. It is wrong to assume that it is bound to a universal quantifier. Such variables are also called the answer variables as these are the variables for which you want to retrieve answers. Note that $x$ is not an answer variable; so, you are not interested in the hotel numbers. All you want to say with this query is: Give me all the names of the hotels in London! Differently, consider this query

${Hotel(x, y, london)} $

where $x$ is also a free variable. It asks for all names + numbers of the hotels in London. A Boolean query is a special case of a conjunctive query that does not contain any free variables. For instance, the query

$\exists \ x,y \ {Hotel(x, y, london)} $

has no free variables and asks a yes/no question: Is there a hotel in London (with some hotel number and name)? Overall, please have a look at the reference books, and simply learn the query semantics.

Answer 2

You cannot have free variables in your expression, i.e. all variables must either be quantified, or appear in the return tuple. So the answer is - always, unless the variable appears in the output tuple

Answer 3

A query in relational calculus is basically a set constructor. What appears on the right side of the "|" ("such that") symbol is a first-order predicate logic sentence, on which all variables should be quantified (otherwise the sentence is meaningless), with the exception of the ones that appear before the "|" symbol. They become the ones that function as arguments for the set constructor.

Could the language use some form of inference or implicit quantification? In principle, yes, but in practice this would create more confusion. When writing any kind of code, we should always err on the side of precision and rigour. Language implementation should not protect us from the burden of clarity.

Answer 4

I was wondering much the same. After acquiring the Ramakrishnan text (2nd edition) I found the answer on page 109:

Let each free variable in a formula $F$ be bound to a tuple value. For the given assignment of tuples to variables, with respect to the given database instance, $F$ evaluates to (or simply 'is') $\text{true}$ if one of the following holds:

• ...

• $F$ is of the form $\exists R(p(R))$, and there is some assignment of tuples to the free variables in $p(R)$, including the variable $R$, that makes the formula $p(R)$ true.

• $F$ is of the form $\forall R(p(R))$, and there is some assignment of tuples to the free variables in $p(R)$ that makes the formula $p(R)$ true no matter what tuple is assigned to $R$.

It appears that what we are essentially doing in the form $\{ T | p(T) \}$ is finding the truth set of the expression $p(T)$ where $T$ ranges over all tuples in the relation under the expression.

Given a relation instance $R$ and some arbitrary expression $p(R)$ we can return the entire tuple $\{ r | r \in R \land p(r) \}$. Alternately we can project and return only those fields we need, by introducing a new tuple variable e.g. $s$. Doing this requires that we have a means to specify the field names to be extracted:

$$\{ s | r \in R \land p(r) \land s.attr1 = r.attr1 \land ... \land s.attr\text{n} = r.attr\text{n} \}$$

Ramakrishnan describes this exactly. Given the query:

$$\{ P | ∃S ∈ Sailors ( S.rating = 7 ∧ P.name = S.name ∧ P.age = S.age ) \}$$

the following is written:

This query illustrates a useful convention: $P$ is considered to be a tuple variable with exactly two fields, which are called name and age, because these are the only fields of $P$ that are mentioned and $P$ does not range over any of the relations in the query; that is, there is no subformula of the form $P \in Relname$.

At the end of the section on TRC the point is made that we can choose to return an entire tuple containing all the fields, or a tuple containing only a subset of the fields. If we want the subset (the projection) we have to introduce the new variable.

In this case the equality comparisons are the notation used to specify the fields that will be in $P$.

Hope that helps.