Duke CPS 116 - Relational Model & Algebra

Unformatted text preview:

1Relational Model & AlgebraCPS 116Introduction to Database Systems2Announcements (Thurs. Aug. 30) Check out what some former 116er (Anthony Bishopric and Tomas Barreto) have been up to: http://www.shoeboxed.com/ Homework #1 will be assigned next Thursday Office hours: see also course Web page Jun: Tuesday before/after class; Thursday before class Yi: Wednesday and Friday afternoons 12:30pm-2:00pm Note on lecture notes The “complete” version will be posted after lecture3Relational data model A database is a collection of relations (or tables) Each relation has a list of attributes (or columns) Each attribute has a domain (or type) Set-valued attributes not allowed Each relation contains a set of tuples (or rows) Each tuple has a value for each attribute of the relation Duplicate tuples are not allowed• Two tuples are identical if they agree on all attributes)Simplicity is a virtue!24ExampleStudent CourseSID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3CID titleCPS116 Intro. to Database SystemsCPS130 Analysis of AlgorithmsCPS114 Computer Networks……EnrollOrdering of rows doesn’t matter(even though the output isalways in some order)…… ……SID CID142 CPS116142 CPS114123 CPS116857 CPS116857 CPS130456 CPS114……5Schema versus instance Schema (metadata) Specification of how data is to be structured logically Defined at set-up Rarely changes Instance Content Changes rapidly, but always conforms to the schema) Compare to type and objects of type in a programming language6Example Schema Student (SID integer, name string, age integer, GPA float) Course (CID string, title string) Enroll (SID integer, CID integer)IInstance { h142, Bart, 10, 2.3i, h123, Milhouse, 10, 3.1i, ...} { hCPS116, Intro. to Database Systemsi, ...} { h142, CPS116i, h142, CPS114i, ...}37Relational algebraRelOpRelOpA language for querying relational databases based on operators: Core set of operators: Selection, projection, cross product, union, difference, and renaming Additional, derived operators: Join, natural join, intersection, etc. Compose operators to make complex queriesRelOp8Selection Input: a table R Notation: σpR p is called a selection condition/predicate Purpose: filter rows according to some criteriapg Output: same columns as R, but only rows of R that satisfy p9Selection example Students with GPA higher than 3.0σGPA > 3.0StudentSID name age GPA142 Bart 10 2.3SID name age GPAσGPA > 3.0123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3…… ……123 Milhouse 10 3.1857 Lisa 8 4.3…… ……410More on selection Selection predicate in general can include any column of R, constants, comparisons (=, ·, etc.), and Boolean connectives (∧: and, ∨: or, and ¬: not) Example: straight A students under 18 or over 21σGPA ≥ 4.0 ∧ (age < 18 ∨ age > 21)Student But you must be able to evaluate the predicate over a single row of the input table Example: student with the highest GPAσGPA ≥ all GPA in Student tableStudent11Projection Input: a table R Notation: πLR L is a list of columns in R Purpose: select columns to outputpp Output: same rows, but only the columns in L12Projection example ID’s and names of all studentsπSID, nameStudentSID name age GPA142 Bart 10 2.3SID name142 BartπSID, name123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3…… ……123 Milhouse857 Lisa456 Ralph……513More on projection Duplicate output rows are removed (by definition) Example: student agesπageStudentSID name age GPA ageageπage142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3…… ……101088…108…14Cross product Input: two tables R and S Notation: R × S Purpose: pairs rows from two tablesOutput: for each rowrinRand each rowsinSOutput: for each row rin Rand each row sin S, output a row rs (concatenation of r and s)15Cross product example Student × Enroll×SID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1…… ……SID CID142 CPS116142 CPS114123 CPS116……SID name age GPA SID CID142 Bart 10 2.3 142 CPS116142 Bart 10 2.3 142 CPS114142 Bart 10 2.3 123 CPS116123 Milhouse 10 3.1 142 CPS116123 Milhouse 10 3.1 142 CPS114123 Milhouse 10 3.1 123 CPS116…… ……… …616A note on column ordering The ordering of columns in a table is considered unimportant (as is the ordering of rows)SID name age GPA SID CID142 Bart 10 2.3 142 CPS116142 Bart 10 2.3 142 CPS114SID CID142 CPS116142 CPS114SID name age GPA142 Bart 10 2.3142 Bart 10 2.3 That means cross product is commutative, i.e.,R × S = S × R for any R and S=142 Bart 10 2.3 123 CPS116123 Milhouse 10 3.1 142 CPS116123 Milhouse 10 3.1 142 CPS114123 Milhouse 10 3.1 123 CPS116…… ……… …123 CPS116142 CPS116142 CPS114123 CPS116……142 Bart 10 2.3123 Milhouse 10 3.1123 Milhouse 10 3.1123 Milhouse 10 3.1…… ……17Derived operator: join Input: two tables R and S Notation: R !pS p is called a join condition/predicate Purpose: relate rows from two tables according to pgsome criteria Output: for each row r in R and each row s in S, output a row rs if r and s satisfy p Shorthand for σp( R × S )18Join example Info about students, plus CID’s of their coursesStudent !Student.SID = Enroll.SIDEnroll×!SdSIDSID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1SID CID142 CPS116142 CPS114×Student.SID= Enroll.SIDUse table_name. column_name syntaxto disambiguate identically named columns from different input tables…… ……123 CPS116……SID name age GPA SID CID142 Bart 10 2.3 142 CPS116142 Bart 10 2.3 142 CPS114142 Bart 10 2.3 123 CPS116123 Milhouse 10 3.1 142 CPS116123 Milhouse 10 3.1 142 CPS114123 Milhouse 10 3.1 123 CPS116…… ……… …SID name age GPA SID CID142 Bart 10 2.3 142 CPS116142 Bart 10 2.3 142 CPS114123 Milhouse 10 3.1 123 CPS116…… ……… …719Derived operator: natural join Input: two tables R and S Notation: R ! S Purpose: relate rows from two tables, and Enforce equality on all common attributesoc qu yo co o bu s Eliminate one copy of common attributes Shorthand for πL( R !pS ), where p equates all attributes common to R and S L is the union of all attributes from R and S, with duplicate attributes removed20Natural join example Student ! Enroll = π?( Student !?Enroll )= πSID, name, age, GPA, CID( Student !Student.SID =


View Full Document

Duke CPS 116 - Relational Model & Algebra

Documents in this Course
Part I

Part I

8 pages

XSLT

XSLT

4 pages

XSLT

XSLT

8 pages

Part I

Part I

8 pages

XSLT

XSLT

8 pages

Load more
Download Relational Model & Algebra
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 Model & Algebra 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 Model & Algebra 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?