3. Relational Model and Formal Query Foundations

Introduction and Context

The relational model is the most influential formal model for organizing data in database systems. It provides a simple but powerful representation: data is arranged in relations, commonly displayed as tables, and relationships among facts are expressed through shared values rather than through physical pointers. Its importance extends beyond SQL. Relational concepts provide the theoretical basis for database design, query processing, integrity enforcement, normalization, and much of modern data analytics.

A data scientist works with tables constantly, but effective work requires more than knowing how to write a query. It requires understanding what a relation means, when two relations can be combined, why duplicate rows are treated differently in relational theory and SQL, how constraints protect meaning, and how a query can be expressed independently of a particular software product. Relational algebra and relational calculus provide these formal foundations.

This chapter develops the relational model from its vocabulary and structural rules to formal query operations. It also examines keys and integrity constraints, set-based reasoning, practical query formulation, and the implications of the model for data quality, governance, and analytical systems.

Learning Objectives

After studying this chapter, you should be able to:

1. Explain relations, tuples, attributes, domains, schemas, and database states.

2. Distinguish candidate, primary, alternate, foreign, and composite keys.

3. Apply entity, referential, and domain integrity constraints.

4. Use relational algebra operations to formulate and interpret queries.

5. Explain the difference between relational algebra and relational calculus.

6. Translate common information requirements into set-based expressions.

7. Identify common errors involving nulls, duplicates, joins, and constraints.

8. Evaluate the professional and governance implications of formal data representation.

The Relational View of Data

A relation is a named set of tuples that share the same attributes. In an informal database discussion, a relation is usually called a table, a tuple a row, and an attribute a column. The formal terminology is useful because it emphasizes meaning rather than presentation.

Consider the following relation:

`STUDENT(StudentID, Name, Programme, YearOfStudy)`

Its relation schema specifies the relation name and its attributes. A particular collection of student records is a relation instance, or database state, at a given time. The schema changes relatively infrequently; the instance changes whenever students are added, updated, or removed.

An attribute has a domain: the set of permitted values for that attribute. For example, `YearOfStudy` may have the domain `{1, 2, 3, 4}`, while `StudentID` may consist of strings matching an institutional identification pattern. A domain is more than a data type. It captures the semantic category of values and can include range, format, and business restrictions.

A tuple is an ordered collection of attribute values. In a logically well-designed relation, each tuple represents one fact or one instance of the relation’s subject. For example, one tuple in `STUDENT` represents the facts associated with one student. The relation should not contain two indistinguishable tuples. Thus, the classical relational model is based on set semantics: order of rows is irrelevant and duplicate tuples are not permitted.

The degree of a relation is the number of attributes in its schema. The cardinality is the number of tuples in a particular instance. These terms should not be confused with primary-key cardinality or the cardinality of a relationship in conceptual modelling.

Schemas, Instances, and Meaning

A database schema defines the structure of relations and the constraints that govern them. A database instance is a valid collection of relation instances at a specific time. A database management system should ensure that every permitted state satisfies the declared integrity constraints.

The relational model also embodies a principle of data independence. Users describe what information they need rather than how records are physically located. Indexes, partitions, storage pages, and execution plans may change without changing the logical relation schema or the meaning of a valid query.

Relations should represent coherent subjects. For example, a relation that combines student, course, lecturer, and payment details in one wide table may produce redundancy and update anomalies. Relations designed around well-defined facts are easier to constrain, query, and maintain. Normalization, discussed elsewhere in database study, uses dependencies and keys to refine this design.

Keys and Integrity Constraints

A key is an attribute or set of attributes used to identify tuples or connect relations. Keys are central to both data quality and query correctness.

A superkey is any attribute set that uniquely identifies tuples in a relation. A candidate key is a minimal superkey: no attribute can be removed while preserving uniqueness. A relation may have several candidate keys. One is selected as the primary key, while the remaining candidate keys are alternate keys. A composite key contains more than one attribute.

