Relational Database Model

The relational model (E. F. Codd, 1970) stores all data in relations, informally tables, and manipulates them with a small algebra of operations. It is the foundation of SQL.

A relation schema R(A₁, …, Aₙ) names the attributes; a database schema is a set of relation schemas with constraints; a schema diagram draws each table with its primary key underlined and arrows from foreign keys to the keys they reference.

Properties of a relation: rows are unordered and distinct; columns are unordered; each value is atomic (single-valued) in a first-normal-form table; NULL means unknown or not applicable (it is not zero or blank).

Every candidate key is a super key; the reverse is false. A table with n attributes where only one attribute is a key has 2^{n-1} super keys.

3.3 Integrity constraints

• Domain constraint: values come from the attribute's domain (type, range, CHECK).
• Entity integrity: no part of a primary key may be NULL.
• Referential integrity: a foreign key value must match an existing primary key value, or be NULL. Student (4, Gita, NULL) is legal; inserting dept_id 99 is not. On delete or update of the referenced row the DBMS can RESTRICT, CASCADE, SET NULL or SET DEFAULT.
• Key and unique constraints, and semantic (business) constraints via triggers or assertions.

3.4 Relational algebra

A procedural query language: operators take relations and return relations, so they compose.

Operator	Symbol	Meaning
Select	σ_condition(R)	rows satisfying the condition
Project	π_attrs(R)	chosen columns (duplicates removed)
Union	R ∪ S	rows in either (union-compatible)
Set difference	R − S	rows in R not in S
Intersection	R ∩ S	rows in both = R − (R − S)
Cartesian product	R × S	every row of R with every row of S;
Rename	ρ	rename relation or attributes
Natural join	R ⋈ S	product, keep rows equal on common attributes, drop the duplicate column
Theta/equi join	R ⋈_θ S	product followed by selection θ
Outer joins	⟕ ⟖ ⟗	like join, but keep unmatched rows of left / right / both, padded with NULL
Division	R ÷ S	values related to all tuples of S ("students who took every course")

Select, project, union, difference, product and rename are the fundamental operators; the rest are derived.

Expressing a query: "names of students enrolled in C1" = π_name(Student ⋈ σ_cid='C1'(Enrollment)) → Sita, Ram. Push selections down before joins to make the intermediate result small; this is the idea behind query optimisation (Unit 8).

3.5 Seeing the ideas: tables, keys and queries

The relational model is a mathematical idea that became a product. Edgar F. Codd described it in 1970 in the IBM paper "A Relational Model of Data for Large Shared Data Banks" and won the Turing Award for it in 1981.

Michael Stonebraker then helped turn the idea into working systems, first Ingres and later Postgres at the University of California, Berkeley; Postgres is the ancestor of the PostgreSQL system that is used all over the world today, and Stonebraker received the Turing Award in 2014.

(a) Michael Stonebraker

(b) Anatomy of the Student relation

A key is a promise about the whole world, not a fact read from a handful of rows.

The first plate shows why, using a sample of six students and a brute-force search over every set of attributes; the second uses a real PostgreSQL run to count the rows that come out of each relational-algebra operator.

(a) Specimen of the Nepal National Identity Card

(b) Superkey search over all 63 attribute subsets

(a) Vehicle number plate in Devanagari

(b) Cardinality of each operator (real run)

3.5.1 Eight advantages of the relational model

