CS 3200 - Fall 2024

​

The Relational Model of Data

Mark Fontenot, PhD

Northeastern University

These notes are based upon and adapted via the generosity of Prof. Nate Derbinsky.

Reminders

• Join Slack & CampusWire!!
• Make sure you can see the course in GradeScope

​

• Mini HW00
• Early EC Deadline: Sunday 9/8 11:59 pm
• Regular Deadline: Monday 9/10 11:59 pm

2

Applications and Data

• Many applications are data intensive compared to compute intensive.
• Many apps need to…
• store data for itself or another app to use in the future (databases)
• remember the results of prior expensive operations (caches)
• allow users to search for data efficiently (indexes)
• send messages with data to another application to handle (stream processing)
• periodically process a large accumulation of data (batch processing)

3

From Kleppmann, Designing Data Intensive Applications, O’Reilly, 2017.

Stores of data?

4

What is a database?

• Structured collection of related data
• usually related to something in the real world
• usually created…
• for a specific group of users
• to help these users perform some kind of tasks
• to hopefully complete those tasks with some performance, redundancy, concurrency, and/or security considerations in mind

5

Notion

• Intended users?
• Intended tasks?
• Considerations of
• Performance?
• Concurrency?
• Redundancy?
• Security?

6

Database Management Systems (DBMS)

• Software that allow the creation and maintenance of databases
• Support the encoding of some type of structure for the data
• Persists the data
• Support adding new data and updating existing data
• Protects against failures and unauthorized access

7

Some Categories of DBMSs

Document-Oriented Databases

- Organizes and queries data based on the concept of a “document” often in JSON

- usually considered semi-structured

Graph Databases

- Organizes data by nodes, edges, labels

- Query about paths between nodes and node relationships

8

Some Categories of DBMSs

Key-Value Databases

- Everything is a key/value pair

- Based on associative array

​

Spatial Databases

- Stores data related to 2D/3D locations

- Query example: are 2 cars about to collide?

9

Some Categories of DBMSs

Vector Databases

• unit of storage is a vector represent high-dimensional data
• highly performant similarity searches
• used extensively in LLMs

10

The category for this course…

• Relational Database Management Systems
• Based on storing data in tables and connections between those tables
• Original concept developed in early 70s by EF Codd and colleagues

11

Relational Model of Data:

Overview

12

The Relational Database: Relation/Table

13

Image borrowed from this Medium post.

Relation - the core construct in a relational database.

​

Relation Schema - represents the attributes and data types for a particular relation

​

Relation Instance - represents the state of the data in the relation at a particular point in time.

​

Row/Tuple - values for each relation’s attribute for one element of a relation instance

The Relational Database: Constraints

14

Image borrowed from this Medium post.

cannot be

null

Must be a valid dorm id in the dorm relation

Example

Constraints:

Constraint - conditions that must hold on all valid relation instances

​

Types:

• Key Constraints
• Entity Integrity Constraints
• Referential Integrity constraints

​

​

Student

The Relational Database: Relationships

15

Student

Dorm

Class

Some values in one table are related (by design) to values in another table

Referential Integrity Constraint Examples

The Relational Database: Queries

16

Student

Dorm

Class

Questions (Queries):

​

“Provide a list of student names and IDs with GPA between 3.0 and 3.5.”

The Relational Database: Queries

17

Student

Dorm

Class

Questions (Queries):

​

“Which students live in Baker Dorm?”

Databases in the Context of a Software System

18

Database

Tier

Application

Tier

Client

Tier

The Relational Model of Data:�Digging In

19

History 101

Codd, Edgar F. "A relational model of data for large shared data banks." Communications of the ACM 13.6 (1970): 377-387.

20

“Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation)…”

History 101

• The relational model provides a formal mathematical basis for the structure of and interaction with a relational database
• Based on set theory and first-order predicate logic
• The formal basis allows for robust scientific development of the model.
• The (eternal) struggle of theory vs. practice…
• Most modern RDBMSs don’t strictly adhere to the purest mathematical formalisms in the relational model.

21

A Little Set Theory Review…

• What’s a set?�

​

• What is the cardinality of a set? (denoted |S|)

�

​

​

22

A set is a collection of unique objects. The things (objects) inside a set are called elements.

cardinality → the number of unique elements in the set.

What are some examples of sets?

?

A Little Set Theory Review…

• What is the Union of sets A and B (A ⋃ B)?

​

• What is the intersection of sets A and B (A ∩ B)?�
• What is the set difference of A and B (A - B)?

