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 | tr } or if r has attributes B1, ...,Bn then it can also be written as {t | sr ( 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 | tr (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= AB(E) or E1= Ac(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.kS.b=L.bV.d=L.d(V S L))
- Step 2: The relations are translated to
- { v | vV } { s | sS } { l | lL }
- Step 3: We first translate the product, then the selection and then the projection.
Example (cont.)
- Cartesian product: { t | vV ( sS ( lL ( 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 | vV ( sS ( lL ( 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 | vV ( sS ( lL ( 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.