Relational Theory and Data Integrity

Introduction

Relational databases are built on a mathematical model that represents information as relations and governs how those relations may be combined, constrained, and queried. MySQL and PostgreSQL are practical database management systems, but effective use of either requires more than knowledge of SQL syntax. Developers must understand what makes a row identifiable, how relationships are enforced, why duplicate rows and NULL values require special treatment, and how constraints protect data from contradictory states.

Relational theory provides a precise vocabulary for database design. It also supplies the foundation for normalization, query optimization, transaction processing, and reliable application development. Data integrity is the practical expression of this theory: stored data should be accurate, consistent, valid, and appropriately related to other data.

Learning Objectives

By the end of this chapter, you should be able to:

• distinguish relations, tuples, attributes, domains, schemas, and instances;
• identify superkeys, candidate keys, primary keys, and foreign keys;
• explain entity, referential, domain, and user-defined integrity;
• apply SQL constraints in MySQL and PostgreSQL;
• use relational algebra and relational calculus to reason about queries;
• distinguish set semantics from SQL’s practical bag semantics;
• explain NULL and three-valued logic;
• analyze a database design for correctness and integrity risks.

1. The Relational Model

1.1 Relations, tuples, and attributes

A relation is a named collection of records organized according to a relation schema. A relation schema is commonly written as:

Here, R is the relation name and A₁, A₂, …, Aₙ are attributes. Each attribute has a domain: the set of permitted values for that attribute. For example, the schema

might define StudentID as positive integers, Name as character strings, Email as strings satisfying an application rule, and DateOfBirth as calendar dates.

A tuple is one record in a relation. In a table representation, it is usually shown as a row. An attribute is a named component of a tuple and is usually shown as a column. A relation instance is the set of tuples stored at a particular time; the schema describes the structure, while the instance describes the current contents.

The degree of a relation is its number of attributes. The cardinality is its number of tuples. A relation of degree 4 and cardinality 250 has four attributes and 250 tuples. Cardinality changes as rows are inserted or deleted; degree normally changes only when the schema is altered.

The classical relational model treats a relation as a set of tuples. Consequently, duplicate tuples are not permitted, and tuple order and attribute order have no conceptual significance. SQL, however, commonly operates with bags, also called multisets, in which duplicate rows may occur unless a constraint or DISTINCT operation removes them.

1.2 Relation schemas and instances

A database schema is a collection of relation schemas together with constraints and relationships. A database instance is the complete collection of relation instances at a particular time. A valid instance satisfies every applicable constraint.

For example:

STUDENT(StudentID, Name, Email)
COURSE(CourseID, Title, Credits)
ENROLLMENT(StudentID, CourseID, EnrolledOn, Grade)

The schema indicates that ENROLLMENT connects students and courses. It does not, by itself, guarantee that referenced students and courses exist. That requirement must be expressed through foreign keys.

2. Keys and Identification

2.1 Superkeys and candidate keys

A superkey is a set of attributes that uniquely identifies each tuple in a relation. If StudentID uniquely identifies students, then both {StudentID} and {StudentID, Name} are superkeys. The second is unnecessarily large but still unique.

A candidate key is a minimal superkey. “Minimal” means that no attribute can be removed while preserving uniqueness. A relation may have several candidate keys. For STUDENT, StudentID and Email might each be candidate keys if both are non-null and unique.

A primary key is the candidate key selected as the principal identifier. Other candidate keys are alternate keys. A good primary key is stable, unique, minimal, and available whenever a row exists. Natural keys, such as a government-issued identifier, have business meaning; surrogate keys, such as generated integers or UUIDs, have little or no business meaning. Neither category is universally superior. The decision depends on stability, privacy, size, interoperability, and business rules.

A key constraint is a statement that no two tuples may agree on all attributes of a candidate key. In SQL, this is implemented through PRIMARY KEY or UNIQUE constraints. A primary key also implies NOT NULL.

2.2 Foreign keys

A foreign key is an attribute or set of attributes in one relation whose values refer to a candidate or primary key in another relation. In ENROLLMENT, StudentID is a foreign key referencing STUDENT(StudentID), and CourseID references COURSE(CourseID).

Referential integrity requires every non-null foreign-key value to match an existing referenced key value. The referencing relation is sometimes called the child, and the referenced relation the parent. A foreign key prevents orphan records such as an enrollment for a student who does not exist.

Composite keys require matching composite foreign keys. If SECTION has primary key {CourseID, SectionNo}, then an offering relation must reference both attributes, in the same logical key relationship. Referencing only CourseID would not identify a particular section.

