Two types:
- Tuple Relational Calculus
- Domain Relational Calculus
We will only cover basics of Tuple Relational Calculus
A tuple is a set of attributes and pairs of domain:value (a table row)
Atoms
In TRC we are going to construct formulae that declare the existence of some tuples. Formulas are defined within a database as a set of atomic formulas.
Examples
- ($t$.cust_id=$s$.cust_id) – means tuple $t$ has a cust_id attribute and tuple $s$ has a cust_id attribute with the same value.
- ($t$.cust_name=’Maltzl’) – tuple $t$ has a name attribute and its value is ‘Maltzl’
- Customer($t$) – tuple $t$ is present in the Customer relation.
Formulae
Atoms can be combined into formulas, as in first order logic, with logical operators $\wedge$, $\vee$ $\lnot$. We can also use $\exists$ and $\forall$ qualifiers.
- $t$.cust_name=’Maltzl’ $\vee$ $t$.custname=’Gomez’
- $t\in$Customer $\vee$ $t\in$Salesperson
- $\forall t$ ($t\in$Customer $\wedge$ $t$.city=’Tokyo’ $\wedge\lnot$($t$.county=’USA’))
We use the typical first order logic here:
- $f_1\wedge f_2$ is true if and only if $f_1$ is true and $f_2$ is true,
- $f_1\vee f_2$ is true if and only if $f_1$ is true or $f_2$ is true or both are true,
- $\lnot f$ is true if and only if $f$ is not true,
- $\exists v H(f)$ is true if and only if there is a tuple $t$ such that the formula $f$ is true for val$_{([v\rightarrow t])}$
- $\forall v H(f)$ is true if and only if for all tuples $t$ the formula $f$ is true for val$_{([v\rightarrow t])}$
Queries
Now, with Atoms and Formulae we can put together Queries to make declarative statements about the information we want.
$\{t | H(t)\}$
Selection
For example, to find the Salespersons who make more than a commission of 11:
$\{t | t\in \textrm{Salesperson}\wedge t.\textrm{comm}>11\}$
Modify this query to answer: Find Salespersons who have a commission less than or equal to 11 and are managed by manager with id of 44.
$\{t | t\in \textrm{Salesperson}\wedge t.\textrm{comm}\le 11\wedge t.\textrm{manager}=44\}$
Safe Queries
Because of how qualifiers can work we want to limit query expressions to be domain-independent. We call these safe queries. To determine whether a query is safe we have two rules. The first rule is to determine the boundedness, the second rule determines equatedness.
$\{t |\lnot (t\in\textrm{Customer})\}$ is unsafe because it asks for all of the possible tuples outside of Customer without binding $t$.
Bounded queries:
- $\lnot f$ doesn’t do any binding — IMPORTANT
- In $∃ v H(f)$ a value $w$.a is bound if it is bound in $f$ and $w\ne v$
- In $\forall v H(f)$ a value $w$.a is bound if it is bound in $f$ and $w\ne v$
What this means: a bound variable is one that comes from some known relation with some known type schema or is somehow equated to a variable from a relation.
The use of quantifiers $\exists$ and $\forall$ in a formula is was binds x in the formula.
If we revisit the definition of a query $\{t | H(t)\}$ the variable $t$ that appears to the left of | must be the only free variable in the formula $H(t)$. All other variables must be bound using a qualifier.
Projection
Suppose we only want the Salesperson names. (We would use project in the algebra.)
$\{t | \exists s (s\in\textrm{Salesperson}\wedge s.\textrm{comm}\le 11 \wedge s.\textrm{manager}=44\wedge s.\textrm{salpername}=t.\textrm{salpername})\}$
Note that $t$ is a tuple variable in 2 fields, i.e., $t$ is a projection of Salesperson.
In English, we may read this equation as “the set of all tuples such that there exists a tuple in the relation Salesperson for which the values of the salpername attribute are equal, and the value of comm is less than or equal to 11 and the value of managerid is 44”
Join
Find Salespersons with commission less than 10 who have a sale of more than 200 items.
$\{t|\exists u\in \textrm{Salesperson}\wedge t.\textrm{salesperson}=u.\textrm{salpers_name} \wedge u.\textrm{comm}<10\wedge \exists s(s\in \textrm{Sale}\wedge s.\textrm{salperid}=u.\textrm{salperid}\wedge s.\textrm{qty}>200)\}$
The use of $\exists$ joins the Salesperson tuples. This does not do projection here because $t$ is defined to range over all the Salesperson-attributes.
Find a Customer who bought an item on Feb 12th
$\{t|\exists s,u(s\in\textrm{Customer}\wedge u\in\textrm{Sale}\wedge u.\textrm{custid}=s.\textrm{custid}\wedge u.\textrm{date}=\textrm{’02/12′}\wedge t.\textrm{name}=s.\textrm{custname})\}$
Another join
Find Salespersons who have sold a Sweater
$\{t|t\in\textrm{Salesperson}\wedge \exists s(s\in\textrm{Sale}\wedge s.\textrm{salperid}=t. \textrm{ salperid}\wedge \exists u(u\in \textrm{Product}\wedge u.\textrm{proddesc}=\textrm{‘Sweater’}\wedge u. \textrm{prodid}=s.\textrm{prodid}))\}$
Notice how the parenthesis control the scope of each qualifier’s binding. This may look cumbersome, but this is how SQL works.
In this case it works just as well to say
$\{t|t\in\textrm{Salesperson}\wedge\exists s,u(s\in\textrm{Sale}\wedge u\in\textrm{Product}\wedge s.\textrm{salperid}=t.\textrm{salperid}\wedge u.\textrm{proddesc}=\textrm{‘Sweater’}\wedge u.\textrm{prodid}=s.\textrm{prodid})\}$
And if we want to do projection on the name:
$\{t|\exists s,u,v(s\in\textrm{Sale}\wedge u\in\textrm{Product}\wedge v\in\textrm{Salesperson}\wedge s.\textrm{salperid}=v.\textrm{salperid}\wedge u.\textrm{proddesc}=\textrm{‘Sweater’}\wedge u.\textrm{prodid}=s.\textrm{prodid}\wedge t.\textrm{result} = v.\textrm{salpersname})\}$
(Having the $t\in\textrm{Salesperson}$ outside of the $\exists$ qualifier does not do implicit projection.)
Examples:
Find Products made in Peru
$\{t|\exists a,b(a\in\textrm{Product}\wedge b\in\textrm{Manufacturer}\wedge a.\textrm{proddesc}=t.\textrm{prod}\wedge a.\textrm{manfid}=b.\textrm{manfid}\wedge b.\textrm{country=’Peru’})\}$
Find Customers or Salespersons who live in Tokyo.
$\{t|\exists s(s\in\textrm{Customer}\wedge t.\textrm{name}=s.\textrm{custname}\wedge s.\textrm{city=’Tokyo’})\vee \exists u(u\in\textrm{Salesperson}\wedge t.\textrm{name}=u.\textrm{salpername}\wedge u.\textrm{office=’Tokyo’})\}$