Relations and Tables: The Foundation of Relational Databases

If the relation schema is the architectural blueprint, the relation instance is the building itself—the actual structure that exists at a particular moment. Instances are what databases are ultimately about: storing, retrieving, and manipulating real data that represents real-world facts.

While schemas define what's possible, instances capture what's true. The same schema can have infinitely many valid instances, ranging from the empty relation (no tuples) to massive collections of millions of records. Understanding instances—their properties, their operations, and their constraints—is essential for effective database work.

This page completes our exploration of relations and tables by examining the dynamic, ever-changing content that gives databases their value.

A relation instance (also called a relation state or relation extension) is the set of tuples that a relation contains at a particular moment in time.

Formal Definition:

Given a relation schema R(A₁:D₁, A₂:D₂, ..., Aₙ:Dₙ), a relation instance r of R is:

r ⊆ D₁ × D₂ × ... × Dₙ

such that:

1. r is a finite subset (instances are always finite)
2. Every tuple t ∈ r satisfies all constraints in R's constraint set
3. Each tuple t is an n-tuple (t₁, t₂, ..., tₙ) where tᵢ ∈ Dᵢ ∪ {NULL} for each i

Notation:

We write r(R) to denote an instance r of schema R. At different times, we might have r₁(R), r₂(R), etc., representing different states of the same relation.

Key Instance Properties:

Two fundamental metrics characterize every relation instance: cardinality (number of tuples) and degree (number of attributes). Understanding these metrics is crucial for query optimization, capacity planning, and understanding query results.

Cardinality (|r|):

The cardinality of instance r is the number of tuples it contains. Cardinality is:

• Dynamic: Changes with every INSERT, DELETE, or some UPDATEs (if they change key values)
• Non-negative: Minimum is 0 (empty relation)
• Bounded in practice: Limited by storage, though no theoretical upper limit

Degree (deg(R)):

The degree of a relation (also called arity) is the number of attributes. Degree is:

• Static: Fixed by the schema (changes only via ALTER TABLE)
• Structural: Defines how 'wide' each tuple is

Impact on Query Performance:

Both cardinality and degree affect query execution:

High Cardinality (Many Rows):

• Full table scans become expensive
• Index selection becomes critical
• Aggregations require more computation
• Join order matters significantly

High Degree (Many Columns):

• Rows are wider, fewer fit per disk page
• SELECT * pulls more data than needed
• Vertical partitioning may help
• Covering indexes become larger

Cardinality Estimation:

Query optimizers estimate result cardinalities to choose execution plans. If the optimizer estimates a join will produce 100 rows but it actually produces 1,000,000, the chosen plan may be catastrophically wrong. Understanding cardinality helps you:

• Write better queries (filter early)
• Create appropriate indexes
• Analyze explain plans
• Diagnose performance issues

Relations instances change through three fundamental operations: INSERT, UPDATE, and DELETE. These Data Manipulation Language (DML) operations are state transitions—they transform one valid instance into another.

INSERT: Adding Tuples

INSERT adds one or more new tuples to a relation instance.

-- Single tuple insertion
INSERT INTO employees (emp_id, emp_name, dept, salary)
VALUES (1004, 'Diana', 'Marketing', 72000);

-- Multi-tuple insertion
INSERT INTO employees (emp_id, emp_name, dept, salary)
VALUES 
    (1005, 'Edward', 'Eng', 88000),
    (1006, 'Fiona', 'Sales', 76000);

-- Insertion from query
INSERT INTO archived_employees
SELECT * FROM employees WHERE termination_date < '2020-01-01';

INSERT Constraints:

• New tuple must not violate PRIMARY KEY (no duplicate)
• Foreign key values must exist in referenced table
• CHECK constraints must be satisfied
• NOT NULL columns must have values

UPDATE: Modifying Tuples

UPDATE changes attribute values in existing tuples.

-- Update specific tuple
UPDATE employees 
SET salary = 98000 
WHERE emp_id = 1001;

-- Update multiple tuples
UPDATE employees 
SET salary = salary * 1.05 
WHERE dept = 'Engineering';

-- Update with subquery
UPDATE employees 
SET dept = 'Research' 
WHERE dept_id IN (SELECT dept_id FROM departments WHERE is_research = true);

UPDATE Constraints:

• New values must satisfy domain constraints
• Primary key updates must not create duplicates
• Foreign key updates must maintain referential integrity
• All CHECK constraints must be satisfied post-update

DELETE: Removing Tuples

DELETE removes tuples from a relation instance.

-- Delete specific tuple
DELETE FROM employees 
WHERE emp_id = 1002;

-- Delete matching tuples
DELETE FROM employees 
WHERE termination_date IS NOT NULL;

-- Delete all tuples (careful!)
DELETE FROM employees;  -- Removes all rows, table still exists

DELETE Constraints:

• Cannot delete if other tuples reference this tuple via foreign key (unless CASCADE)
• Some systems support soft delete (marking deleted rather than removing)
• Triggers may execute on delete

Every DML operation is a state transition: it takes the database from one valid state to another. Understanding state transitions helps you reason about data consistency and transaction correctness.

Formal Model:

Let S be the set of all valid database states (states satisfying all constraints). A DML operation O is a function:

O: S → S ∪ {FAILURE}

If the operation succeeds, we get a new valid state. If it would create an invalid state (constraint violation), the operation fails and the original state is preserved.

State Transition Visualized:

