DOC PREVIEW
Berkeley COMPSCI 186 - Relational Calculus

This preview shows page 1-2-3-21-22-23-42-43-44 out of 44 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 44 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 44 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 44 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 44 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 44 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 44 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 44 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 44 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 44 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 44 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Relational CalculusSlide 2Tuple Relational CalculusTRC FormulasFree and Bound VariablesSelection and ProjectionJoinsJoins (continued)Division (makes more sense here???)Division – a trickier example…a  b is the same as a  bUnsafe Queries, Expressive PowerSummarySQL: The Query Language Part 1Relational Query LanguagesThe SQL Query LanguageDDL – Create TableCreate Table (w/column constraints)Create Table (w/table constraints)Create Table (Examples)The SQL DMLQuerying Multiple RelationsBasic SQL QueryQuery SemanticsStep 1 – Cross ProductStep 2) Discard tuples that fail predicateStep 3) Discard Unwanted ColumnsNow the DetailsExample SchemasAnother Join QuerySome Notes on Range VariablesMore NotesFind sailors who’ve reserved at least one boatExpressionsString operationsFind sid’s of sailors who’ve reserved a red or a green boatFind sid’s of sailors who’ve reserved a red and a green boatAND Continued…Nested QueriesNested Queries with CorrelationMore on Set-Comparison OperatorsRewriting INTERSECT Queries Using INDivision in SQLBasic SQL Queries - SummaryRelational CalculusCS 186, Fall 2005R&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 Domain relational calculus (DRC).•Calculus has variables, constants, comparison ops, logical connectives 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 that make the formula evaluate to true.Tuple Relational Calculus•Query has the form: {T | p(T)}–p(T) denotes a formula in which tuple variable T appears. •Answer is the set of all tuples T for which the formula p(T) evaluates to true.•Formula is recursively defined:start with simple atomic formulas (get tuples from relations or make comparisons of values)build bigger and better formulas using the logical connectives.TRC Formulas•An Atomic formula is one of the following:R  Rel R.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 is said 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 be the only free variable in the formula p(T).—in other words, all other tuple variables must be bound using a quantifier.Selection and Projection•Find all sailors with rating above 7–Modify this query to answer: Find sailors who are older than 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 a projection of Sailors) •only 2 fields are ever mentioned and S is never used to range over 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)}Find sailors rated > 7 who’ve reserved boat #103 Note the use of  to find a tuple in Reserves that `joins with’ the Sailors tuple under consideration. {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 of each quantifier’s binding.•This may look cumbersome, but it’s not so different from 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 Boats there is a tuple in Reserves showing that sailor S has reserved 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’  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  b•If a is true, b must be true! –If a is true and b is false, the implication evaluates to false.•If a is not true, we don’t care about b–The expression is always true.aTFT FbTT TFUnsafe Queries, Expressive Power•  syntactically correct calculus queries that have an 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 algebra can be expressed as a safe query in DRC / TRC; the converse is also true. •Relational Completeness: Query language (e.g., SQL) can express every query that is expressible in relational algebra/calculus. (actually, SQL is more powerful, as we will see…)S| S  SailorsSummary•The relational model has rigorously defined query languages — 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 in terms 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.SQL: The Query Language Part 1CS186, Fall 2005


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?