Database theory

Database Theory

Database theory is a branch of formal sciences that studies the logical, mathematical, and computational foundations of database systems. It encompasses the design, representation, manipulation, and management of structured data, focusing on data models, query languages, integrity constraints, and transaction processing. The field draws on concepts from discrete mathematics, logic, automata theory, and complexity theory to provide rigorous frameworks for understanding how data can be stored, retrieved, and updated efficiently and reliably.

1 Foundations of Database Theory

1.1 Relational Model

The relational model, introduced by Edgar F. Codd in 1970, organizes data into relations (tables) where each relation consists of a set of tuples (rows) sharing the same attributes (columns). It provides a mathematical basis for data independence and declarative querying.

1.1.1 Relations and Tuples

A relation is defined as a subset of the Cartesian product of a list of domains, each domain being a set of atomic values. A tuple is an ordered list of attribute values, one from each domain. Relations are unordered sets of tuples, with attribute names identifying each position. The degree of a relation is the number of attributes, and the cardinality is the number of tuples.

1.1.2 Keys and Functional Dependencies

A key is a set of attributes that uniquely identifies a tuple. Candidate keys are minimal superkeys, and one is chosen as the primary key. Functional dependencies (FDs) express constraints of the form X → Y, meaning that if two tuples agree on attributes X, they must also agree on Y. FDs are central to normalization and dependency theory.

1.2 Set Theory and Logic

Set theory and formal logic provide the mathematical underpinnings for defining query languages and constraints. First-order predicate logic is used to express queries and integrity conditions.

1.2.1 First-Order Predicate Logic

First-order logic (FOL) extends propositional logic with quantifiers (∀, ∃) and predicates over variables. In database theory, a database is interpreted as a finite structure over a relational schema. Queries are expressed as FOL formulas whose free variables represent the result columns. Safe FOL formulas ensure finite results by restricting quantification to active domains.

1.2.2 Domain Relational Calculus

Domain relational calculus (DRC) is a non-procedural query language based on first-order logic. Queries are of the form {<x₁,…,xₙ>	P(<x₁,…,xₙ>)}, where P is a FOL formula with variables ranging over domains. DRC is equivalent in expressive power to tuple relational calculus and relational algebra.

1.3 Algebraic Foundations

Relational algebra and tuple relational calculus form the core of the relational query paradigm. They provide formal semantics and a basis for query optimization.

1.3.1 Relational Algebra

Relational algebra is a set of operators on relations: selection (σ), projection (π), rename (ρ), Cartesian product (×), join (⨝), union (∪), intersection (∩), difference (−), and division (÷). Each operator returns a relation, allowing composition. The algebra is relationally complete, meaning it can express any query definable in first-order logic (without recursion or aggregation).

1.3.2 Tuple Relational Calculus

Tuple relational calculus (TRC) is a declarative language using tuple variables ranging over relations. Queries are of the form {t	P(t)}, where t is a tuple variable and P is a FOL formula involving tuple attributes. TRC and relational algebra are equivalent in expressive power (Codd’s theorem).

2 Data Models

Data models define the structure, constraints, and operations for representing data. They are categorized into conceptual, logical, and physical levels.

2.1 Conceptual Data Models

Conceptual models describe data at a high, implementation-independent level, focusing on entities, relationships, and constraints as perceived by users.

2.1.1 Entity-Relationship Model

The entity-relationship (ER) model represents data as entity types (e.g., Customer, Order) and relationship types connecting them. Attributes describe entities and relationships. Cardinality constraints (one-to-one, one-to-many, many-to-many) and participation constraints (total/partial) are key. The ER model is widely used in database design.

2.1.2 Enhanced Entity-Relationship Model

The enhanced ER (EER) model extends the ER model with specialization/generalization (subclass/superclass), categories (union types), and attribute inheritance. It supports more complex conceptual modeling, such as overlapping or disjoint subclasses and total versus partial specialization.

2.2 Logical Data Models

Logical models are implementation-oriented representations that organize data into structures amenable to computer storage and retrieval.

2.2.1 Hierarchical Model

The hierarchical model organizes data into tree structures, where each record type has a parent-child relationship. Data navigation follows predefined paths. It was prominent in early database systems (e.g., IMS) but lacks flexibility for many-to-many relationships.

2.2.2 Network Model

The network model extends the hierarchical model by allowing multiple parent records per child (a graph structure). It uses sets (owner-member relationships) and provides navigational querying via record-at-a-time access (e.g., CODASYL). It supports many-to-many relationships but is complex.

2.2.3 Relational Model

The relational model is the dominant logical model, representing data as relations (tables) with sets of tuples. It supports set-oriented operations and declarative queries. Its mathematical foundation simplifies data independence and integrity enforcement.