State S₀                    State S₁                    State S₂
┌─────────────┐   INSERT    ┌─────────────┐   UPDATE    ┌─────────────┐
│ employees   │────────────▶│ employees   │────────────▶│ employees   │
│  (1001,...)│             │  (1001,...) │             │  (1001,...')│
│             │             │  (1002,...) │             │  (1002,...) │
└─────────────┘             └─────────────┘             └─────────────┘
   Cardinality: 1              Cardinality: 2              Cardinality: 2

Transition Classification:

Note: UPDATE can change cardinality if it modifies a primary key to duplicate an existing key (which typically fails) or in special MERGE/UPSERT scenarios.

Constraint Checking During Transitions:

When a DML operation executes, the DBMS checks constraints:

Deferred vs. Immediate Checking:

Some constraints can be deferred until transaction commit:

-- PostgreSQL example: defer foreign key checking
SET CONSTRAINTS my_fk_constraint DEFERRED;

-- Now can insert child before parent in same transaction
INSERT INTO orders (order_id, customer_id) VALUES (1, 999);
INSERT INTO customers (customer_id, name) VALUES (999, 'New Customer');

COMMIT;  -- Constraint checked here

Deferred checking allows flexible insertion order but delays error detection.

Constraints divide the space of all possible instances into valid instances (those satisfying all constraints) and invalid instances (those violating at least one constraint).

The Constraint Satisfaction Perspective:

An instance r is valid for schema R if and only if:

1. Every tuple has the correct degree (n attributes)
2. Each attribute value comes from its domain (or is NULL if allowed)
3. No two tuples are duplicates (set property)
4. All schema constraints are satisfied

Detecting Invalid States:

The DBMS prevents invalid states through constraint enforcement. But sometimes invalid data enters through:

• Constraints added after data exists
• ETL/import processes that bypass constraints
• Application bugs with direct database access
• Disabled constraints during bulk loads

Finding Constraint Violations:

-- Find orphan foreign keys (child without parent)
SELECT o.*
FROM orders o
LEFT JOIN customers c ON o.customer_id = c.customer_id
WHERE c.customer_id IS NULL;

-- Find duplicates (would violate uniqueness)
SELECT email, COUNT(*)
FROM users
GROUP BY email
HAVING COUNT(*) > 1;

-- Find check constraint violations
SELECT * FROM products WHERE price < 0;

-- Find NULL violations (assuming column should be NOT NULL)
SELECT * FROM employees WHERE hire_date IS NULL;

A special case worth understanding is the empty relation instance—a relation with zero tuples.

The Empty Instance:

An empty instance r = {} (or r = ∅) satisfies:

• |r| = 0 (cardinality is zero)
• The schema is fully defined (columns, types, constraints exist)
• The relation legally exists; it just contains no facts

When Empty Instances Occur:

Algebraic Properties of Empty Relations:

Empty relations have interesting algebraic behaviors:

These properties are important for query optimization—the optimizer can short-circuit operations involving empty relations.

Handling Empty Results in Applications:

Empty results are legitimate and common. Applications must handle them gracefully:

// Bad: assumes results exist
const user = await db.query('SELECT * FROM users WHERE id = ?', [userId]);
console.log(user.name);  // ERROR if user not found!

// Good: check for empty result
const users = await db.query('SELECT * FROM users WHERE id = ?', [userId]);
if (users.length === 0) {
    throw new NotFoundError('User not found');
}
const user = users[0];

Distinguishing Causes:

An empty result can mean:

1. No data exists (legitimate empty)
2. Filter is wrong (bug in query)
3. Data exists but doesn't match (understanding issue)

Always verify: if you expect data and get none, investigate before assuming correctness.

Relation instances change over time. Understanding temporal aspects is crucial for auditing, debugging, and applications that need historical data.

Current vs. Historical State:

• Current Instance: What the relation contains right now
• Historical Instance: What the relation contained at some past time
• Temporal Instance: Relations that explicitly model time in their schema

Why Historical Data Matters:

Approaches to Historical Data:

1. Audit Logging: Separate tables record changes:

CREATE TABLE employee_audit (
    audit_id SERIAL PRIMARY KEY,
    emp_id INTEGER NOT NULL,
    action VARCHAR(10) NOT NULL,  -- INSERT, UPDATE, DELETE
    old_values JSONB,
    new_values JSONB,
    changed_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    changed_by VARCHAR(100)
);

2. Temporal Tables (SQL:2011 Standard): System-versioned tables automatically track history:

-- PostgreSQL syntax
CREATE TABLE employees (
    emp_id INTEGER PRIMARY KEY,
    emp_name VARCHAR(100),
    salary DECIMAL(12,2),
    valid_from TIMESTAMP GENERATED ALWAYS AS ROW START,
    valid_to TIMESTAMP GENERATED ALWAYS AS ROW END,
    PERIOD FOR SYSTEM_TIME (valid_from, valid_to)
) WITH SYSTEM VERSIONING;

-- Query historical state
SELECT * FROM employees 
FOR SYSTEM_TIME AS OF '2023-06-15 10:00:00';

3. Soft Deletes: Mark records as deleted rather than removing:

ALTER TABLE employees ADD COLUMN deleted_at TIMESTAMP NULL;

-- "Delete" by marking
UPDATE employees SET deleted_at = CURRENT_TIMESTAMP WHERE emp_id = 1001;

-- Query active records only
SELECT * FROM employees WHERE deleted_at IS NULL;

We've now completed our exploration of relations and tables, from abstract mathematical foundations to concrete instances. Let's synthesize what we've learned:

The Complete Picture:

Module Completion:

You now understand relations and tables from first principles through practical implementation. This foundation supports everything that follows in relational database study: keys, normalization, algebra, SQL queries, and optimization all build on these concepts.