Table-Based Structure

In 1970, a mathematician at IBM named E.F. Codd published a paper that would transform the entire computing industry. Titled "A Relational Model of Data for Large Shared Data Banks," this groundbreaking work proposed something radical: instead of navigating complex pointer structures or hierarchical trees, data could be organized into simple, intuitive tables.

This deceptively simple idea—that data could be represented as rows and columns, like a spreadsheet—became the foundation of virtually every major database system in existence. From Oracle to PostgreSQL, MySQL to SQL Server, the relational model's table-based structure has dominated database technology for over five decades.

But what makes tables so powerful? Why did this representation triumph over hierarchical and network models? And what are the precise semantics behind what appears to be a simple grid of data?

While we casually refer to database tables, the formal term in the relational model is relation. This isn't mere academic pedantry—the choice of terminology reflects deep mathematical foundations that give the relational model its power.

What is a Relation?

In mathematics, a relation is a subset of the Cartesian product of one or more sets. In database terms, this translates to:

• A relation is a set of tuples
• Each tuple represents a single record (row)
• Each tuple contains values for a fixed set of attributes (columns)
• The domain of an attribute defines all possible values it can hold

This formal definition has profound implications for how data behaves in a relational system.

Let's dissect the structure of a relation in detail. Consider a relation storing employee information:

Employee(emp_id: INTEGER, name: VARCHAR(100), department: VARCHAR(50), salary: DECIMAL(10,2), hire_date: DATE)

Here, Employee is the relation name (or relation schema). The items in parentheses define the attributes and their domains.

The Relation Schema

A relation schema, denoted R(A₁, A₂, ..., Aₙ), consists of:

• The relation name R
• A set of attributes {A₁, A₂, ..., Aₙ}
• A mapping from each attribute to its domain

Key Components Explained

1. Attributes (Columns)

Each attribute represents a single, atomic piece of information about the entities the relation describes. In our example:

• emp_id uniquely identifies each employee
• name stores the employee's full name
• department categorizes the employee's organizational unit
• salary records their compensation

2. Domains

Every attribute is associated with a domain—the complete set of values it can take. Domains can be:

• Simple: Built-in types like INTEGER, VARCHAR, DATE
• User-defined: Custom types like email addresses or SSNs with specific formats
• Semantic: Beyond the data type, domains can encode meaning (e.g., salary must be positive)

3. Tuples (Rows)

Each tuple is an ordered list of values, one for each attribute. A tuple in our example:

(1001, 'Alice Chen', 'Engineering', 95000.00)

This tuple represents a single employee with all their associated attribute values.

4. Relation Instance

The complete set of tuples at any given moment is called the relation instance or relation state. This is the actual data—what changes as employees are hired, promoted, or leave. The schema, by contrast, defines the structure and typically changes rarely.

Relations are not arbitrary tables. They obey specific mathematical properties that distinguish them from spreadsheets or CSV files. These properties aren't constraints imposed for convenience—they're fundamental to enabling the powerful operations the relational model supports.

Why These Properties Matter

Each property enables something important:

No Duplicates → Integrity Duplicate elimination ensures data integrity. If the same employee appears twice with different salaries, which is correct? Duplicates create ambiguity. By preventing them mathematically, the relational model forces clean, unambiguous data.

Unordered Tuples → Query Optimization Because tuple order is undefined, the database engine is free to store and retrieve data in whatever order is most efficient. It can use indexes, parallelization, and caching without worrying about preserving artificial ordering.

Unordered Attributes → Schema Evolution Referring to attributes by name rather than position means adding a new column doesn't break existing queries. You can evolve your schema without rewriting your application.

Atomicity → Simple, Predictable Operations When every value is atomic, operations like comparison, sorting, and indexing are straightforward. There's no need for special logic to handle nested structures or varying lengths.

The concepts of attributes and domains deserve deeper exploration, as they form the foundation of relational integrity and query semantics.

Attribute Semantics

An attribute isn't just a column name—it's a semantic statement about the data. Consider these two relations:

Employee(id, name, manager_id)
Department(id, name, budget)

Both have id and name attributes, but they mean different things. Employee.id is an employee identifier; Department.id is a department identifier. Even if both are integers, they represent different domains semantically.

Domain Types

1. Simple Domains Built-in data types provided by the DBMS:

• INTEGER, BIGINT, SMALLINT
• DECIMAL(p, s), FLOAT, REAL
• CHAR(n), VARCHAR(n), TEXT
• DATE, TIME, TIMESTAMP
• BOOLEAN

2. Constrained Domains Simple domains with additional restrictions:

CREATE DOMAIN positive_salary AS DECIMAL(10,2)
    CHECK (VALUE > 0 AND VALUE < 10000000);

CREATE DOMAIN email_address AS VARCHAR(255)
    CHECK (VALUE ~ '^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$');

3. Enumerated Domains A fixed set of allowed values:

CREATE TYPE employment_status AS ENUM ('ACTIVE', 'INACTIVE', 'TERMINATED', 'ON_LEAVE');

4. Composite Domains (Extended Relational) Some modern systems support structured types:

CREATE TYPE address AS (
    street VARCHAR(100),
    city VARCHAR(50),
    postal_code VARCHAR(20),
    country CHAR(2)
);

Note: Pure relational theory requires atomic values; composite types extend the model.

A tuple is more than a row of values—it's a proposition about the real world. Understanding this perspective transforms how you think about data modeling.

Tuples as Facts

Consider this tuple from our Employee relation:

(1001, 'Alice Chen', 'Engineering', 95000.00)

This tuple asserts a fact: "There exists an employee with ID 1001, named Alice Chen, who works in Engineering and earns $95,000."

This interpretation has profound implications:

• Adding a tuple = asserting a new fact about the world
• Deleting a tuple = retracting a previously asserted fact
• Updating a tuple = correcting or updating an existing fact
• A missing tuple = absence of that fact (not that we don't know—that the fact doesn't hold)

The Closed World Assumption

Relational databases operate under the Closed World Assumption (CWA): if a fact is not represented by a tuple in the database, that fact is assumed to be false.

This contrasts with the Open World Assumption used in some knowledge representation systems, where a missing fact simply means we don't know.

Example under CWA:

• Our Employee relation has no tuple for employee ID 9999
• Conclusion: Employee 9999 does not exist (not "we don't know if they exist")

This assumption is what allows us to answer questions like "How many employees are in Engineering?" with a definitive count. If we couldn't assume completeness, every count would be "at least n."

Practical Implications:

• Data entry is critical—missing data means missing facts
• Deletions must be intentional—you're declaring something no longer true
• NULLs must be used carefully—they break the simple true/false proposition model

A critical distinction in the relational model is between schema (structure) and instance (data). This separation is fundamental to data independence and schema evolution.

Relation Schema (Intension)

The schema defines the structure:

• Relation name
• Attribute names and their domains
• Integrity constraints
• Keys and relationships

Schemas are defined at design time and typically change infrequently. They describe what could be stored.

Relation Instance (Extension)

The instance is the actual data:

• The specific tuples currently in the relation
• Values that satisfy the schema's constraints
• The state of the data at a particular moment

Instances change constantly as data is inserted, updated, and deleted. They describe what is stored.

Why This Distinction Matters

1. Data Independence Separating schema from instance enables logical data independence. Applications can be written against the schema; the actual data can change without affecting application logic.

2. Constraint Enforcement Constraints defined in the schema are enforced on every instance. You define rules once; they apply to all data, past and future.

3. Query Generality Queries are written against schemas, not specific data. SELECT * FROM Employee WHERE salary > 80000 works regardless of how many employees exist or what their specific salaries are.

4. Schema Evolution Schemas can be modified (add column, change type) while preserving existing instance data, often with automatic migration.

While relations are mathematical objects, we commonly visualize them as tables. Understanding the visual conventions helps when reading documentation, designing schemas, and communicating with colleagues.

Standard Table Visualization

Notation Conventions

1. Schema Notation

Relation_Name(attribute₁: domain₁, attribute₂: domain₂, ...)

Example: Employee(emp_id: INT, name: VARCHAR(100), salary: DECIMAL(10,2))

2. Instance Notation

Relation_Name = {tuple₁, tuple₂, ...}

Example: Employee = {(1001, 'Alice', 95000), (1002, 'Bob', 78000)}

3. Key Notation Primary key attributes are often underlined or marked:

Employee(emp_id, name, salary)  — emp_id underlined as primary key

4. Foreign Key Notation Relationships between relations shown with arrows or notation:

Employee(emp_id, name, dept_id → Department)