​

23

A = {1, 3, 5} B = {3, 4, 5, 6}

A Little Set Theory Review…

• What is the cartesian product of two sets?

​

​

​

A = {123, 435} B = {Chul, Kev, Sal}

• What is the cartesian product of A and B (aka A x B)?

​

24

{ (123, Chul), (123, Kev), (123, Sal), (435, Chul), (435, Kev), (435, Sal) }

What’s a Relational Database?

• A Relational Database consists of
• a collection of relations, and
• a collection of constraints.

​

• A relational database is in a valid/consistent state if it satisfies all constraints (else, invalid/inconsistent state).

25

Relations

• A relation consists of
• its schema → a description of the structure of the relation (relation schema)
• its state → the current data that is populated in the relation (relation instance)
• The schema of a relation includes
• the name of the relation
• an list of n attributes each with an associated domain (what values that attribute can take on).
• Notation: REL_NAME(Attrib1:Dom1, Attrib2:Dom2…)

26

More formally…

• Let A₁, A₂, …, A_n be names of attributes of relation R with associated domains D₁, D₂, …, D_n, then � R(A₁:D₁, A₂:D₂,...A_n:D_n) �is a relation schema and n, the degree of R, represents the number of attributes of R.�
• An instance of Relation R is a subset of the cartesian product of the domains of the attributes of R.

27

Relations - Example

• Assume we have the following domains:
• names → {‘Jared’, ‘Sakshi’}
• id_nums → {all 9 digit positive integers starting with 00}
• majors → {‘CS’, ‘DS’, ‘CY’}
• Defining the TA relation schema:� TA(name: names, id: id_nums, major: majors)

28

Is the following a valid instance of TA?

{

(‘Jared’, 001928374, ‘CS’)� (‘Sakshi’, 001122334, ‘DS’)

}

?

Relations - Example

• Assume we have the following domains:
• names → {‘Jared’, ‘Sakshi’}
• id_nums → {all 9 digit positive integers starting with 00}
• majors → {‘CS’, ‘DS’, ‘CY’}
• Defining the TA relation schema:� TA(name: names, id: id_nums, major: majors)

29

Is the following a valid instance of TA?

{

(‘Sakshi’, 001928374, ‘CS’)� (‘Sakshi’, 001122334, ‘CY’)

}

?

Relations - Example

• Assume we have the following domains:
• names → {‘Jared’, ‘Sakshi’}
• id_nums → {all 9 digit positive integers starting with 00}
• majors → {‘CS’, ‘DS’, ‘CY’}
• Defining the TA relation schema:� TA(name: names, id: id_nums, major: majors)

30

Is the following a valid instance of TA?

{

(‘Sakshi’, 001928374, ‘CS’)� (‘Dylan’, 001122334, ‘DS’)

}

?

Relations - Example

• Assume we have the following domains:
• names → {‘Jared’, ‘Sakshi’}
• id_nums → {all 9 digit positive integers starting with 00}
• majors → {‘CS’, ‘DS’, ‘CY’}
• Defining the TA relation schema:� TA(name: names, id: id_nums, major: majors)

31

Is the following a valid instance of TA?

{

(‘Sakshi’, 001928374, ‘CS’)� (‘Jared’, 001122334)

}

?

Relation Instance

• A relation instance is a set of tuples (rows) from a relation at a particular point in time.
• Each tuple (row) is an ordered sequence of values, one for each attribute (possibly null)
• usually enclosed in < and >

​

​

32

Student

1 Tuple

Tuples: Theory vs. Practice

• Theory: a relation instance is defined as a set of tuples.
• tuples are unordered
• tuples cannot be duplicated
• Practice: rows in a table are implemented as multisets and stored in some physical medium (disk)
• if they’re on a disk, they are in some order
• later.. physical design might dictate some specific order
• bags/multisets imply duplicate tuples allowed.

33

Null Value

• Null is a special value that may exist in the domain of an attribute
• Could mean different things
• value unknown
• value unavailable right now
• attribute doesn’t apply to this tuple
• Does NOT mean:
• zero (0)
• the empty string (‘’)
• (NULL != NULL) Comparing two values of NULL does NOT return true

34

Value of an Attr in a Tuple

• Values should be atomic
• Say NO to composite attributes (ex: address that includes city, state and zip)
• Say NO to multi-valued attributes (ex: all email addresses for 1 person)

35

Student

Super and Candidate Keys

• key - a subset of attributes of a relation used to uniquely identify one tuple in a relation from other tuples

