DOC PREVIEW
UVA CS 662 - Relational Calculus

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UVA CS 662 - Relational Calculus

Download Relational Calculus
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Relational Calculus and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Relational Calculus 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?