2.2.4 Object-Oriented Model

The object-oriented model integrates database capabilities with object-oriented programming concepts: objects include both data (attributes) and behavior (methods). Features include object identity, inheritance, and complex types. Standards like ODMG 3.0 define query languages (OQL) and binding to languages like Java and C++.

2.3 Physical Data Models

Physical models specify how data is stored on physical media, including file organization and indexing.

2.3.1 Storage Structures

Common storage structures include heap files (unordered), sorted files, and hash files. Each provides different trade-offs between insertion, deletion, and retrieval performance. Record and block management are fundamental to efficient I/O.

2.3.2 Indexing Techniques

Indexes accelerate data retrieval by providing fast access paths. Primary indexes are built on the ordering key of a sorted file. Secondary indexes provide access on non-ordering attributes. B-trees and hash indexes are commonly used. Multidimensional indexes (R-trees, kd-trees) support spatial and similarity queries.

3 Query Languages

Query languages provide a means to specify data retrieval and manipulation. The field studies their syntax, semantics, expressive power, and optimization.

3.1 Relational Query Languages

Relational query languages include both procedural (algebraic) and declarative (calculus-based) forms. Two prominent examples are SQL and Datalog.

3.1.1 SQL and Theoretical Foundations

SQL (Structured Query Language) is the standard relational query language. Its core SELECT-FROM-WHERE clause corresponds to relational algebra expressions: SELECT maps to projection, FROM to cross product/join, and WHERE to selection. SQL extends the relational model with aggregation (GROUP BY, HAVING), sorting (ORDER BY), and set operations. Theoretical foundations connect SQL to relational algebra and first-order logic, though SQL includes constructs (e.g., NULLs, duplicates, outer joins) that go beyond pure relational theory.

3.1.2 Datalog

Datalog is a declarative logic programming language based on Prolog, used in deductive databases. Rules are of the form head :- body, where body atoms are relational literals and comparisons. Datalog supports recursion and negation (with stratification). It is relationally complete and can express transitive closure queries that cannot be expressed in first-order logic. Datalog evaluation relies on fixpoint semantics.

3.2 Expressive Power and Completeness

Expressive power measures which queries a language can express. Relational completeness is a key benchmark.

3.2.1 Relational Completeness

A query language is relationally complete if it can express every query definable in relational algebra (or equivalently, in safe first-order logic). Examples include relational algebra, tuple relational calculus, and Datalog without recursion. Relational completeness is a minimal standard for practical query languages.

3.2.2 Limitations of First-Order Logic

First-order logic (FOL) cannot express certain queries due to its finite-model theory limitations. For instance, transitive closure (e.g., “find all nodes reachable in a graph”) is not expressible in FOL. Recursive queries (e.g., in Datalog) extend beyond FOL. Additionally, FOL cannot express aggregate queries (e.g., sum, count) unless extended.

3.3 Query Equivalence and Optimization

Query equivalence refers to two queries producing the same result for all database instances. Optimization rewrites a query into an equivalent but more efficient form.

3.3.1 Query Rewriting Rules

Typical rewriting rules include pushing selections down (early reduction of tuples), merging projections, commutativity of joins, and distributivity of selection over union and join. The goal is to minimize the size of intermediate results and reduce I/O. Equivalence is based on algebraic laws.

3.3.2 Chase and Backchase Algorithms

The chase algorithm enforces constraints (e.g., functional dependencies) by adding tuples to a tableau representing a query, generating all possible information. The backchase algorithm removes redundant joins. Together, they can find minimal equivalent queries under constraints. They are used in constraint-based query optimization and data exchange.

4 Database Design Theory

Database design theory provides formal methods to create schemas that minimize redundancy and avoid anomalies.

4.1 Normalization

Normalization decomposes relations into smaller, well-structured relations based on dependencies.

4.1.1 Functional Dependencies and Closure

Given a set of FDs, the closure of a set of attributes X (denoted X⁺) is the set of attributes functionally determined by X. The closure algorithm is used to determine keys and test membership of FDs. Armstrong’s axioms derive all implied FDs.

4.1.2 Normal Forms (1NF, 2NF, 3NF, BCNF)

• 1NF: Each attribute is atomic (no multivalued or composite attributes).
• 2NF: It is in 1NF, and every non-prime attribute is fully functionally dependent on every candidate key (no partial dependency).
• 3NF: It is in 2NF, and no non-prime attribute is transitively dependent on any candidate key.
• BCNF (Boyce-Codd Normal Form): For every non-trivial FD X → Y, X must be a superkey. BCNF is stronger than 3NF.