Foreign-key actions must be selected deliberately:

CASCADE is useful for genuinely dependent data, but dangerous for records that must be retained for legal, financial, or audit reasons.

3. Integrity Constraints

Integrity constraints define valid database states. They should be enforced as close to the data as practical, normally in the database, rather than relying only on application code.

3.1 Domain integrity

Domain integrity requires values to belong to the correct domain. SQL data types provide a first layer of protection. Additional restrictions can be expressed using CHECK constraints, for example:

CREATE TABLE course (
    course_id  integer PRIMARY KEY,
    title      varchar(200) NOT NULL,
    credits    integer NOT NULL CHECK (credits BETWEEN 1 AND 6)
);

The CHECK expression must evaluate as acceptable under the DBMS’s constraint rules. Because NULL can produce UNKNOWN, a CHECK condition should be designed carefully; use NOT NULL when a value is mandatory.

PostgreSQL supports rich types, domains, enumerated types, and exclusion constraints. MySQL supports CHECK constraints in current versions, but behavior in older releases differed, so the deployed version must be verified. Portability should never be assumed merely because two systems accept similar SQL syntax.

3.2 Entity integrity

Entity integrity requires each tuple to be identifiable. A primary-key value must be unique and cannot be NULL. In PostgreSQL, a declaration such as GENERATED ALWAYS AS IDENTITY can generate numeric identifiers. MySQL commonly uses AUTO_INCREMENT. Generated identifiers solve generation, not business uniqueness; meaningful alternate keys may still need UNIQUE constraints.

3.3 Referential integrity

Referential integrity maintains valid relationships between tables. A typical definition is:

CREATE TABLE enrollment (
    student_id  integer NOT NULL,
    course_id   integer NOT NULL,
    enrolled_on date NOT NULL,
    grade       numeric(5,2),
    PRIMARY KEY (student_id, course_id),
    FOREIGN KEY (student_id) REFERENCES student(student_id),
    FOREIGN KEY (course_id) REFERENCES course(course_id),
    CHECK (grade IS NULL OR grade BETWEEN 0 AND 100)
);

The composite primary key prevents the same student from being enrolled in the same course more than once. The foreign keys prevent references to nonexistent students or courses. The CHECK constraint permits an unassigned grade but restricts assigned grades to the stated range.

3.4 Assertions and business rules

Some rules involve several rows or tables, such as “a department must always have a chair” or “a student may enroll in at most five courses per term.” Standard SQL includes assertions conceptually, but major systems do not generally implement them as a portable feature. Such rules may require triggers, indexed structures, transactions, deferred checks, or carefully designed application services.

Triggers can enforce complex rules, but they add hidden behavior and can be difficult to test. Prefer declarative constraints where possible. When procedural enforcement is necessary, document transaction boundaries, concurrency assumptions, and failure behavior.

4. Relational Algebra

Relational algebra is a procedural formal language for transforming relations. It is useful for understanding query meaning, proving equivalence, and reasoning about optimization. Basic operators include selection, projection, union, difference, Cartesian product, and various joins.

4.1 Selection

Selection chooses tuples satisfying a predicate:

For example, σ_{Credits ≥ 4}(COURSE) returns courses with at least four credits. Selection changes cardinality but not degree.

4.2 Projection

Projection chooses attributes:

For example, π_{StudentID, Email}(STUDENT) returns only those attributes. Under classical set semantics, duplicate projected tuples are eliminated. SQL requires DISTINCT if that behavior is wanted explicitly.

4.3 Union, difference, and intersection

Union combines tuples from two union-compatible relations:

R and S must have corresponding attributes with compatible domains. Difference returns tuples in R but not S:

Intersection returns tuples common to both relations and can be expressed as R ∩ S = R − (R − S). SQL expresses these operations through UNION, EXCEPT, and INTERSECT, although EXCEPT and INTERSECT support varies by product version; PostgreSQL supports both, while MySQL’s support should be checked for the deployed release.

4.4 Product and joins

The Cartesian product pairs every tuple in R with every tuple in S:

If R has m tuples and S has n tuples, the product has m × n tuples, assuming ordinary finite relations. A product is often filtered to form a join:

An equijoin uses equality, while a natural join matches same-named attributes and removes one copy of the matching attribute. Natural joins should be used cautiously because adding a same-named column can silently change their meaning. Explicit join conditions are usually safer in production SQL.

An outer join preserves unmatched tuples. A left outer join preserves every tuple from its left input and supplies NULLs for missing right-side values. This distinction is essential when reporting entities with no related records.

