Overview of System R: Relational Data Model and SQL Query Language

System R Mike Cafarella (some slides thx to Chris Re)

One Slide Summary of System R System R is one of the most important systems in DB history Several ideas in this paper stayed with us for decades Main Contribution: Show that one could build an RDBMS based on the Relational Model

Goal of System R EMP(NAME,DNO,JOB,SAL) DEPT(DNO,DNAME,LOC) JOB(JOB,TITLE) SELECT NAME, TITLE, SAL, DNAME FROM EMP, DEPT, JOB WHERE TITLE= Clerk AND LOC= Denver AND EMP.DNO=DEPT.DNO AND EMP.JOB=JOB.JOB Retrieve the name, salary, job title, and department of employees who are clerks and work for departments in Denver

Relational Data Model A data model is a collection of concepts for describing data A schema is a description of a particular collection of data, using the given data model The relational model is the most widely used today Main concept: relation, basically a table with rows and columns. Every relation has a schema, which specifies the name of the relation, name and type (domain) of each column. Can think of a relation as a set of rows or tuples. (i.e., all rows are distinct) 3/12/2025 4

Example Instance of Students Relation Specifies schema sid 53666 Jones jones@cs 53688 Smith smith@eecs 53650 Smith smith@math name login age gpa 18 18 19 3.4 3.2 3.8 Order of rows is not important Sets (classic relational) vs. Multisets (SQL) All rows are distinct 3/12/2025 5

The SQL Query Language To find all 18 year old students, we can write: SELECT * FROM Students S WHERE S.age=18 53688 Smith smith@ee 18 sid 53666 Jones name login jones@cs age gpa 18 3.4 3.2 To find just names and logins, replace the first line: SELECT S.name, S.login 3/12/2025 6

The SQL Query Language What does the following query compute? SELECT S.name, E.cid FROM Students S, Enrolled E WHERE S.sid=E.sid AND E.grade= A sid cid grade C B A B Given the following instances of Enrolled and Students: 53831 Carnatic101 53831 Reggae203 53650 Topology112 53666 History105 sid 53666 Jones jones@cs 53688 Smith smith@eecs 53650 Smith smith@math name login age gpa 18 18 19 3.4 3.2 3.8 we get: S.name Smith E.cid Topology112 3/12/2025 7

Integrity Constraints Key constraints Minimal subset of attributes is a unique identifier for a tuple One key identified as primary key Foreign key constraints Information stored in one relation linked to another relation Primary key attributes reference foreign key attributes General constraints 3/12/2025 8

What Came Before Relational DBs One example: IMS hierarchical model (1968) Overview: Record types arranged as hierarchy Each type has single parent Sample Instances Type Hierarchy (Schema) Supplier 16, General Supply, Boston, MA (sno, sname, scity, sstate) Part 27, Power Saw, 7, silver, 100, $20 (pno, pname, psize, pcolor, qty, price) (Each record has a key) 3/12/2025 9

Some Problems Schema #1 Schema #2 Supplier Part (sno, sname, scity, sstate) (pno, pname, psize, pcolor, qty, price) Part Supplier (pno, pname, psize, pcolor, qty, price) (sno, sname, scity, sstate) Information repeated Schema 1: Part info repeated for each supplier that supplies the part Schema 2: Supplier info repeated for each part it supplies Existence depends on parent data Schema 1: What if there is a part not currently supplied by anyone?

DL/1 (Programming Language for IMS) Record-at-a-time language Programmer constructs an algorithm for solving her query; IMS executes it Supplier Find red parts supplied by Supplier 16 (sno, sname, scity, sstate) Part (pno, pname, psize, pcolor, qty, price) Get unique Supplier (sno = 16) Until no-more { Get next within parent (color = red) } Until no-more { Get next Part (color = red) } 3/12/2025 11

DL/1 (Programming Language for IMS) Different underlying storage formats = different restrictions on commands Heavy coupling between storage format used (sequential/B-tree/hashed) and client applications Thus, poor physical data independence Different sets of data = different optimization opportunities Optimization is performed by programmer 3/12/2025 12 EECS 584, Fall 2011

System Rs Contributions First relational implementation Query optimization model Access paths Join selection Recovery Views Locking 3/12/2025 13

1. Query Optimization Model Parsed (Syntax Check) Optimization Code Selection Execution RSS: The Storage Manager (locking/access paths)

Optimization Input What should be considered during optimization? How to measure plan s cost? Why is writing an optimizer difficult? Why doesn t UNIX have one? (Or does it?) Now an aside 3/12/2025 15

Memory Hierarchy 0.5-5 Clocks 1-5 Clocks 50-100 clocks 10-50 Clocks 105clocks If one CPU instruction is 1 second, then a disk read takes a month!

The Mechanics of Disk Cylinder Mechanical characteristics: Rotation speed (5400RPM) Number of platters (1-30) Number of tracks (<=10000) Number of bytes/track(105) Spindle Tracks Disk head Sector Unit of read or write: disk block: k*Sector Size Once in memory: page Typically: 4k or 8k or 16k Platters Arm movement Arm assembly 17

The Mechanics of Disk Cylinder Next Block concept (1) Blocks on same track (2) Blocks on same cylinder (3) Blocks on adjacent cylinder Spindle Tracks Disk head Sector Platters Disks read/write one block at a time Arm movement Arm assembly 18

Disk Access Characteristics Disk latency = time between when command is issued and when data is in memory Disk latency = seek time + rotational latency Seek time = time for the head to reach cylinder: 8-10ms Rotational latency = time for the sector to rotate Rotation time = 10ms & Average latency = 10ms/2 If RPM=7200, what is the latency? Transfer time = typically 780MB/s 3MB/s For traditional hardware, optimizer largely concerns itself with avoiding disk latency 19

Optimization: Access Paths Heap vs B-Tree Why prefer one to the other? 3/12/2025 20

Optimization: Join Algorithms Merge Join Nested Loop Join <whiteboard> 3/12/2025 21

2. Recovery Different failure modes Disk System Transaction Solutions to each? 3/12/2025 22

3. Views and Authorization A view is a SQL query Why bother with them? Closest OS analogue? Differences between OS access control and view-centric access control? 3/12/2025 23

4. Locking What are the different access coordination problems UNIX and System R try to solve? <whiteboard for hierarchical locking> 3/12/2025 24