4.1.3 Multivalued Dependencies and 4NF

A multivalued dependency (MVD) X ↠ Y asserts that for each X-value, Y-values appear independently in the relation. Fourth normal form (4NF) requires that the relation is in BCNF and every MVD is a functional dependency on a superkey.

4.1.4 Join Dependencies and 5NF

A join dependency (JD) states that a relation is equal to the natural join of its projections on subsets of attributes. Fifth normal form (5NF, also called projection-join normal form) requires that every JD is implied by candidate keys. 5NF eliminates redundancy from join dependencies that are not captured by keys.

4.2 Dependency Theory

Dependency theory studies the logical implications and properties of constraints such as FDs, MVDs, and JDs.

4.2.1 Armstrong’s Axioms

Armstrong’s axioms are a sound and complete set of inference rules for FDs: reflexivity (if Y ⊆ X, then X → Y), augmentation (if X → Y, then XZ → YZ), and transitivity (if X → Y and Y → Z, then X → Z). Additional derived rules include union, decomposition, and pseudo-transitivity.

4.2.2 Minimal Cover and Canonical Forms

A minimal cover of a set of FDs is an equivalent set with no redundant dependencies, no redundant attributes in dependency left-hand sides, and each dependency having a single attribute on the right. It is unique up to ordering. Minimal covers are used in schema decomposition algorithms and in computing keys.

4.3 Integrity Constraints

Integrity constraints enforce the correctness and consistency of data.

4.3.1 Domain Constraints

Domain constraints restrict the set of allowable values for an attribute, such as data types, ranges, and enumerated sets. They are enforced at the attribute level.

4.3.2 Referential Integrity

Referential integrity ensures that a foreign key value in one relation matches a primary key value in the referenced relation (or is null). This constraint maintains consistency across related tables. Enforcement includes actions (cascade, set null, restrict) on updates and deletions.

4.3.3 Assertions and Triggers

Assertions are general conditions on the database state that must always hold (e.g., total salary sum less than budget). Triggers are event-condition-action rules that automatically execute specified actions when data is modified, used for enforcing complex constraints, auditing, and maintaining derived data.

5 Transaction Processing and Concurrency Control

Transaction processing manages concurrent access to data while preserving consistency.

5.1 Transaction Model

A transaction is a sequence of read/write operations treated as an atomic unit of work.

5.1.1 ACID Properties

• Atomicity: All operations complete successfully or none have any effect.
• Consistency: Transactions preserve database consistency (integrity constraints).
• Isolation: Concurrent transactions appear to execute serially.
• Durability: Committed changes survive failures.

5.1.2 Schedules and Serializability

A schedule is an ordering of operations from one or more transactions. A schedule is serializable if it is equivalent to some serial schedule (transactions executed sequentially). Conflict serializability ensures that the order of conflicting operations (two operations on the same data item, at least one write) is consistent with a serial schedule. View serializability is a less restrictive notion.

5.2 Concurrency Control Protocols

Protocols ensure serializability and isolation.

5.2.1 Lock-Based Protocols

Two-phase locking (2PL) requires transactions to acquire locks before accessing data and to release locks only after acquiring all locks (growing phase then shrinking phase). Strict 2PL releases all locks at commit time, supporting cascadeless schedules. Deadlocks are handled by detection and resolution or prevention.

5.2.2 Timestamp-Based Protocols

Each transaction is assigned a timestamp. Operations are ordered by timestamps; a write with a timestamp larger than the transaction’s read timestamp may cause a rollback (Thomas write rule allows ignoring some outdated writes). Timestamp ordering ensures serializability without locks but may cause more restarts.

5.2.3 Optimistic Protocols

Optimistic concurrency control assumes conflicts are rare. Transactions execute without locks; at commit time, a validation phase checks for conflicts (e.g., comparing read/write sets). If validation fails, the transaction is aborted and restarted. Suitable for low-contention environments.

5.3 Recovery Theory

Recovery mechanisms restore the database to a consistent state after a failure.

5.3.1 Log-Based Recovery

A log records all modifications (undo/redo information). The recovery manager uses write-ahead logging (WAL) to ensure that before a transaction commits, its log records are flushed to stable storage. During restart, the system scans the log to redo committed transactions and undo uncommitted ones. Checkpoints reduce recovery time.

5.3.2 Shadow Paging

Shadow paging maintains two copies of the database: the current page table and a shadow page table. When a transaction commits, the shadow table becomes the current one. This avoids logging but requires page-level copies; used less frequently than log-based recovery.

6 Query Optimization and Evaluation

Query optimization selects an efficient execution plan from many equivalent alternatives.

6.1 Cost Models

A cost model estimates the resource consumption (I/O, CPU, memory) of each plan.