1. It is simple. Everything is a table of rows and columns, a picture that a school student already understands. A Nepali college clerk can read a Student table without any training in computer science. This simplicity is a main reason why the model replaced older tree and network models.
2. It has a strong mathematical base. Relations are sets, and relational algebra and calculus give exact rules for what a query means. Because of this, two different-looking queries can be proved equal, and an optimiser can rewrite them safely. Reliable behaviour comes from this foundation.
3. Data independence is high. Programs name tables and columns and never follow physical pointers. The DBA can add an index or move files and no application needs to change. This saves large amounts of maintenance work.
4. It uses a declarative language. In SQL you say what you want, such as the names of students above 80 marks, and the system decides how to get it. You do not write loops over files. A short query replaces a long program.
5. Integrity is built in. Primary keys, foreign keys, NOT NULL and CHECK rules are declared once with the table. The DBMS rejects a Student row that points to a missing department. Clean data results without extra code in every program.
6. Relationships are flexible. Tables are linked by matching values, so new links can be made at query time, for example joining Student with Enrollment by sid. No one has to plan every path in advance, as in network databases. Ad-hoc questions from managers can be answered at once.
7. Normalisation gives sound design. Theory of functional dependencies tells us how to split tables to remove redundancy and update anomalies (Unit 4). A bank can store each customer once and link accounts to the customer. Storage is saved and updates stay consistent.
8. A huge ecosystem exists. MySQL, PostgreSQL, Oracle, SQL Server and SQLite all follow the same model and mostly the same SQL. Skills learned in this course apply to a bank, to a government portal and to a mobile app. Tools for backup, reporting and security are plentiful.

Formula and fact sheet

• Candidate key = minimal super key; primary key chosen from candidates; foreign key references a primary key.
• Entity integrity: PK ≠ NULL. Referential integrity: FK matches a PK or is NULL.
• |R × S| = |R|·|S|. Natural join = product + equality on common attributes + project.
• Fundamental operators: σ, π, ∪, −, ×, ρ.

Chapter summary

• A relation is a set of unique tuples over atomic domains; keys identify tuples and link tables.
• Integrity rules keep data valid across tables.
• Relational algebra composes select, project, product, set operations and joins to express any query; outer joins preserve unmatched rows.

Practice

1. Define relation, tuple, attribute, degree, cardinality, domain.
2. Differentiate super, candidate, primary and foreign keys with Student(sid, email, name).
3. State entity and referential integrity; give a violation of each.
4. Using the sample data, evaluate π_dept_name(Department ⋈ Student) and Department − π_dept_id(Student) (rename as needed).
5. Write relational algebra for "names of students who scored below 70 in any course".
6. What is the difference between ⋈ and ×?
7. What does a left outer join give that a natural join does not?
8. How many super keys does R(A, B, C) have if A is the only candidate key?

Answers and worked solutions

1. Relation: a set of tuples over a schema; tuple: a row; attribute: a column; degree: number of columns; cardinality: number of rows; domain: set of legal values.

2. Super: {sid}, {email}, {sid, name}, … Candidate: {sid}, {email}. Primary: say {sid}. Foreign key: an attribute of another table that refers to Student.sid.

3. Entity: PK not NULL (inserting a row with sid = NULL violates it). Referential: FK matches an existing PK (a student with dept_id 99 when no such department exists).

4. Department ⋈ Student → BCA, BCA, BIT, so π_dept_name = {BCA, BIT}. Department − π_dept_id(Student) = departments with no students (compare on dept_id) = (30, BBS).

5. π_name(Student ⋈ σ_marks<70(Enrollment)) → Ram (64).

6. × pairs every row with every row; ⋈ keeps only pairs that agree on the common attributes and removes the duplicate column.

7. The rows of the left relation with no match, padded with NULLs (Gita).

8. Any attribute set containing A: 2² = 4 ({A}, {A,B}, {A,C}, {A,B,C}).

Model answers (5 and 10 marks)

Q1 (5 marks). Explain the different types of keys in the relational model with examples.

Introduction. A key is an attribute or set of attributes that identifies tuples. Keys make the relational model work because rows have no order and cannot be found by position. Figure 3.1 shows how the types are related, using Student(sid, name, email, dept_id).

1. Super key. Any set of attributes that identifies a tuple uniquely. {sid}, {email}, {sid, name} and {sid, name, dept_id} are all super keys; some contain unnecessary attributes.
2. Candidate key. A minimal super key, one from which no attribute can be removed. Here {sid} and {email} are candidate keys, but {sid, name} is not because name can be dropped.
3. Primary key. The candidate key chosen by the designer to identify tuples. It can never be NULL and should not change, so sid is a good choice.
4. Alternate key. A candidate key that was not chosen, here email. It is usually declared UNIQUE.
5. Composite key. A key made of more than one attribute. In Enrollment(sid, cid, marks) the pair (sid, cid) is the primary key because one student can take many courses and one course has many students.
6. Foreign key. An attribute of one table that refers to the primary key of another, such as dept_id in Student referring to Department. It creates the link between tables and enforces referential integrity.