For example, in `ENROLMENT(StudentID, CourseID, Semester, Grade)`, the combination `(StudentID, CourseID, Semester)` may be a candidate key. Neither `StudentID` nor `CourseID` alone identifies one enrolment. A surrogate key, such as `EnrolmentID`, is an artificially assigned identifier. Surrogates can simplify references, but they do not eliminate the need to enforce business uniqueness where it exists.

A foreign key is an attribute or attribute set in one relation whose values correspond to a candidate or primary key in another relation. In `ENROLMENT`, `StudentID` can reference `STUDENT(StudentID)` and `CourseID` can reference `COURSE(CourseID)`. Foreign keys express connections and support referential integrity.

Three major forms of integrity are especially important:

• Domain integrity: Each attribute value must belong to its declared domain and satisfy applicable checks.
• Entity integrity: A primary-key value cannot be null, and primary-key values must be unique.
• Referential integrity: A non-null foreign-key value must match a referenced key value, unless the design explicitly permits an appropriate null relationship.

Additional constraints include `UNIQUE`, `CHECK`, assertions, functional dependencies, and business rules enforced through procedures or application logic. A rule such as “a course cannot have more than 60 enrolled students” may require a mechanism beyond a simple domain constraint.

Constraints are declarative statements of acceptable states. They should be defined as close as possible to the data so that all applications receive consistent protection. Relying solely on interface validation is risky because data may also arrive through batch jobs, APIs, scripts, or integration pipelines.

Set-Based Reasoning and Relational Algebra

Relational algebra is a procedural formal query language. It provides a collection of operations that take relations as input and produce relations as output. Because the result of every operation is itself a relation, operations can be composed into expressions. This property is called closure.

Relational algebra is not normally used directly by end users, but database optimizers use equivalent algebraic transformations when constructing execution plans. It also gives students a precise way to reason about query meaning.

Selection

Selection chooses tuples satisfying a predicate. It is written:

`σ condition (R)`

For example:

`σ YearOfStudy = 1 (STUDENT)`

returns first-year students. Selection filters rows without changing the attributes of the relation. Several conditions may be combined using logical operators such as AND, OR, and NOT.

Projection

Projection chooses attributes:

`π StudentID, Name (STUDENT)`

It returns only the selected columns. Under classical set semantics, duplicate resulting tuples are removed. This differs from SQL, where `SELECT` retains duplicates unless `DISTINCT` is specified.

Selection and projection are often combined. To obtain the names of first-year students:

`π Name (σ YearOfStudy = 1 (STUDENT))`

The order of operations can affect results. Projecting away an attribute before using it in a selection makes that selection impossible. In some circumstances, however, selection can be pushed closer to the base relation without changing the result; this is an important optimization principle.

Union, Intersection, and Difference

Union combines tuples from two union-compatible relations:

`R ∪ S`

The relations must have the same number of attributes, with corresponding attributes drawn from compatible domains. Intersection returns tuples common to both relations:

`R ∩ S`

Difference returns tuples in the first relation but not the second:

`R − S`

For example, if `ACTIVE_STUDENT` and `SCHOLARSHIP_STUDENT` have identical schemas, `ACTIVE_STUDENT ∩ SCHOLARSHIP_STUDENT` identifies students in both sets. Difference can identify students who are active but do not receive scholarships.

Cartesian Product

The Cartesian product combines every tuple of one relation with every tuple of another:

`R × S`

If R has m tuples and S has n tuples, the product has m × n tuples before filtering. It is rarely the desired final result, but it forms the conceptual basis of a join.

Joins

A join combines related tuples according to a condition. A theta join is written:

`R ⋈ condition S`

An equijoin uses equality, such as matching `STUDENT.StudentID` with `ENROLMENT.StudentID`. A natural join matches attributes with the same names and removes one duplicate copy of the joining attribute. Natural joins are concise but can be dangerous when identical attribute names have different meanings or when a later schema change introduces an unintended matching column.

