Unformatted text preview:

1Relational CalculusCS 186, Fall 2002, Lecture 8R&G, Chapter 4"$We will occasionally use thisarrow notation unless there is danger of no confusion.Ronald Graham Elements of Ramsey TheoryRelational Calculus• Comes in two flavors: Tuple relational calculus (TRC) and Domainrelational calculus (DRC).• Calculus has variables, constants, comparison ops, logicalconnectives and quantifiers.–TRC: Variables range over (i.e., get bound to) tuples.• Like SQL.–DRC: Variables range over domain elements (= field values).• Like Query-By-Example (QBE)– Both TRC and DRC are simple subsets of first-order logic.• We’ll focus on TRC here• Expressions in the calculus are called formulas.• Answer tuple is an assignment of constants to variables thatmake the formula evaluate to true.Tuple Relational Calculus•Query has the form: {T | p(T)}–p(T) denotes a formula in which tuplevariable T appears.•Answer is the set of all tuples T forwhich the formula p(T) evaluates to true.•Formula is recursively defined:vstart with simple atomic formulas (get tuplesfrom relations or make comparisons ofvalues)vbuild bigger and better formulas using thelogical connectives.TRC Formulas•An Atomic formula is one of the following:R Œ RelR.a op S.bR.a op constantop is one of• A formula can be:– an atomic formula– where p and q are formulas– where variable R is a tuple variable– where variable R is a tuple variable< > = £ ≥ ≠, , , , ,ÿ Ÿ ⁄p p q p q, ,))(( RpR$))(( RpR"Free and Bound Variables• The use of quantifiers and in a formula issaid to bind X in the formula.– A variable that is not bound is free.• Let us revisit the definition of a query:– {T | p(T)}$ X" X• There is an important restriction— the variable T that appears to the left of `|’ must bethe only free variable in the formula p(T).— in other words, all other tuple variables must bebound using a quantifier.Selection and Projection• Find all sailors with rating above 7– Modify this query to answer: Find sailors who are olderthan 18 or have a rating under 9, and are called ‘Bob’.• Find names and ages of sailors with rating above 7.– Note: S is a tuple variable of 2 fields (i.e. {S} is aprojection of Sailors)• only 2 fields are ever mentioned and S is never used to rangeover any relations in the query.{S |S ŒSailors Ÿ S.rating > 7}{S | $S1 ŒSailors(S1.rating > 7 Ÿ S.sname = S1.sname Ÿ S.age = S1.age)}2 Find sailors rated > 7 who’ve reserved boat#103Note the use of $ to find a tuple in Reservesthat `joins with’ the Sailors tuple underconsideration.{S | SŒSailors Ÿ S.rating > 7 Ÿ $R(RŒReserves Ÿ R.sid = S.sid Ÿ R.bid = 103)}JoinsJoins (continued)• Observe how the parentheses control the scope ofeach quantifier’s binding.• This may look cumbersome, but it’s not so differentfrom SQL!{S | SŒSailors Ÿ S.rating > 7 Ÿ $R(RŒReserves Ÿ R.sid = S.sid Ÿ R.bid = 103)}{S | SŒSailors Ÿ S.rating > 7 Ÿ $R(RŒReserves Ÿ R.sid = S.sid Ÿ $B(BŒBoats Ÿ B.bid = R.bid Ÿ B.color = ‘red’))}Find sailors rated > 7 who’ve reserved boat #103Find sailors rated > 7 who’ve reserved a red boatDivision (makes more sense here???)• Find all sailors S such that for all tuples B in Boatsthere is a tuple in Reserves showing that sailor S hasreserved B.Find sailors who’ve reserved all boats (hint, use "){S | SŒSailors Ÿ "BŒBoats ($RŒReserves (S.sid = R.sid Ÿ B.bid = R.bid))}Division – a trickier example…{S | SŒSailors Ÿ "B Œ Boats ( B.color = ‘red’ fi $R(RŒReserves Ÿ S.sid = R.sid Ÿ B.bid = R.bid))}Find sailors who’ve reserved all Red boats{S | SŒSailors Ÿ "B Œ Boats ( B.color ≠ ‘red’ ⁄ $R(RŒReserves Ÿ S.sid = R.sid Ÿ B.bid = R.bid))}Alternatively…a fi b is the same as ÿa ⁄ b• If a is true, b mustbe true!– If a is true and b isfalse, the implicationevaluates to false.• If a is not true, wedon’t care about b– The expression isalways true.aTFT FbTT TFUnsafe Queries, Expressive Power• $ syntactically correct calculus queries that havean infinite number of answers! Unsafe queries.– e.g.,– Solution???? Don’t do that!• Expressive Power (Theorem due to Codd):– every query that can be expressed in relational algebracan be expressed as a safe query in DRC / TRC; theconverse is also true.•Relational Completeness: Query language (e.g.,SQL) can express every query that is expressible inrelational algebra/calculus. (actually, SQL is morepowerful, as we will see…)† S|ÿS Œ SailorsÊ Ë Á Á ˆ ¯ ˜ ˜ Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ Ô3Summary• The relational model has rigorously defined querylanguages — simple and powerful.• Relational algebra is more operational– useful as internal representation for query evaluation plans.• Relational calculus is non-operational– users define queries in terms of what they want, not interms of how to compute it. (Declarative)• Several ways of expressing a given query– a query optimizer should choose the most efficient version.• Algebra and safe calculus have same expressive power– leads to the notion of relational completeness.Addendum: Use of "• "x (P(x)) - is only true if P(x) is true forevery x in the universe• Usually: "x ((x Œ Boats) fi (x.color = “Red”)• fi logical implication,a fi b means that if a is true, b must betruea fi b is the same as ÿa ⁄ bFind sailors who’ve reserved all boats• Find all sailors S such that for each tuple Beither it is not a tuple in Boats or there is a tuple inReserves showing that sailor S has reserved it.{S | SŒSailors Ÿ "B( (BŒBoats) fi $R(RŒReserves Ÿ S.sid = R.sid Ÿ B.bid = R.bid))}{S | SŒSailors Ÿ "B(ÿ(BŒBoats) ⁄ $R(RŒReserves Ÿ S.sid = R.sid Ÿ B.bid = R.bid))}... reserved all red boats• Find all sailors S such that for each tuple Beither it is not a tuple in Boats or there is a tuple inReserves showing that sailor S has reserved it.{S | SŒSailors Ÿ "B( (BŒBoats Ÿ B.color = “red”) fi $R(RŒReserves Ÿ S.sid = R.sid Ÿ B.bid = R.bid))}{S | SŒSailors Ÿ "B(ÿ(BŒBoats) ⁄ (B.color ≠ “red”) ⁄ $R(RŒReserves Ÿ S.sid = R.sid Ÿ B.bid =


View Full Document

Berkeley COMPSCI 186 - Relational Calculus

Documents in this Course
Load more
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?