4.5 Relational division

Division expresses “for all” queries. If TAKEN(StudentID, CourseID) records completed courses and REQUIRED(CourseID) records required courses, then:

returns students who have taken every required course. In SQL, this is commonly implemented using double NOT EXISTS or grouping and HAVING. Division is conceptually important because universal conditions are often harder to express than existential conditions.

5. Relational Calculus

Relational calculus is declarative: it specifies what tuples should satisfy rather than the sequence of operations used to obtain them. Tuple relational calculus uses tuple variables and predicates. A simplified expression for students enrolled in a course with at least four credits is:

{ s | STUDENT(s) AND ∃e ∃c
      (ENROLLMENT(e) AND COURSE(c)
       AND e.StudentID = s.StudentID
       AND e.CourseID = c.CourseID
       AND c.Credits ≥ 4) }

The symbol ∃ means “there exists.” Universal conditions use ∀, meaning “for every.” Safe calculus expressions restrict results to values drawn from the database, so they produce finite, meaningful results. Relational algebra and safe relational calculus are equivalent in expressive power for the classical relational model. SQL is influenced by both, but includes additional features such as aggregation, ordering, NULL, recursion, and implementation-specific behavior.

6. Set Semantics, Bag Semantics, and SQL

The classical model uses sets. SQL commonly uses bags. Consider two enrollment rows that project to the same StudentID. Relational projection returns one value under set semantics, whereas:

SELECT student_id FROM enrollment;

may return repeated values. To request set-like output:

SELECT DISTINCT student_id FROM enrollment;

UNION removes duplicates by default, while UNION ALL preserves them. Duplicate preservation can be useful for performance and for queries where multiplicity has meaning, but it can also produce incorrect counts. For example, joining a customer to multiple orders and then counting joined rows may count orders rather than customers. Developers must identify the intended unit of counting and use DISTINCT, grouping, or a different query structure accordingly.

7. NULL and Three-Valued Logic

NULL does not mean zero, an empty string, false, or necessarily “unknown” in every business context. It represents an absent, inapplicable, or unknown value according to the design. Since a comparison involving NULL generally cannot be established as true or false, SQL uses three-valued logic: TRUE, FALSE, and UNKNOWN.

For example, 5 = NULL evaluates to UNKNOWN, not TRUE or FALSE. Therefore, the correct test is:

WHERE middle_name IS NULL

and not middle_name = NULL. The predicate middle_name IS NOT NULL tests presence.

In a WHERE clause, only TRUE passes; FALSE and UNKNOWN do not. This explains why a query such as:

WHERE grade <> 50

does not return rows where grade is NULL. To include them, write the intended logic explicitly:

WHERE grade <> 50 OR grade IS NULL

Important truth behavior includes:

The exact treatment of NULL in UNIQUE constraints, indexes, sorting, and grouping can vary in detail between systems. PostgreSQL and MySQL, for example, generally allow multiple NULLs in a UNIQUE constraint because NULLs are not treated as equal in ordinary uniqueness testing. PostgreSQL also provides options such as NULLS NOT DISTINCT in suitable contexts. Always consult the DBMS version documentation when a rule depends on NULL uniqueness.

NULL also affects aggregates. COUNT(*) counts rows, while COUNT(column) counts non-null values in that column. SUM, AVG, MIN, and MAX generally ignore NULL inputs and return NULL when no non-null input exists. COALESCE can replace NULL with a chosen value, but it should not be used to conceal missing information without a sound business interpretation.

8. Worked Design Example

Suppose a university needs to record students, courses, and enrollments. A poor design stores:

REGISTRATION(StudentID, StudentName, CourseID, CourseTitle, Grade)

This repeats student and course facts. Updating a course title in only some rows creates an update anomaly; deleting the last registration for a course may lose the course itself; inserting a course before any student enrolls may be impossible. These are signs that facts with different identities have been combined.

A better design is:

STUDENT(StudentID, StudentName)
COURSE(CourseID, CourseTitle)
ENROLLMENT(StudentID, CourseID, Grade)

STUDENT and COURSE each have a primary key. ENROLLMENT has a composite primary key and two foreign keys. A grade is an attribute of a student-course enrollment, not of the student alone or the course alone. This design reduces redundancy and makes dependencies explicit.

A query for students who have no enrollment can use an outer join:

SELECT s.student_id, s.student_name
FROM student AS s
LEFT JOIN enrollment AS e
  ON e.student_id = s.student_id
WHERE e.student_id IS NULL;

Alternatively, it can use the relational-calculus idea of nonexistence:

