1Relational CalculusR&G, Chapter 4∀∃We will occasionally use thisarrow notation unless there is danger of no confusion.Ronald Graham Elements of Ramsey TheoryRelational Calculus•Query has the form: {T | p(T)}–p(T) is a formula containing T•Answer = tuples T for which p(T) = true.Formulae•Atomic formulae:R ∈ RelationR.a op S.bR.a op constant… op is one of• A formula can be:– an atomic formula–––< > = ! " #, , , , ,! ¬p, p"q, p#q,p$q))(( RpR!))(( RpR!Free and Bound Variables• Quantifiers: ∃ and ∀• Use of or binds X.– A variable that is not bound is free.• Recall our definition of a query:– {T | p(T)}! X! X• Important restriction:—T must be the only free variable in p(T).— all other variables must be bound using a quantifier.Simple Queries• Find all sailors with rating above 7• Find names and ages of sailors with rating above 7.– Note: S is a variable of 2 fields (i.e. S is a projection ofSailors){S |S ∈Sailors ∧ S.rating > 7}{S | ∃ S1 ∈ Sailors(S1.rating > 7 ∧ S.sname = S1.sname ∧ S.age = S1.age)} Find sailors rated > 7 who’ve reserved boat#103{ S | S∈Sailors ∧ S.rating > 7 ∧ ∃ R(R∈Reserves ∧ R.sid = S.sid ∧ R.bid = 103) }Joins2Joins (continued)• This may look cumbersome, but it’s not so differentfrom SQL!{ 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 a red boatUniversal QuantificationFind sailors who’ve reserved all boats{ S | S∈Sailors ∧ ∀B∈Boats (∃R∈Reserves (S.sid = R.sid ∧ B.bid = R.bid)) }A trickier example…{ S | S∈Sailors ∧ ∀B ∈ Boats ( B.color = ‘red’ ⇒ ∃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 ⇒ b is the same as ¬a ∨ baTFT FbTT TFA Remark: Unsafe Queries• ∃ syntactically correct calculus queries that havean infinite number of answers! Unsafe queries.– e.g.,– Solution???? Don’t do that!S S Sailors| ¬ !"#$$%&''()*+*,-*.*Expressive Power• Expressive Power (Theorem due to Codd):– Every query that can be expressed in relational algebracan be expressed as a safe query in relational calculus;the converse is also true.•Relational Completeness:Query language (e.g., SQL) can express every query thatis expressible in relational algebra/calculus.(actually, SQL is more powerful, as we will see…)3Summary• Formal query languages — simple and powerful.–Relational algebra is operational• used as internal representation for query evaluationplans.–Relational calculus is “declarative”• query = “what you want”, not “how to compute it”–Same expressive power--> relational completeness.• Several ways of expressing a given query– a query optimizer should choose the most efficient
View Full Document
Unlocking...