UVA DEPARTMENT OF COMPUTER SCIENCECalculus-1Relational CalculusA formal description of the information desired- non-procedural data manipulation languagesTuple calculus{t | P(t)} or {t(A) | P(t)}t: tuple variablet(A): value of t for attribute AP: predicateDomain calculus{x1, ..., xk| P(x1, ..., xk)}xi: domain variables that range over domains of attributesQuery languages- relational algebra-based: SQL- tuple calculus-based: QUEL- domain calculus-based: QBEUVA DEPARTMENT OF COMPUTER SCIENCECalculus-2Tuple CalculusQuantifiers- used for further specifying desired conditions- existential quantifier: t (Q(t))- universal quantifier: t (Q(t))s (s.Name = "Rose")t (t.SSN > 19000)Find all customers having a loan from the Perry branch,and get their names and cities.Borrow (B-name, Loan#, C-name, Amount)Customer (C-name, Street, C-city){t(C-name, C-city)| s (s borrow t[C-name]=s[C-name]s[B-name]="Perry" u (u customeru[C-name]=s[C-name] t[C-city]=u[C-city]))}Algebraic equivalent:C name,C city(B name=Perryborrow customer)UVA DEPARTMENT OF COMPUTER SCIENCECalculus-3Valid Tuple FormulaAtomic formula (atoms)- tuple variable t (t r, where r is a relation)- s[i] u[j]: value comparison- s[i] c: comparison with a literal, where c isa constant in the domain of i th attributeFormulae- every atomic formula is a formula- if P1and P2are formulae, thenP1P2, P1P2, P1, (P1) is also a formula- if P is a formula, then t (P(t)) and t (P(t)) are formulae- there are no more other formulaUVA DEPARTMENT OF COMPUTER SCIENCECalculus-4Equivalence in LogicP1P2( P1P2)P1P2( P1P2)t (P(t)) t ( (P(t))P Q P QUVA DEPARTMENT OF COMPUTER SCIENCECalculus-5Problem of Infinite RelationNot clear what the expression {t | P(t)} really means- a tuple calculus expression may generate an infinite relation- a problem of interpretation: search through all domains?<ex> Consider an expression {t | t borrow}There exist infinitely many tuples that are not in therelation borrow. Do we need to bother?Restricted domain of a tuple calculus formula- a limited interpretation of tuple calculus such thatall domains are essentially finitefor a formula P,dom (P) = set of all values referenced in P= set of all values that either appear as constantsin the expression P or exist in any tuple of therelations referenced in the expression PUVA DEPARTMENT OF COMPUTER SCIENCECalculus-6Restricted Domain{t | t[1] = C r(t)} and let r be a k-ary relationdom(P) = {c}1(r) ...k(r)<ex> r A B---------a1 b1a2 b2dom(r) = {a1, a2, b1, b2}1) r(a1 b1)? True2) r(a2 b2)? False3) r(a2 b1)? True( t (t r t[A]=a2 t[B]=b1))4) r(a1 c1)? Falsenegation by failure: failure to find it means not trueUVA DEPARTMENT OF COMPUTER SCIENCECalculus-7Safe ExpressionAn expression {t | P(t)} is safe if all valuesthat appear in the result are values from dom(P)1) each value that appear in the expression dom(P)2) for each subexpression of the form s(P1(s)),if P1is satisfied by s, then each component of s dom(P1)3) for each subexpression of the form s(P1(s)), P1is trueiff P1(s) is true for all tuples a with values from dom(P1)Purpose of the safety notion- to ensure the finite set (relation):results will include only those values from dom(P)- to ensure computability:subformulae with and can be tested withoutconsidering infinitely many possibilitiesUVA DEPARTMENT OF COMPUTER SCIENCECalculus-8Domain CalculusResults as a set of names of domain values- while tuple calculus returns a set of tuples- domain variables sivs tuple variable sValid formula- atoms: r(s1, ..., sn)siujsiC- formulae: same as tuple calculus formulaeNotion of safe expression is the same as in tuple calculusDomain calculus, restricted to safe expressions, is equivalentin terms of expressive power to the tuple calculus, restrictedto safe expressions.They are also equivalent to that of relational
View Full Document