SELECT s.student_id, s.student_name
FROM student AS s
WHERE NOT EXISTS (
    SELECT 1
    FROM enrollment AS e
    WHERE e.student_id = s.student_id
);

The second form often communicates the intended logic directly and avoids accidental multiplication of rows.

9. Case Study: Integrity in an Online Learning Platform

Background

The following is an illustrative case. A learning platform stores learners, courses, course offerings, registrations, payments, and assessment results. Initially, one wide table records learner details, course details, payment status, and grades for every registration.

Problem

Support staff report duplicate registrations, payments linked to deleted courses, and inconsistent grades. A learner who changes an email address must be updated in hundreds of rows. Reports also disagree because some queries count registration rows while others count distinct learners.

Analysis

The table mixes facts with different determinants. LearnerID determines learner attributes; CourseID determines course attributes; and the pair (LearnerID, OfferingID) determines a registration. Payment status is associated with a payment transaction, while a grade is associated with a learner’s assessment attempt or registration. The existing design has update, insertion, and deletion anomalies.

Approach and solution

The platform is redesigned using separate LEARNER, COURSE, OFFERING, REGISTRATION, PAYMENT, and ASSESSMENT tables. Primary keys identify entities and transactions. Registration receives a UNIQUE constraint on (LearnerID, OfferingID) where only one active registration is allowed. Foreign keys enforce valid references. CHECK constraints restrict payment amounts to non-negative values and grades to the approved range. Historical payments are retained rather than deleted when a course is retired.

Transactions are used when registering a learner: the system checks capacity, inserts the registration, and records the payment request as one coordinated operation or uses an explicit pending state. Concurrent requests are tested because an application-level capacity check alone can allow over-enrollment.

Outcome

Duplicate active registrations are rejected by the database. Orphan payments cannot be created. Learner updates occur once, and reports specify whether they count registrations, offerings, or distinct learners. Audit requirements are supported because historical transactions are preserved.

Learning points

The case demonstrates that integrity is both a logical and operational concern. Correct tables and constraints prevent many errors, but transaction design, concurrency control, reporting semantics, and audit policy are equally important.

10. Professional Practice and Contemporary Considerations

Data integrity is a governance responsibility as well as a programming responsibility. Constraints should be reviewed during schema migration, tested with invalid data, and monitored in production. Migration scripts should establish or validate constraints before declaring a migration complete. Backup and restore procedures must preserve constraints, indexes, and encoding behavior.

Least-privilege access reduces the chance that users or services can bypass integrity rules. Sensitive identifiers should not be exposed unnecessarily, and personally identifiable information should be protected through access control, encryption, retention limits, and appropriate regulatory processes. A surrogate key does not anonymize a person; linkage through other columns may still identify them.

AI-assisted coding can generate plausible SQL but may misunderstand key cardinality, NULL semantics, or the difference between counting rows and counting entities. AI-generated schema and queries require review against functional dependencies, constraints, execution plans, security requirements, and test data. Automated tools are useful for checking consistency, not for replacing domain accountability.

Best practices include:

1. define business identity and candidate keys before choosing a primary key;
2. use NOT NULL for mandatory facts rather than relying on application validation;
3. enforce uniqueness and referential integrity in the database;
4. name constraints clearly and use explicit join predicates;
5. treat NULL as a deliberate modeling choice;
6. test inserts, updates, deletes, concurrency, and rollback behavior;
7. document foreign-key actions and retention requirements;
8. distinguish set-oriented requirements from SQL’s bag behavior;
9. review execution plans after correctness is established;
10. keep schemas, migrations, and integrity tests under version control.

Chapter Summary

The relational model represents data through relations, tuples, attributes, and domains. Keys identify tuples: superkeys guarantee uniqueness, candidate keys are minimal superkeys, and one candidate key is selected as the primary key. Foreign keys connect relations and enforce referential integrity. Domain, entity, referential, and business constraints define valid database states.

Relational algebra provides operators such as selection, projection, union, difference, product, joins, and division. Relational calculus expresses the same broad query power declaratively through predicates, existential quantifiers, and universal quantifiers. Classical relations use set semantics, whereas SQL commonly preserves duplicates as bags. NULL introduces UNKNOWN and requires three-valued logic, explicit IS NULL tests, and careful aggregate interpretation.

Reliable database design separates facts according to their identities and dependencies, places enforceable rules in declarative constraints, and uses transactions for coordinated changes. Professional practice also requires attention to concurrency, auditing, privacy, version-specific DBMS behavior, and critical review of AI-generated SQL.

Key Terms

