1Relational Model & AlgebraCPS 116Introduction to Database Systems2Announcements (Thurs. September 1) Please sign up for mailing list and database (IBM DB2) accounts on the sign-up sheet (now circulating) Homework #1 will be assigned next Tuesday Office hours: see also course Web page Jun: TTH afternoon Ming: MW late afternoon Book update $101 (new) / $75.75 (used) from Duke bookstore• Available possibly tomorrow and definitely by next Tuesday $86.15 (new, free shipping) from Amazon3Relational 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 attributesSimplicity is a virtue!4ExampleStudent CourseEnrollOrdering of rows doesn’t matter(even though the output isalways in some order)SID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3... ... ... ...CID titleCPS116 Intro. to Database SystemsCPS130 Analysis of AlgorithmsCPS114 Computer Networks... ...SID C ID142 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)Instance { h142, Bart, 10, 2.3i, h123, Milhouse, 10, 3.1i, ...} { hCPS116, Intro. to Database Systemsi, ...} { h142, CPS116i, h142, CPS114i, ...}27Relational algebra 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 queriesRelOpRelOpA language for querying relational databases based on operators:8Selection Input: a table R Notation: σpR p is called a selection condition/predicate Purpose: filter rows according to some criteria Output: same columns as R, but only rows of R that satisfy p9Selection example Students with GPA higher than 3.0σGPA > 3.0StudentσGPA > 3.0SID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3SID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.310More 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 output Output: same rows, but only the columns in L12Projection example ID’s and names of all studentsπSID, nameStudentπSID, nameSID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3SID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3313More on projection Duplicate output rows are removed (by definition) Example: student agesπageStudentπageSID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.3SID name age GPA142 Bart 10 2.3123 Milhouse 10 3.1857 Lisa 8 4.3456 Ralph 8 2.314Cross product Input: two tables R and S Notation: R × S Purpose: pairs rows from two tables Output: for each row r in R and each row s in S, output a row rs (concatenation of r and s)15Cross product example Student × EnrollSID 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... ... ... ... ... ...16A 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 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 CID SID name age GPA142 CPS116 142 Bart 10 2.3142 CPS114 142 Bart 10 2.3123 CPS116 142 Bart 10 2.3142 CPS116 123 Milhouse 10 3.1142 CPS114 123 Milhouse 10 3.1123 CPS116 123 Milhouse 10 3.1... ... ... ... ... ... That means cross product is commutative, i.e.,R × S = S × R for any R and S=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 some 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.SIDEnrollSID 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... ... ... ... ... ...Student.SID = Enroll.SIDUse table_name. column_name syntaxto disambiguate identically named columns from different input tables419Derived operator: natural join Input: two tables R and S Notation: R S Purpose: relate rows from two tables, and Enforce equality on all common attributes 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 removed20SID 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... ... ... ...
View Full Document
Unlocking...