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)IInstance { 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 tablesOutput: for each rowrinRand each rowsinSOutput: 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