Relation: A named collection of tuples defined by a relation schema.

Tuple: A single record or row in a relation.

Attribute: A named component or column of a tuple.

Domain: The set of permitted values for an attribute.

Relation schema: The structural definition 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.

Superkey: An attribute set that uniquely identifies tuples.

Candidate key: A minimal superkey.

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

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

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

Referential integrity: The requirement that non-null foreign-key values reference existing keys.

Selection: A relational-algebra operation that filters tuples.

Projection: A relational-algebra operation that chooses attributes.

Relational calculus: A declarative formal query language based on predicates.

Bag semantics: A model in which duplicate rows may occur.

NULL: A marker for an absent, inapplicable, or unknown value.

Three-valued logic: Logic using TRUE, FALSE, and UNKNOWN.

Review Questions

Short Answer Questions

1. What is the difference between a relation schema and a relation instance?
2. Why is every candidate key a superkey, but not every superkey a candidate key?
3. What problem does a foreign key prevent?
4. Why does column = NULL not correctly test for missing values in SQL?
5. How do COUNT(*) and COUNT(column) differ when NULL values are present?

Long Answer Questions

1. Explain primary keys, alternate keys, surrogate keys, and natural keys, including advantages and risks of each.
2. Describe the principal relational-algebra operators and relate them to SQL operations.
3. Explain entity, domain, referential, and business integrity, giving an example of each.
4. Compare set semantics and bag semantics and analyze their effect on projection, UNION, joins, and counting.
5. Explain SQL’s three-valued logic and show how it affects WHERE predicates, CHECK constraints, and aggregates.

Analytical / Application Questions

1. Design tables and constraints for a library in which a member may borrow a book copy, each copy belongs to one title, and a copy cannot be simultaneously loaned to two members. Justify every key and constraint.
2. A report joins CUSTOMER, ORDER, and ORDER_ITEM and reports too many customers. Diagnose the likely bag-semantics problem and propose two logically correct query strategies.
3. A university wants to delete a course while retaining historical registrations and grades. Select appropriate foreign-key behavior and explain how your choice supports auditability and data integrity.

Multiple Choice Questions with Answers

Question 1

Which property distinguishes a candidate key from a superkey?

A. A candidate key is minimal.

B. A candidate key may contain duplicate values.

C. A candidate key must contain a foreign key.

D. A candidate key may be NULL for some tuples.

Correct Answer: A. A candidate key is minimal.

Question 2

Which constraint prevents an enrollment from referring to a nonexistent student?

A. CHECK

B. FOREIGN KEY

C. DEFAULT

D. INDEX

Correct Answer: B. FOREIGN KEY

Question 3

What is the result of a SQL predicate comparing an ordinary value with NULL using =?

A. TRUE

B. FALSE

C. UNKNOWN

D. A syntax error in all DBMSs

Correct Answer: C. UNKNOWN

Question 4

Which relational-algebra operation changes the selected attributes of a relation?

A. Selection

B. Projection

C. Difference

D. Cartesian product

Correct Answer: B. Projection

Question 5

Which SQL expression correctly tests whether email is missing?

A. email = NULL

B. email <> NULL

C. email IS NULL

D. email == NULL

Correct Answer: C. email IS NULL

Question 6

Under classical set semantics, what happens to duplicate tuples produced by projection?

A. They are retained twice.

B. They are converted to NULL.

C. They are eliminated.

D. They cause a primary-key error.

Correct Answer: C. They are eliminated.

Question 7

A relation R has 4 tuples and relation S has 6 tuples. How many tuple pairs are in R × S, assuming finite ordinary relations?

A. 2

B. 10

C. 24

D. 64

Correct Answer: C. 24

Question 8

Which declaration best prevents duplicate registration of the same student in the same course offering?

A. A CHECK constraint on the course title

B. A composite UNIQUE constraint on student_id and offering_id

C. A DEFAULT value for student_id

D. An index on grade alone

Correct Answer: B. A composite UNIQUE constraint on student_id and offering_id

Question 9

What does COUNT(column_name) generally exclude?

A. Rows containing NULL in that column

B. Rows containing zero

C. Rows containing duplicate values only

D. Rows created in the current transaction

Correct Answer: A. Rows containing NULL in that column

Question 10

Which foreign-key action is most appropriate when historical child records must be retained after a parent is retired?

A. CASCADE deletion

B. Delete the child records manually

C. Preserve the parent or use a retirement status rather than deleting history

D. Set every identifying foreign key to an arbitrary value

Correct Answer: C. Preserve the parent or use a retirement status rather than deleting history