​

• A super key of a relation R is a subset of the attributes of R such that no two distinct tuples in any possible relation instance will have the same values for the subset of attributes.
• may not be minimal - could contain attributes that aren’t needed for unique determination
• A candidate key of relation r is a minimal super key.
• A relation may have more than one candidate keys.

36

Keys - Superkey

37

Some Possible Superkeys:

(customerNumber, customerName)

(customerNumber, salesRepEmployeeNumber)

(customerNumber)

Not Minimal

​

​

Minimal

Customers

Keys - Candidate Keys

38

Some Possible Superkeys:

(customerNumber, customerName)

(customerNumber, salesRepEmployeeNumber)

(customerNumber)

Not Candidate Keys

​

​

Candidate Key

Customers

The Primary Key

• The primary key (PK) of relation R is chosen from the set of candidate keys
• If a relation has only 1 candidate key, it becomes the PK.
• If a relation has > 1 candidate key, the database designer chooses one based on business requirements
• Every relation must have a PK
• Entity Integrity Constraint → PK values must be unique and may NOT be null
• (Usually) the PK is underlined in a relation schema or table

39

Keys - Primary Key

40

Some Possible Superkeys:

(customerNumber, customerName)

(customerNumber, salesRepEmployeeNumber)

(customerNumber)

Chosen as Primary Key

If there are 2+ Candidate Keys, DB Designer will choose one as the Primary key

Customers

Foreign Keys

• Foreign Key (FK) - An attribute a_i in one relation R_C (the child relation) refers to/references the PK a_j in another relation R_P (parent relation) suck that all values of a_i must either be NULL or contain a value from a_j.

​

• Self-Referential Relation → R_C and R_P are the same relation
• Foreign Key == Referential Integrity Constraint
• Foreign Keys are the operationalization of relationships in a relational database

41

Foreign Key Example

42

Students

Grades

Parent Relation Child Relation

(the one being referenced) (the one referencing another relation)

Primary Keys Foreign Key

Note: in this example, Grades.sID cannot contain null values because it is part of the PK of Grades Relation.

FKs - but why???

43

Customers

Notice: empLast, empFirst, and empEmail attributes contain duplicated/repeated data. Opens up the possibility of insert or update anomalies.

​

So, put them in a separate table along with empNum and refer back to the new table (becomes the parent table)

Relational Algebra

44

Relational Algebra

• Relational Algebra (RA) : a procedural query language for relations that allow us to retrieve information from a relational database
• A query is an operation or set of operations applied to one or more relation instances
• RA is closed, meaning the result/output of each query is another relation
• In RA, order of operations matters
• Forms the basis for the SELECT statement in SQL.

45

Quick Aside: Predicate Functions

• Predicate functions - functions that return true or false.
• We will use predicate functions (or just “predicates”) to determine if tuples in a relation instance should be returned by a query or not.
• in the form attr <op> attr OR attr <op> <constant>
• <op> can be any standard relational operator (=, !=, <, >, <=, etc)
• predicates can be composed with ^ (and), v (or), ㄱ (not).

​

Examples:

• empID = 143
• empID > 400
• firstName = ‘Bob’ ^ empID = 333

​

46

Employees

The First 6 Basic Operations of RA

1. Select σ (Tuple Filtering)
2. Project π (Attribute Filtering)
3. Join ⨝
4. Cartesian Product ✕
5. Set-difference –
6. Union/Intersection U ⋂
7. Rename ρ

​

47

Relational Algebra: Select Operator

• Select - return a relation containing tuples from relation R that satisfy predicate pred.

​

Notation:�

• Can be thought of as a horizontal subset (subset of tuples/rows) of a relation instance

48

Relational Algebra: Select Operator

49

Enrollments

Enrollments

Result:

Relational Algebra: Select Operator

50

Enrollments

Enrollments

Result:

Relational Algebra: Project Operator

Project - returns a relation with a subset of attributes (A₁… A_k) from R.

�Notation:

​

Duplicate tuples will be removed from the resulting relation (because relations are sets).

51

Relational Algebra: Project Operator

52

Enrollments

Enrollments

Enrollments

Result:

Result:

Relational Algebra: Cartesian Product

Same operation we know from set theory.

​

53

R

S

Union, Intersection & Difference

• Essentially the same as what we know from set theory.

​

​

• One small difference: relations must be schema compatible
• same number of attributes
• attributes’ domains must be compatible

54

More Complex RA Expressions

