Please solve 4 questions by using this latex symbol: https://oeis.org/wiki/List_of_LaTeX_mathematical_symbols
The Relational Model The Relational Model Lecture 18 Today’s Lecture The Relational Model & Relational Algebra Relational Algebra Pt. II 2 Lecture 18 2 1. The Relational Model & Relational Algebra 3 Lecture 18 > Section 1 What you will learn about in this section The Relational Model Relational Algebra: Basic Operators Execution ACTIVITY: From SQL to RA & Back 4 Lecture 18 > Section 1 4 Motivation The Relational model is precise, implementable, and we can operate on it (query/update, etc.) Database maps internally into this procedural language. Lecture 18 > Section 1 > The Relational Model 5 A Little History Relational model due to Edgar “Ted” Codd, a mathematician at IBM in 1970 A Relational Model of Data for Large Shared Data Banks". Communications of the ACM 13 (6): 377–387 IBM didn’t want to use relational model (take money from their Information Management System) Won Turing award 1981 Lecture 18 > Section 1 > The Relational Model IMS apparently used in the moonshot (http://www-01.ibm.com/software/data/ims/benchmark.html) and still boasts high #s 6 The Relational Model: Schemata Relational Schema: Lecture 18 > Section 1 > The Relational Model Students(sid: string, name: string, gpa: float) Attributes String, float, int, etc. are the domains of the attributes Relation name 7 8 The Relational Model: Data sidnamegpa 001Bob3.2 002Joe2.8 003Mary3.8 004Alice3.5 Student An attribute (or column) is a typed data entry present in each tuple in the relation The number of attributes is the arity of the relation Lecture 18 > Section 1 > The Relational Model 8 9 The Relational Model: Data sidnamegpa 001Bob3.2 002Joe2.8 003Mary3.8 004Alice3.5 Student A tuple or row (or record) is a single entry in the table having the attributes specified by the schema The number of tuples is the cardinality of the relation Lecture 18 > Section 1 > The Relational Model 9 10 The Relational Model: Data Student A relational instance is a set of tuples all conforming to the same schema Recall: In practice DBMSs relax the set requirement, and use multisets. sidnamegpa 001Bob3.2 002Joe2.8 003Mary3.8 004Alice3.5 Lecture 18 > Section 1 > The Relational Model 10 A relational schema describes the data that is contained in a relational instance To Reiterate Let R(f1:Dom1,…,fm:Domm) be a relational schema then, an instance of R is a subset of Dom1 x Dom2 x … x Domn Lecture 18 > Section 1 > The Relational Model In this way, a relational schema R is a total function from attribute names to types 11 A relational schema describes the data that is contained in a relational instance One More Time A relation R of arity t is a function: R : Dom1 x … x Domt {0,1} Lecture 18 > Section 1 > The Relational Model Then, the schema is simply the signature of the function I.e. returns whether or not a tuple of matching types is a member of it Note here that order matters, attribute name doesn’t… We’ll (mostly) work with the other model (last slide) in which attribute name matters, order doesn’t! 12 A relational database A relational database schema is a set of relational schemata, one for each relation A relational database instance is a set of relational instances, one for each relation Two conventions: We call relational database instances as simply databases We assume all instances are valid, i.e., satisfy the domain constraints Lecture 18 > Section 1 > The Relational Model 13 Remember the CMS Relation DB Schema Students(sid: string, name: string, gpa: float) Courses(cid: string, cname: string, credits: int) Enrolled(sid: string, cid: string, grade: string) SidNameGpa 101Bob3.2 123Mary3.8 Students cidcnamecredits 564564-24 3084172 Courses sidcidGrade 123564A Enrolled Relation Instances 14 Lecture 18 > Section 1 > The Relational Model Note that the schemas impose effective domain / type constraints, i.e. Gpa can’t be “Apple” 14 2nd Part of the Model: Querying “Find names of all students with GPA > 3.5” We don’t tell the system how or where to get the data- just what we want, i.e., Querying is declarative Actually, I showed how to do this translation for a much richer language! Lecture 18 > Section 1 > The Relational Model SELECT S.name FROM Students S WHERE S.gpa > 3.5; To make this happen, we need to translate the declarative query into a series of operators… we’ll see this next! 15 Virtues of the model Physical independence (logical too), Declarative Simple, elegant clean: Everything is a relation Why did it take multiple years? Doubted it could be done efficiently. Lecture 18 > Section 1 > The Relational Model 16 Relational Algebra Lecture 18 > Section 1 > Relational Algebra RDBMS Architecture How does a SQL engine work ? SQL Query Relational Algebra (RA) Plan Optimized RA Plan Execution Declarative query (from user) Translate to relational algebra expresson Find logically equivalent- but more efficient- RA expression Execute each operator of the optimized plan! Lecture 18 > Section 1 > Relational Algebra RDBMS Architecture How does a SQL engine work ? SQL Query Relational Algebra (RA) Plan Optimized RA Plan Execution Relational Algebra allows us to translate declarative (SQL) queries into precise and optimizable expressions! Lecture 18 > Section 1 > Relational Algebra Five basic operators: Selection: s Projection: P Cartesian Product: Union: Difference: - Derived or auxiliary operators: Intersection, complement Joins (natural,equi-join, theta join, semi-join) Renaming: r Division Relational Algebra (RA) We’ll look at these first! And also at one example of a derived operator (natural join) and a special operator (renaming) Lecture 18 > Section 1 > Relational Algebra Keep in mind: RA operates on sets! RDBMSs use multisets, however in relational algebra formalism we will consider sets! Also: we will consider the named perspective, where every attribute must have a unique name attribute order does not matter… Lecture 18 > Section 1 > Relational Algebra Now on to the basic RA operators… Returns all tuples which satisfy a condition Notation: sc(R) Examples sSalary > 40000 (Employee) sname = “Smith” (Employee) The condition c can be =, <, ,="">, , <> 1. Selection () SELECT * FROM Students WHERE gpa > 3.5; SQL: RA: Students(sid,sname,gpa) Lecture 18 > Section 1 > Relational Algebra sSalary > 40000 (Employee) SSNNameSalary 1234545John200000 5423341Smith600000 4352342Fred500000 SSNNameSalary 5423341Smith600000 4352342Fred500000 Another example: Lecture 18 > Section 1 > Relational Algebra Eliminates columns, then removes duplicates Notation: P A1,…,An (R) Example: project social-security number and names: P SSN, Name (Employee) Output schema: Answer(SSN, Name) 2. Projection () SELECT DISTINCT sname, gpa FROM Students; SQL: RA: Students(sid,sname,gpa) Lecture 18 > Section 1 > Relational Algebra P Name,Salary (Employee) SSNNameSalary 1234545John200000 5423341John600000 4352342John200000 NameSalary John200000 John600000 Another example: Lecture 18 > Section 1 > Relational Algebra Note that RA Operators are Compositional! SELECT DISTINCT sname, gpa FROM Students WHERE gpa > 3.5; Students(sid,sname,gpa) How do we represent this query in RA? Are these logically equivalent? Lecture 18 > Section 1 > Relational Algebra Each tuple in R1 with each tuple in R2 Notation: R1 R2 Example: Employee Dependents Rare in practice; mainly used to express joins 3. Cross-Product () SELECT * FROM Students, People; SQL: RA: Students(sid,sname,gpa) People(ssn,pname,address) Lecture 18 > Section 1 > Relational Algebra ssnpnameaddress 1234545John216 Rosse 5423341Bob217 Rosse sidsnamegpa 001John3.4 002Bob1.3 ssnpnameaddresssidsnamegpa 1234545John216 Rosse001John3.4 5423341Bob217 Rosse001John3.4 1234545John216 Rosse002Bob1.3 5423341Bob216 Rosse002Bob1.3 People Students Another example: Lecture 18 > Section 1 > Relational Algebra Changes the schema, not the instance A ‘special’ operator- neither basic nor derived Notation: r B1,…,Bn (R) Note: this is shorthand for the proper form (since names, not order matters!): r A1B1,…,AnBn (R) Renaming () SELECT sid AS studId, sname AS name, gpa AS gradePtAvg FROM Students; SQL: RA: Students(sid,sname,gpa) We care about this operator because we are working in a named perspective Lecture 18 > Section 1 > Relational Algebra sidsnamegpa 001John3.4 002Bob1.3 Students studIdnamegradePtAvg 001John3.4 002Bob1.3 Students Another example: Lecture 18 > Section 1 > Relational Algebra Notation: R1 R2 Joins R1 and R2 on equality of all shared attributes If R1 has attribute set A, and R2 has attribute set B, and they share attributes AB = C, can also be written: R1 R2 Our first example of a derived RA operator: Meaning: R1 R2 = PA U B(sC=D(R1) R2)) Where: The rename renames the shared attributes in one of the relations The selection sC=D checks equality of the shared attributes The projection PA U B eliminates the duplicate common attributes Natural Join () SELECT DISTINCT ssid, S.name, gpa, ssn, address FROM Students S, People P WHERE S.name = P.name; SQL: RA: Students(sid,name,gpa) People(ssn,name,address) Lecture 18 > Section 1 > Relational Algebra ssnP.nameaddress 1234545John216 Rosse 5423341Bob217 Rosse sidS.namegpa 001John3.4 002Bob1.3 sidS.namegpassnaddress 001John3.41234545216 Rosse 002Bob1.35423341216 Rosse People P Students S Another example: Lecture 18 > Section 1 > Relational Algebra Natural Join Given schemas R(A, B, C, D), S(A, C, E), what is the schema of R S ? Given R(A, B, C), S(D, E), what is R S ? Given R(A, B), S(A, B), what is R S ? Lecture 18 > Section 1 > Relational Algebra Example: Converting SFW Query -> RA SELECT DISTINCT gpa, address FROM Students S, People P WHERE gpa > 3.5 AND sname = pname; How do we represent this query in RA? Lecture 18 > Section 1 > Relational Algebra Students(sid,sname,gpa) People(ssn,sname,address) Logical Equivalece of RA Plans Given relations R(A,B) and S(B,C): Here, projection & selection commute: What about here? We’ll look at this in more depth later in the lecture… Lecture 18 > Section 1 > Relational Algebra RDBMS Architecture How does a SQL engine work ? SQL Query Relational Algebra (RA) Plan Optimized RA Plan Execution We saw how we can transform declarative SQL queries into precise, compositional RA plans Lecture 18 > Section 1 > Relational Algebra RDBMS Architecture How does a SQL engine work ? SQL Query Relational