6.1.1 Statistical Estimators

Database statistics (e.g., number of tuples, distinct values, histograms) are used to estimate selectivity of predicates (fraction of tuples satisfying a condition). Cardinality estimates are critical for join size estimation. Errors propagate, making robust estimation challenging.

6.1.2 Index Selectivity

Index selectivity measures how effectively an index reduces the number of tuples accessed. A high-selectivity index (e.g., unique index) retrieves few tuples. Cost models incorporate index access method costs (e.g., B-tree traversal, leaf page scan).

6.2 Plan Space and Search Strategies

The optimizer enumerates candidate plans and selects the lowest-cost one.

6.2.1 Dynamic Programming

Dynamic programming (DP) for join ordering partitions the set of relations into subsets and computes the best plan for each subset. The classic DP algorithm (System R) enumerates left-deep trees. It guarantees optimality for cost models satisfying the principle of optimality but can be expensive for many joins.

6.2.2 Heuristic-Based Optimization

Heuristics reduce the search space: push selections down, avoid cross products, use interesting orders, and apply simple join ordering rules (e.g., smallest relations first). Many commercial optimizers combine heuristics with limited DP.

6.3 Advanced Optimization

Advanced techniques handle specific query types.

6.3.1 Top-K Queries

Top-k queries return the k highest-ranked tuples according to a scoring function. Optimization uses techniques like threshold algorithms (e.g., Fagin’s algorithm, TA) that access sorted lists and stop early. Indexes and materialized views can accelerate top-k.

6.3.2 Join Ordering and Enumeration

For complex queries (e.g., many joins, star schemas), clever enumeration algorithms (e.g., memoization, genetic algorithms, randomized search) are used. Bushy trees (non-linear join orders) are considered when parallel execution is possible. The problem is NP-hard for arbitrary cost functions.

7 Advanced Topics

Advanced database theory addresses distributed, analytical, graph, and temporal data.

7.1 Distributed Database Theory

Distributed databases manage data across multiple networked sites.

7.1.1 Data Partitioning and Replication

Data can be horizontally partitioned (sharded) by key ranges, hash functions, or list-based rules. Vertical partitioning splits relations by columns. Replication creates copies of data for availability and performance; it introduces consistency challenges (e.g., eventual consistency vs. strong consistency in CAP theorem).

7.1.2 Distributed Query Processing

Queries in a distributed system require data movement between sites. Strategies include fragment-and-replicate, semi-join reduction, and shipping operations (e.g., to data). Optimization must consider network costs, local processing, and site autonomy.

7.2 Data Warehousing and OLAP

Data warehouses support analytical queries over historical data.

7.2.1 Star Schema and Snowflake Schema

A star schema consists of a central fact table with numerical measures (e.g., sales amount) and dimension tables (e.g., time, product, customer) surrounding it. Snowflake schema normalizes dimensions into subdimensions (e.g., product category). Both support OLAP operations (roll-up, drill-down, slice, dice).

7.2.2 Cube Computation

A data cube generalizes grouping by multiple dimensions. Cube computation (e.g., using ROLAP, MOLAP, or HOLAP) precomputes aggregates for all combinations of dimensions. Algorithms like BUC (Bottom-Up Cube) and iceberg cubes optimize space and time.

7.3 Graph Database Theory

Graph databases represent data as vertices and edges, enabling efficient traversal.

7.3.1 Property Graph Model

A property graph consists of nodes (vertices) with properties (key-value pairs) and edges (relationships) that are directed, labeled, and also may have properties. It is a flexible model for interconnected data (e.g., social networks, knowledge graphs).

7.3.2 Graph Query Languages (e.g., SPARQL, Cypher)

SPARQL is a W3C standard query language for RDF (triple) graphs, using pattern matching (SELECT, CONSTRUCT, ASK). Cypher is a declarative language for property graphs, using ASCII-art-like patterns (MATCH (n)-[:FRIEND]->(m)). Both support path patterns and aggregation.

7.4 Temporal and Deductive Databases

Temporal databases manage time-varying data, while deductive databases combine logic-based rules with querying.

7.4.1 Temporal Data Models

Temporal models include valid time (when fact is true in reality) and transaction time (when fact was stored). Bitemporal models combine both. Representations include timestamped tuples or dual tables. Query languages (e.g., TSQL2) extend SQL with temporal operators.

7.4.2 Recursive Query Processing

Deductive databases support recursive queries via Datalog. Evaluation methods include naive fixpoint, semi-naive evaluation (incremental computation), and magic sets rewriting (goal-directed evaluation). Recursion enables queries like transitive closure and recursive aggregation (e.g., shortest path).