An ordinary inner join returns only matching tuples. An outer join preserves unmatched tuples. A left outer join retains every tuple from the left relation and fills unavailable right-side attributes with null markers. Right and full outer joins provide analogous behaviour.

A semijoin returns tuples from one relation for which a match exists in another. An antijoin returns tuples for which no match exists. These concepts are useful in distributed query processing and in expressing questions such as “Which students have at least one enrolment?” or “Which courses have no enrolments?”

Division

Division expresses a “for all” condition. If `COMPLETED(StudentID, CourseID)` records completed courses and `REQUIRED(CourseID)` records all required courses, then:

`COMPLETED ÷ REQUIRED`

returns students who completed every required course. Division is conceptually important because ordinary joins naturally express “there exists a matching value,” whereas division expresses universal qualification. In SQL, division is often implemented using nested `NOT EXISTS` conditions or grouped counting.

Aggregation and Extended Algebra

Classical relational algebra does not include aggregate functions such as count, sum, average, minimum, and maximum. Extended relational algebra adds grouping and aggregation. For example, grouping enrolments by `CourseID` and counting tuples can identify course demand. Aggregates require careful interpretation: an average grade over students is not necessarily the same as an average over enrolment records if students have different numbers of enrolments.

Relational Calculus: Describing What Is Wanted

Relational calculus is a non-procedural formalism. Instead of specifying a sequence of operations, it describes the properties that qualifying tuples must satisfy. It therefore focuses on what the answer is rather than how to compute it.

Tuple relational calculus uses tuple variables. A query may be expressed conceptually as: “Return each student tuple for which there exists an enrolment tuple with the same StudentID and CourseID equal to `DS501`.” Domain relational calculus uses variables representing individual attribute values rather than complete tuples.

Relational calculus depends on safe expressions. A safe query returns a finite result whose values are drawn appropriately from the database and specified constants. Without safety restrictions, a formal expression could describe an unbounded or meaningless set.

SQL is not identical to relational calculus, but its declarative style is closely related. SQL allows users to state required results while the optimizer selects an execution strategy. This separation supports portability of intent, although SQL’s null semantics, duplicate preservation, grouping rules, and implementation-specific features mean that it is not a pure classical relational language.

Relational algebra and calculus are equivalent in expressive power for the core relational operations. This means that a query stated procedurally in algebra can, under suitable conditions, be stated declaratively in calculus. The distinction remains valuable: algebra supports operational reasoning and optimization, while calculus supports specification and logical interpretation.

Translating Information Needs into Formal Queries

A reliable query-development process begins with the business question, not with a preferred SQL syntax. First identify the subject of the result and its required attributes. Next identify the relations containing those attributes, determine how they are connected, and state the filtering conditions. Finally consider whether the question involves existence, non-existence, counting, or a universal condition.

Suppose the requirement is: “List the names of students enrolled in a course offered by the Data Science department.” A formal reasoning path is:

1. Start with `STUDENT` and `ENROLMENT`.

2. Join them on `StudentID`.

3. Join `ENROLMENT` with `COURSE` on `CourseID`.

4. Select courses whose department is `Data Science`.

5. Project student names.

A corresponding algebraic expression is:

`π Name (σ Department = 'Data Science' (STUDENT ⋈ ENROLMENT ⋈ COURSE))`

The exact expression may require qualified attributes and explicit join conditions, but the reasoning is the essential point. If the requirement instead asks for students with no enrolment, an ordinary join is insufficient; an antijoin or set difference is more appropriate.

Ambiguity must also be addressed. “Students who passed every required course” is different from “students who passed at least one required course.” The former requires division-like reasoning. “Number of students enrolled” requires deciding whether duplicate enrolment records are possible and whether the count should be over students or enrolments.

