Database 1
Data Manipulation

Prof. dr. Paul M.E. De Bra

Dept. of Computer Science

Eindhoven Univ. of Technology

Equivalence of calculus and algebra

For every relational algebra query there is an equivalent tupel calculus query.

For every tupel calculus query there is an equivalent relational algebra query.

Translation algebra  calculus is fairly straightforward and can be used to obtain tc queries from ra queries.

Translation calculus  algebra is very artificial and does not result in readable ra queries.

We will show (and do exercises) on algebra to calculus translation.

Translating algebra to tupel calculus

Step 1: reduce the algebra expression to the basic operators

Step 2: if E is a single relation r then E translates to { t | tr } or if r has attributes B1, ...,Bn then it can also be written as {t | sr ( t[B1]=s[B1] ... t[Bn]=s[Bn] ) }

Step 3, apply the following substeps recursively (if the algebra expressions are base relations an  may need to be added):

Renaming: let { t | f(t) } be a tc expression equivalent to an ra expression E that uses attributes B1, ...,Bn; let E1 = x(A1,...,An)(E) then the translation to tc is { s | tr (f(t)  s[A1]=t[B1] ... s[An]=t[Bn]) }

Translating algebra to tupel calculus

Selection: let { t | f(t) } be a tc expression equivalent to E then E1= AB(E) or E1= Ac(E) (where  is , , ,...) is translated to { t | f(t)  t[A]t[B] } resp. { t | f(t)  t[A]c }

Projection: if E translates to { t | f(t) } then B1, ...,Bp (E) translates to { t | f'(t) } where f' is f with references to t[B1] ... t[Bp] only (no other attributes of t used in f).

Cartesian Product: if E1 (over A1, ...,An) translates to { t | f(t) } and E2 over B1, ...,Bm translates to { s | g(s) } then E1  E2 translates to { r | f(t)  g(s)  t[A1]=r[A1] ... t[An]=r[An]  s[B1]=r[B1] ... s[Bm]=r[Bm] }

Translating algebra to tupel calculus

Union: let { t | f(t) } be a tc expression equivalent to E1 and { t | g(t) } be a tc expression equivalent to E2 then E1  E1 is translated to { t | f(t)  g(t) }

Difference: let { t | f(t) } be a tc expression equivalent to E1 and { t | g(t) } be a tc expression equivalent to E2 then E1 - E1 is translated to { t | f(t)  g(t) }

Example

List all drinkers who visit a bar that serves a beer they like.

RA: V.d(V  S  L)

Step 1: V.d( V.k=S.kS.b=L.bV.d=L.d(V  S  L))

Step 2: The relations are translated to

{ v | vV } { s | sS } { l | lL }

Step 3: We first translate the product, then the selection and then the projection.

Example (cont.)

Cartesian product: { t | vV ( sS ( lL ( t[vd]=v[d]  t[vk]=v[k]  t[sk]=s[k]  t[sb]=s[b]  t[ld]=l[d]  t[lb]=l[b] ) ) } (attribute names must be unique)

Selection: { t | vV ( sS ( lL ( t[vd]=v[d]  t[vk]= v[k]  t[sk]=s[k]  t[sb]=s[b]  t[ld]=l[d]  t[lb]=l[b]  v[k]=s[k]  s[b]=l[b]  v[d]=l[d] ) ) ) }

Projection: { t | vV ( sS ( lL ( t[vd]=v[d]  v[k]=s[k]  s[b]=l[b]  v[d]=l[d] ) ) ) }

Translation exercises

Do the translations of exercise 3.13 and 3.14 according to the method described above.

Preparation for labsession 4

You should study part of SQL (chapter 4 up to and including section 4.3) by April 28.

We first answer the bank queries in SQL and then the Beer queries.

In this colstruction we are going to try to understand to recognize different types of queries by looking at the question formulated in natural language. We then translate to tupel calculus. If you find it hard to translate from natural language to tupel calculus you can of course try to translate the relational algebra solutions to tupel calculus.

Databases 1, Colstructie 8

Translation between algebra and calculus

Paul De Bra

2003-04-01T22:52:54

Paul De Bra