Conclusion. A table has many super keys and candidate keys, one primary key and as many foreign keys as it has links to other tables.

Q2 (5 marks). What are integrity constraints? Explain the types with examples.

Introduction. Integrity constraints are rules declared in the schema that the DBMS checks on every insert, update and delete. They keep the data correct and consistent without relying on every programmer. Figure 3.2 gives a sample schema.

1. Domain constraint. Each value must belong to the domain of its column: a data type plus rules such as CHECK (marks BETWEEN 0 AND 100). A mark of 150 is rejected.
2. Key constraint. The values of a candidate key must be unique. Two students cannot have the same sid.
3. Entity integrity. No attribute of a primary key may be NULL, because a row that cannot be identified is not a real entity. Enrollment cannot have a row with sid NULL.
4. Referential integrity. A foreign key value must be NULL or must match an existing primary key value. Enrollment(9, C1, 70) is rejected when student 9 does not exist, but Student(4, Gita, NULL) is allowed because NULL means no department yet.
5. NOT NULL and UNIQUE. These force a value to be present or different from all others, for example for a phone number.
6. Actions on delete and update. When a referenced row is deleted the designer chooses RESTRICT (refuse), CASCADE (delete dependent rows) or SET NULL.

Example. Deleting department 10 with ON DELETE RESTRICT fails while Sita and Ram still belong to it.

Conclusion. Declared constraints guard the database at one central place, so wrong data is stopped before it enters.

Q3 (10 marks). Explain the operators of relational algebra with examples. Use Student(sid, name, dept_id): (1, Sita, 10), (2, Ram, 10), (3, Hari, 20), (4, Gita, NULL); Department(dept_id, dept_name): (10, BCA), (20, BIT), (30, BBS); Enrollment(sid, cid, marks): (1, C1, 85), (1, C2, 72), (2, C1, 64), (3, C2, 91).

Introduction. Relational algebra is a procedural query language whose operators take one or two relations and return a relation, so operators can be nested. It is the theory that SQL is built on and that the optimiser (Figure 3.4) uses to rewrite queries.

Fundamental operators.

1. Select, σ. Chooses rows. σ_dept_id=10(Student) gives (1, Sita, 10) and (2, Ram, 10).
2. Project, π. Chooses columns and removes duplicates. π_name(Student) gives Sita, Ram, Hari, Gita.
3. Union, ∪. Rows in either relation; the relations must be union-compatible, with the same number and types of attributes.
4. Set difference, −. Rows in the first but not the second. π_sid(Student) − π_sid(Enrollment) gives {4}: Gita has no enrolment.
5. Cartesian product, ×. Every row of one with every row of the other. Student × Department has 4 × 3 = 12 rows.
6. Rename, ρ. Gives a new name to a relation or attribute, which is necessary for self-joins.

Derived operators.

7. Intersection R ∩ S = R − (R − S).
8. Natural join, ⋈. A product followed by selection on equal common attributes with the duplicate column removed. Student ⋈ Department gives three rows (Figure 3.3); Gita and BBS disappear.
9. Outer joins. The left outer join also keeps (4, Gita, NULL, NULL); the full outer join keeps BBS as well, with NULLs.
10. Division, ÷. Finds values related to all rows of another relation: π_sid,cid(Enrollment) ÷ {C1, C2} gives sid 1, because only Sita took both courses.

Combined query. The names of students scoring above 80 are π_name(σ_marks>80(Student ⋈ Enrollment)) = Sita (85) and Hari (91).

Operator	Symbol	Result for the sample data
Select	σ	2 rows
Project	π	4 names
Natural join	⋈	3 rows
Product	×	12 rows
Division	÷	sid 1

Conclusion. Six fundamental operators are enough to express any relational query, and the derived operators make queries shorter. Pushing selections before joins gives the same answer with less work.