An Illustrative Case: University Enrolment Analytics

Background

Consider an illustrative university database containing the relations:

`STUDENT(StudentID, Name, Programme, Status)`

`COURSE(CourseID, Title, Department, Credits)`

`ENROLMENT(StudentID, CourseID, Semester, Grade)`

`REQUIRED(Programme, CourseID)`

Primary keys are `StudentID`, `CourseID`, `(StudentID, CourseID, Semester)`, and `(Programme, CourseID)` respectively. Foreign keys connect enrolments to students and courses, and required courses to programmes and courses.

Situation and Problem

The academic planning office wants to identify active students who have not completed all courses required for their programme. A simple report listing students with low grades is inadequate because it does not account for the set of courses required by each programme. The question is relational: for each student, compare the set of passed courses with the set of required courses for that student’s programme.

Analysis

First, define passed enrolments using a selection such as `Grade` meeting the institution’s passing rule. Next connect students to required courses through their programme. The completed set can be compared with the required set. Students for whom at least one required course is absent can be found through an antijoin or through a double-negation query: identify students for whom there exists a required course for which no passing enrolment exists.

This analysis also exposes important data-quality issues. A missing grade may mean that assessment is pending rather than failed. A repeated course may produce several enrolment tuples, so the query must distinguish attempts from successful completion. Programme requirements may change by academic year, requiring a version or effective-date attribute.

Approach and Solution

A robust implementation would:

• enforce foreign keys for students, courses, and programme requirements;
• define a documented passing-grade rule;
• use existence tests rather than relying on row counts when duplicate attempts are possible;
• preserve programme and curriculum versions;
• provide an exception report for missing or contradictory data.

Conceptually, the result is obtained by taking each active student and subtracting the required courses for which a passing enrolment exists. If the remaining set is non-empty, the student has outstanding requirements. A division formulation is suitable when the question is reversed: students whose passed-course set contains every required course.

Outcome

The resulting report supports academic advising without confusing “no record,” “not yet graded,” and “failed.” It also provides an auditable basis for decisions because each outstanding course can be traced to a requirement and the absence of a qualifying completion record.

Learning Points

The case demonstrates that relational queries are statements about sets, not merely commands for retrieving rows. Keys establish identity, foreign keys establish valid connections, selections define predicates, joins connect facts, and division or nested non-existence expresses “all” conditions. A formally correct query still depends on clear business definitions and trustworthy constraints.

Professional Practice, Risks, and Limitations

A common mistake is joining tables without identifying the relationship cardinality. Joining a student table to a transaction table can multiply student rows, so a report requiring one row per student may need projection with duplicate elimination, grouping, or an existence predicate. Another mistake is using a natural join without examining common attribute names.

Null values require special care. In classical relational theory, a relation contains values from declared domains. SQL introduces null markers to represent missing, unknown, or inapplicable information. Comparisons involving null generally evaluate to unknown rather than true or false, and this affects filtering, joins, and `NOT IN` queries. `NOT EXISTS` is often safer than `NOT IN` when nullable values are possible, although the correct choice depends on the intended semantics.

Set and bag semantics also differ. SQL commonly preserves duplicates, while relational algebra assumes sets. Consequently, an SQL projection may return repeated rows unless `DISTINCT` is requested. Aggregates, joins, and union operations must be interpreted with this difference in mind.

Poorly constrained databases can produce orphan records, duplicate entities, inconsistent codes, and misleading analytics. Conversely, excessive constraints may obstruct legitimate historical corrections or integration with external systems. Constraint design should therefore reflect documented business rules, ownership, exception procedures, and data-retention requirements.

From a governance perspective, the relational model supports accountability because relationships and constraints can make data provenance more explicit. Access controls should follow least privilege. Sensitive attributes should be minimized, masked, or pseudonymized where appropriate. A logically elegant query can still violate privacy if it exposes personally identifiable information beyond a legitimate purpose.