• Simple RA expression can be composed into more complex expressions
• Remember: output of each RA operation is another relation

55

Relational Algebra: Temporary Relation Names

For more complex RA queries, you can have:

• one long query expression
• an ordered list of smaller expressions, the result of each is given a temporary name with the ← operator

​

Example:

• TEMP_NAME ←

TEMP_NAME can then be used as a relation in subsequent steps of the same query.

​

​

56

Relational Algebra: Rename Operator

Rename Operator (rho) – Allows us to “rename” a relation, the attributes of a relation, or both.

• If only name is provided, the relation is being renamed (all attributes retain their original name.)

​

• List of attributes in parentheses means renaming attributes, but not relation (assume attributes originally (employeeID, lastName, firstName)

​

​

​

• Rename both.

​

​

57

Developing Relational Algebra Expressions

58

Writing RA Queries

• Sometimes we need to evaluate an RA query against a database instance
• Result is usually another relation instance/set of tuples/table
• Other times we need to convert the narrative form of a query into a RA query
• Example: “Provide a list of all info from the Employee relation where the empID is less than 400.”
• Answer:

59

Writing RA Queries

60

Students

Courses

Grades

Next few examples use this database schema.

Writing RA Queries

61

Students

Courses

Grades

Write a RA query that returns the names of all students.

Writing RA Queries

62

Students

Courses

Grades

Provide a list of all course numbers taught by the CS Department.

Writing RA Queries

63

Students

Courses

Grades

List all 2nd year student names.

Writing RA Queries

64

Students

Courses

Grades

What course or courses (dept and number) are taught by Professor Norris?

Writing RA Queries

65

Students

Courses

Grades

List the letter grades that Sam has earned (don’t need to include course info).

Joining Data from Two Relations

66

Relational Algebra: The Join Operator

• Join - allows us to combine data from two relations.
• Subset of the cartesian product of the two argument relations based on explicit or implicit join predicate.

​

• 2 Versions:
• Natural Join - Join relations on attributes with the same name

• Theta Join (or condition join or simply Join) - Join relations with explicitly supplied join predicate

67

Natural Join

• Given: A(R, S, T, U, V) and B(S, V, W, X)
• Query:
• Notice: A and B both have attributes named S & V.
• Result:
• Schema of resulting relation is

where attr(R) returns a set containing the attributes of R

• so, attributes used in the implicit join condition are not duplicated in the result
• contains any tuple from A x B where values for attributes S and V are equal
• If A & B have no common attribute names, result is A X B.

68

Example

69

Students

Grades

Query:

Result:

theta-Join (or Join… or Condition(al) Join)

• Operator has an explicit join predicate (condition) (doesn’t rely upon attribute names)
• Result is a subset of the cartesian product where provided predicate holds true
• Assume: S(sID, name) and G(stu-ID, course, semester, grade)
• Query:
• Result:
• Relation with schema (sID, name, stu-ID, course, semester, grade)
• all tuples where S.sID = G.stu-ID
• Note: join condition can use other operators besides =.

70

theta-Join (or Join… or Condition(al) Join)

71

A

B

1

Cat

2

Dog

3

Bird

C

D

1

Meow

3

Chirp

S

T

A

B

1

Cat

3

Bird

C

D

1

Meow

3

Chirp

New: Entity Relationship Diagram

72

Northwind Traders Data Model

- sample database model that has been around

for years; originally developed by Microsoft

- represents data model for fake Northwind Traders company, an importer/exporter of specialty foods

New: ER Diagram

73

Relation Name

Attributes

Primary Key Attributes

Relationships

Relations in Northwind

• Suppliers: Suppliers and vendors of Northwind
• Customers: Customers who buy products from Northwind
• Employees: Employee details of Northwind traders
• Products: Product information
• Shippers: The details of the shippers who ship the products from the traders to the end-customers
• Orders and Order_Details: Sales Order transactions taking place between the customers & the company
• Categories: The categories a product can fall into

74

Practice Time!

75

For each of the following, compose a relational algebra query that satisfies the narrative-form of the question.

Query Time!

76

1. For each supplier, provide its name, contact person, and phone number.

Query Time!

77

2. Which products are supplied by FoodsRUs? Please include the product name and unit price.

Query Time!

78

3. Provide a list of all product names ordered by World Market (a customer’s name).

Query Time!

79

4. Which customers has employee Sam Johnson worked with? Provide the complete customer information.

Further Reading

• Harrington Ch5 (OReilly)
• Foundations of Computer Science - Ch 8 - The Relational Model

80