Technology and Emerging Practice

Modern relational database systems use query optimizers to transform declarative SQL into algebraically equivalent execution plans. Selection pushdown, projection pruning, join reordering, indexing, partitioning, and parallel execution can substantially improve performance. These transformations are valid only when they preserve query semantics, including null and duplicate behaviour.

Relational systems increasingly support JSON, graph-like features, temporal tables, geospatial types, machine-learning extensions, and cloud-native scaling. These developments expand the model’s practical reach but do not remove the need for relational discipline. Semi-structured extensions still benefit from keys, domains, constraints, and explicit relationship reasoning.

Data warehouses and lakehouse platforms frequently expose relational query interfaces over distributed storage. Query engines may use columnar formats, vectorized execution, caching, and approximate algorithms. At the conceptual level, however, the analyst still needs to distinguish a relation’s grain, determine whether joins are one-to-one or one-to-many, and validate the meaning of aggregates.

Best Practices for Relational Query Design

1. Define the grain of every relation and every report before writing a query.

2. Identify candidate keys and enforce the selected primary key.

3. Declare foreign keys and document permitted optional relationships.

4. Use explicit join conditions and qualified attribute names.

5. Treat “all,” “none,” and “at least one” as distinct logical requirements.

6. Check whether duplicate rows are meaningful or accidental.

7. Test queries with empty relations, unmatched rows, nulls, duplicate attempts, and boundary values.

8. Validate aggregate results against independently calculated samples.

9. Keep business definitions, domain rules, and temporal assumptions documented.

10. Protect sensitive data through access controls, minimization, and auditable use.

Chapter Summary

The relational model represents data as relations composed of tuples and attributes drawn from domains. Relation schemas describe structure, while relation instances represent database states. Keys identify tuples and connect relations; domain, entity, and referential integrity constraints protect validity.

Relational algebra supplies composable operations including selection, projection, set operations, products, joins, outer joins, semijoins, antijoins, and division. Relational calculus expresses the properties that qualifying results must satisfy and provides a declarative foundation related to SQL. Set-based reasoning is essential for distinguishing existence, non-existence, counting, and universal conditions.

Professional use of the model requires attention to grain, duplicates, nulls, join cardinality, constraints, privacy, and temporal meaning. Modern optimizers and distributed platforms may change execution methods, but they depend on the same logical foundations. Correct database work therefore combines formal reasoning with accurate business interpretation and responsible governance.

Key Terms

Relation: A named set of tuples sharing a common schema.

Tuple: A single ordered record in a relation.

Attribute: A named property or column of a relation.

Domain: The permitted set or semantic category of values for an attribute.

Relation schema: The name and attribute structure of a relation.

Relation instance: The tuples present in a relation at a particular time.

Degree: The number of attributes in a relation.

Cardinality: The number of tuples in a relation instance.

Superkey: An attribute set that uniquely identifies tuples.

Candidate key: A minimal superkey.

Primary key: The candidate key selected as the principal tuple identifier.

Foreign key: An attribute set referencing a key in another relation.

Entity integrity: The requirement that primary keys be unique and non-null.

Referential integrity: The requirement that valid foreign-key values match referenced keys.

Selection: A relational algebra operation that filters tuples by a predicate.

Projection: A relational algebra operation that selects attributes.

Join: An operation combining tuples from relations according to a matching condition.

Relational algebra: A procedural, closed set of operations over relations.

Relational calculus: A non-procedural formal language specifying qualifying tuples or values.

Division: An operation expressing a “for every” or universal condition.

Review Questions

Short Answer Questions

1. Distinguish a relation schema from a relation instance.

2. Why is a candidate key described as minimal?

3. State the difference between domain integrity and referential integrity.

4. What is the purpose of selection in relational algebra?

5. Why can a natural join produce unintended results?

Long Answer Questions

1. Explain the relational model’s main concepts and show how they support data independence.

2. Discuss primary, candidate, alternate, composite, surrogate, and foreign keys using an enrolment example.

3. Describe relational algebra operations and explain how they can be composed into a query.

4. Compare relational algebra and relational calculus in terms of procedure, specification, and database optimization.

5. Explain how nulls, duplicate rows, and join cardinality can affect SQL interpretations of relational queries.

Analytical / Application Questions

1. Design a relational-algebra solution for finding active students who have no enrolment in any course. Explain why an antijoin or set difference is appropriate.

2. A report counts enrolment rows to estimate the number of students in each course. Analyse when this produces an incorrect result and propose a corrected set-based approach.

3. Using the university case, formulate a logical strategy for identifying students who have completed every required course while distinguishing failed, pending, and missing results.

22. Multiple Choice Questions with Answers

Question 1

Which statement best distinguishes a relation schema from a relation instance?

A. A schema contains physical storage pages, while an instance contains indexes

B. A schema defines structure, while an instance contains tuples at a particular time

C. A schema contains only primary keys, while an instance contains foreign keys

D. A schema is a query result, while an instance is a database constraint

Correct Answer: B. A schema defines structure, while an instance contains tuples at a particular time

Question 2

In ENROLMENT(StudentID, CourseID, Semester, Grade), why might (StudentID, CourseID, Semester) be a composite candidate key?

A. Because each individual attribute is always unique

B. Because the combination uniquely identifies an enrolment and no smaller combination does

C. Because composite keys cannot contain foreign keys

D. Because candidate keys must contain exactly three attributes

Correct Answer: B. Because the combination uniquely identifies an enrolment and no smaller combination does

Question 3

Which relational algebra operation returns only tuples satisfying a predicate?

A. Projection

B. Selection

C. Division

D. Cartesian product

Correct Answer: B. Selection

Question 4

What is the principal risk of using a natural join without examining the schemas?

A. It always removes all unmatched tuples

B. It can join on same-named attributes that are not intended relationship attributes

C. It cannot combine relations with foreign keys

D. It necessarily produces a Cartesian product

Correct Answer: B. It can join on same-named attributes that are not intended relationship attributes

Question 5

Which operation is most directly associated with expressing a universal condition such as 'students who completed every required course'?

A. Division

B. Selection

C. Union

D. Projection

Correct Answer: A. Division

Question 6

A left outer join is preferred over an inner join when the requirement is to:

A. Return only records having matches in both relations

B. Preserve every tuple from the left relation, including unmatched tuples

C. Remove all null values from the result

D. Guarantee that the right relation has a primary key

Correct Answer: B. Preserve every tuple from the left relation, including unmatched tuples

Question 7

Which constraint prevents a non-null foreign-key value from referring to a nonexistent parent tuple?

A. Domain integrity

B. Entity integrity

C. Referential integrity

D. Projection integrity

Correct Answer: C. Referential integrity

Question 8

Why can counting enrolment rows overestimate the number of students in a course?

A. A course can have no attributes

B. The same student may have multiple enrolment attempts or records

C. Foreign keys automatically duplicate course identifiers

D. Selection always counts columns rather than rows

Correct Answer: B. The same student may have multiple enrolment attempts or records

Question 9

Which statement correctly characterizes relational calculus?

A. It specifies the desired properties of result tuples rather than an operational sequence

B. It is limited to physical page addresses

C. It requires users to select indexes manually

D. It permits only Cartesian products

Correct Answer: A. It specifies the desired properties of result tuples rather than an operational sequence

Question 10

Why is NOT EXISTS often useful for finding students with no qualifying enrolment?

A. It expresses a non-existence condition without requiring unmatched rows to be fabricated

B. It automatically ignores all integrity constraints

C. It converts every relation into a set of unique columns

D. It guarantees that nulls are treated as passing grades

Correct Answer: A. It expresses a non-existence condition without requiring unmatched rows to be fabricated