Skip to content
CS Fundamentals

DBMS interview questions and answers

80 questions, 12 with code. About 6 h 22 min to read them all.

By TestLab · Updated

Plan for an interview
80 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a DBMS, and why is it better than a file system?

A database management system (DBMS) is software that defines, organizes, retrieves, updates, and controls shared data while enforcing integrity, security, concurrency, and recovery rules. Compared with storing records in ordinary files, a DBMS provides standardized data management and stronger guarantees for consistent, concurrent, transactional workloads.

Read full answer

Applies todatabase management systems (PostgreSQL 16 and MySQL 8.4 with InnoDB)

What a DBMS Does

A DBMS separates application logic from the physical storage of data. Its major components include:

  • Storage engine: Manages pages, files, indexes, free space, and durability mechanisms.

  • Query processor: Parses SQL or another query language, validates it, and converts it into an execution plan.

  • Query optimizer: Estimates costs and chooses an efficient access path, such as an index scan or hash join.

  • Execution engine: Runs the plan and returns result rows.

  • Transaction manager: Coordinates concurrency control, isolation, commits, and rollbacks.

  • Recovery manager: Uses techniques such as write-ahead logging and checkpoints to restore a consistent state after failure.

  • Data dictionary: Stores metadata describing schemas, relationships, constraints, and privileges.

  • Authorization manager: Controls which users and roles may read or modify particular objects.

The database is the data itself; the DBMS is the software responsible for managing that data.

DBMS Versus a File System

Concern DBMS Traditional file system
Data structure Supports tables, records, relationships, documents, or graphs Primarily organizes files and directories
Integrity Enforces primary keys, foreign keys, uniqueness, and check constraints Does not inherently understand relationships between records
Redundancy Can use normalization to reduce duplicated data Often duplicates data across application-owned files
Concurrent access Provides locking, multiversion concurrency control, and transaction isolation Applications must implement synchronization themselves
Failure recovery Offers transactions, logging, checkpoints, and automated recovery Durability depends on the file system and application behavior
Security Supports users, roles, grants, and row- or column-level policies Usually provides filesystem permissions and discretionary access controls
Querying Includes declarative SQL and query optimization Usually requires reading and parsing files in application code
Data independence Logical schemas can change without necessarily rewriting every application Applications often depend directly on file formats
Performance Maintains indexes, statistics, buffer pools, and execution plans Optimized mainly for file I/O rather than relational queries

A file system can still be the better choice for source code, logs, media files, archives, or other unstructured data. The important distinction is that a DBMS manages data semantics and shared access, not merely bytes on disk.

Worked Example

Consider two relational tables:

department

dept_id dept_name
1 Computer Science
2 Electrical

student

student_id student_name dept_id
101 Asha 1
102 Ben 2
103 Chen 1

A query that joins student with department on dept_id produces:

student_name dept_name
Asha Computer Science
Ben Electrical
Chen Computer Science

The dept_id columns form a foreign-key relationship. The DBMS can prevent an invalid department reference, optimize the join, isolate concurrent updates, and recover both tables consistently after a crash. An application storing these records in separate files would have to implement these safeguards itself.

Transactions and Recovery

A DBMS groups operations into a transaction, typically following ACID properties:

  • Atomicity: All transaction operations succeed, or all are rolled back.

  • Consistency: The transaction moves the database from one valid state to another.

  • Isolation: Concurrent transactions observe an isolation level that balances correctness and throughput.

  • Durability: Committed changes survive failures according to the database’s durability guarantees.

PostgreSQL commonly uses multiversion concurrency control, while MySQL InnoDB combines multiversioning, locking, and clustered-index storage. Both rely on operating-system filesystems for persistence, but add database-specific logging, recovery, and concurrency mechanisms.

Advantages and Trade-offs

  • Centralized control: One component enforces schemas, constraints, permissions, and concurrency rules.

  • Lower application complexity: Developers issue queries instead of implementing file parsing, record linking, locking, and recovery.

  • Better correctness: Database constraints protect relationships even when several applications modify the data.

  • Efficient retrieval: Indexes and the query optimizer improve access to large datasets.

  • Operational reliability: Backup, replication, logging, and recovery reduce the risk of inconsistent or lost data.

The trade-offs are additional CPU, memory, storage, and administrative overhead. Relational schemas can also be inflexible for rapidly changing or highly variable data, which is one reason NoSQL systems exist. In practice, PostgreSQL and MySQL InnoDB are strong choices for relational transactional data, while specialized file-based or object-storage systems remain appropriate for unstructured data and simple read-only assets.

2

What distinguishes an RDBMS from a general DBMS?

A DBMS is software that stores, retrieves, and manages a database, including its query processor, storage engine, transaction manager, and recovery mechanisms. An RDBMS is a specialized type of DBMS based on the relational model, where data is organized into relations—represented as tables—with keys, constraints, and relationships.

Read full answer

Applies todatabase management systems (general concepts; PostgreSQL 16 and MySQL 8.4 with InnoDB)

Key Differences

Aspect General DBMS RDBMS
Data model May use relational, document, key-value, graph, hierarchical, or other models Uses the relational model
Logical structure Structure depends on the selected model Data is represented by relations containing tuples and attributes
Schema May be schema-less or weakly schema-defined Uses defined relation schemas and a system catalog
Integrity rules Enforcement depends on the database engine Commonly enforces primary keys, foreign keys, UNIQUE, NOT NULL, and CHECK constraints
Query language May provide model-specific APIs or query languages Conventionally provides SQL, which operates over relations
Relationships May embed, link, or duplicate related data Represents relationships through keys, especially foreign keys
Example systems May be relational or non-relational PostgreSQL, MySQL with InnoDB, Oracle Database, and SQL Server

An RDBMS is therefore a specialization of a DBMS, not a separate category or merely a collection of additional capabilities. “General DBMS” is not a standardized alternative to “RDBMS”: the broad category includes both relational and non-relational engines such as MongoDB, Redis, and Neo4j.

A DBMS supporting SQL or transactions is not automatically relational. For example, a document database can support SQL-like querying or ACID transactions while remaining a document-oriented system.

Relational Principles and Design Practices

The relational model provides a disciplined way to represent and validate data:

  • Keys: When a primary key is declared, it uniquely identifies each tuple in a relation.

  • Foreign keys: When declared and enforced, they preserve relationships between relations and enforce referential integrity.

  • Normalization: A design process that decomposes relations according to functional dependencies to reduce redundancy and update anomalies.

  • Logical independence: The conceptual schema can remain stable while storage, indexes, and physical access methods change.

  • Declarative queries: SQL states what result is required rather than prescribing the exact retrieval procedure.

These are logical properties and design practices, not merely physical storage techniques. An index may improve query performance, but it does not replace primary-key or foreign-key constraints.

Worked Example

Consider customers and orders:

customer_id customer_name
101 Asha
102 Ravi
order_id customer_id amount
5001 101 250
5002 101 80
5003 102 120

In this schema, the separate relations are linked by matching customer_id values. The declared primary keys uniquely identify customers and orders, while the declared foreign key on orders.customer_id prevents an order from referencing a nonexistent customer.

A document-oriented DBMS could instead store each customer with an embedded list of orders:

Customer document
{customer_id: 101, customer_name: "Asha", orders: [{order_id: 5001, amount: 250}, {order_id: 5002, amount: 80}]}

Both structures can serve the application, but their integrity rules, normalization behavior, relationship representation, and query planning differ.

Textbook and Real-System Differences

The textbook relational model is idealized: a relation is a set of tuples with no duplicate tuples, and every attribute has a defined domain. SQL implementations relax some rules:

  • SQL tables can contain duplicate rows unless a key or UNIQUE constraint prevents them.

  • NULL represents missing or unknown information rather than a single textbook value.

  • PostgreSQL supports non-relational features such as JSONB, but its core system remains relational.

  • MySQL 8.4 supports JSON documents and other extensions, while InnoDB provides relational transactions, foreign keys, and crash recovery.

  • Physical storage and execution are implementation-specific. PostgreSQL and MySQL use indexes, query optimizers, buffer managers, and background processes to implement the logical relational model.

Interview Guidance and Common Pitfalls

  • Describe an RDBMS as a specialization of a DBMS, not as an entirely separate category.

  • Do not claim that only RDBMSs support transactions; non-relational systems may also provide ACID guarantees.

  • Do not define an RDBMS solely as “a DBMS that uses SQL.” The defining feature is the relational model and its logical principles.

  • Distinguish logical organization from physical storage: both relational and non-relational databases usually store data on disk and maintain indexes or internal metadata.

  • When discussing PostgreSQL or MySQL, identify the relational engine—PostgreSQL itself or MySQL’s InnoDB—rather than treating every feature of those products as part of the textbook relational model.

3

How does the three-schema architecture enable data independence?

The three-schema architecture separates a database into external, conceptual, and internal schema layers. This separation enables data independence, allowing one layer to change with minimal or no modification to the others.

Read full answer

Applies todatabase management systems (ANSI/SPARC model; PostgreSQL 16 and MySQL 8.4 InnoDB examples)

Architecture Layers

  • External schema: A user- or application-specific view of the database. It exposes the columns, rows, and relationships required by that user while hiding unrelated details.

  • Conceptual schema: The community- or organization-wide logical model. It defines entities, relationships, attributes, constraints, and the logical structure of the entire database independently of physical storage.

  • Internal schema: The physical representation of the data. It includes storage organization, file layouts, indexes, access paths, and physical encoding details.

A typical flow is:

External schema → Conceptual schema → Internal schema

An application normally interacts with an external view rather than directly with storage structures.

Schema Mappings

Two mappings connect the layers:

  • External–conceptual mapping: Describes how the global conceptual schema is transformed into each user-specific external schema.

  • Conceptual–internal mapping: Describes how logical tables, records, indexes, and other objects are represented physically and accessed by the storage engine.

These mappings isolate changes at one level. For example, adding an index changes an access path in the internal schema without requiring the conceptual schema, external views, or application queries to change.

Types of Data Independence

Property Meaning Typical example
Physical data independence The internal schema can change without modifying the conceptual schema, external schemas, or application programs. Adding an index, reorganizing files, or changing a physical storage format without changing table definitions.
Logical data independence The conceptual schema can change without modifying external schemas or application programs. Splitting data into another relation while preserving a stable external view over the original information.

Logical data independence is generally harder to achieve because a conceptual redesign may affect the data required by users. Physical data independence is usually easier because indexes and storage layouts can often evolve transparently.

For example, suppose an application uses a customer_names view containing customer_id and name. Adding another index for name lookups changes the physical access path while the view and application SQL remain unchanged. Likewise, moving email addresses from the customer relation into customer_email is a conceptual redesign; a suitably defined external view can preserve the interface expected by existing applications.

Textbook Model and Real Systems

The ANSI/SPARC model provides a useful conceptual separation, but real database products do not expose three completely independent layers:

  • PostgreSQL represents tables and views in system catalogs. Views commonly serve the same practical purpose as external schemas, while query planners and storage engines select indexes, page layouts, and execution strategies.

  • MySQL InnoDB stores records in an indexed table structure and manages indexes through its data dictionary. Query plans may change after an index is added, but application SQL and the logical schema can remain stable.

  • A view does not automatically provide logical data independence for every redesign. If a user requires a newly introduced attribute, the external schema must eventually be updated.

  • Physical data independence does not guarantee identical performance. Adding an index may improve one query while increasing write cost and storage usage.

Thus, the three-schema architecture explains how DBMSs isolate users and applications from physical storage changes and, to a greater extent, logical database redesigns.

4

What are the main data models used in DBMSs?

A data model defines how data is organized, related, constrained, and manipulated by a database. Traditional DBMS models include relational, hierarchical, network, object-oriented, and object-relational models, while modern NoSQL systems commonly use document, key-value, column-family, and graph models.

Read full answer

Applies todatabase management systems, including PostgreSQL 16 and MySQL 8 with InnoDB

Data Model Layers

Data models are often discussed at three abstraction levels:

Level Purpose Typical representation
Conceptual Describes entities, attributes, and relationships independent of implementation ER model, UML class diagram
Logical Represents tables, keys, records, and constraints Relational schema, JSON schema, graph schema
Physical Defines storage and access details B-tree indexes, heap files, hash partitions

For example, an Order entity with order_id and customer_id may be modeled conceptually with an ER diagram, logically as a relational table, and physically as heap pages accessed through a B-tree index.

Traditional Database Models

Data model Structure and relationships Main strengths Main limitations
Relational Tables contain rows; primary and foreign keys express relationships Strong constraints, standardized SQL, predictable joins Complex relationships can require many joins; horizontal scaling is difficult
Hierarchical A tree of parent-child records Fast access through known paths; useful for classifications One parent per node; many-to-many relationships are awkward
Network A graph with explicit links between records Supports many-to-many relationships and navigational access Complex administration and tightly coupled application structure
Object-oriented Objects combine state and behavior Natural mapping to object-oriented programs Object identity, inheritance, and persistence complicate queries and optimization
Object-relational Relational tables extended with objects, types, inheritance, and user-defined functions Combines SQL with richer data types Feature overlap can increase complexity and reduce portability

The relational model, formalized by E. F. Codd, is the dominant model for transactional systems. PostgreSQL and MySQL InnoDB are relational systems: their central abstraction remains tables, rows, columns, keys, and constraints, even though both also support JSON data.

NoSQL Data Models

Data model Representation Typical use case Example systems
Key-value Unique key mapped to an opaque value Sessions, caches, simple lookups Redis, Amazon DynamoDB
Document Self-contained JSON-like documents Content, catalogs, event payloads MongoDB, Couchbase
Column-family Rows grouped by columns or column partitions Time-series and very large-scale workloads Apache Cassandra, HBase
Graph Nodes, edges, and properties Relationships and path analysis Neo4j, Amazon Neptune

These are not mutually exclusive in practice. For example, a document may contain nested arrays of products, while a relational schema stores products in a separate table linked by a foreign key.

Concrete Representation

In a relational design:

  • Customer(customer_id, name, city)

  • Order(order_id, customer_id, order_date)

  • Product(product_id, name, price)

  • OrderItem(order_id, product_id, quantity)

A product is linked to an order through OrderItem. In a document model, the same information may appear inside one order document as an array of product objects. The relational design reduces duplication through normalization; the document design can retrieve an entire order in one operation but requires careful handling of duplicated product data.

Trade-offs and Selection

  • Use relational models when data integrity, transactions, complex joins, and a consistent schema are primary requirements. PostgreSQL is a common choice for general-purpose workloads.

  • Use document models when records are naturally self-contained and retrieved as a unit.

  • Use column-family models when write throughput and horizontal distribution across large datasets matter more than rich relational queries.

  • Use graph models when relationships are the primary data and traversals such as “friends of friends” are frequent.

  • Use hierarchical or network models in specialized legacy or navigational systems, although most new applications favor relational or NoSQL alternatives.

In real systems, the theoretical categories overlap. PostgreSQL supports JSONB, arrays, extensions, and indexing, but it remains a relational DBMS. Likewise, MySQL InnoDB provides ACID transactions, foreign keys, and clustered indexes while supporting a JSON column type. These features extend the relational model; they do not automatically turn the systems into document or graph databases.

5

What are the building blocks of an entity-relationship (ER) model?

An entity-relationship (ER) model is a conceptual data model that describes real-world objects, their properties, and the associations between them before the database is implemented relationally. Its main building blocks are entities, attributes, and relationships, supplemented by keys and structural constraints.

Read full answer

Applies todatabase management systems (ER modeling with PostgreSQL 16 and MySQL 8.4/InnoDB)

Core Concepts

  • Entity: A distinguishable object or event that the database must store information about, such as a Student, Course, or Order.

  • Entity set: A collection of entities of the same type. For example, STUDENT represents all students.

  • Attribute: A property of an entity or relationship, such as StudentName, CourseTitle, or Grade.

  • Relationship: An association between entity sets. ENROLLMENT associates students with courses.

  • Key attribute: An attribute that uniquely identifies each entity in an entity set, such as StudentID.

An ER model captures both the structure of data and important business rules. It is therefore more precise than an informal list of tables and columns.

ER Model Components

Component Purpose Example
Entity set Represents a category of business objects STUDENT, COURSE
Attribute Describes a property of an entity or relationship StudentName, Grade
Relationship set Represents an association between entity sets ENROLLMENT
Key Uniquely identifies entity instances StudentID
Structural constraint Controls how entities may participate A student may enroll in many courses

Attributes can also be classified as follows:

  • Simple attribute: Stored as one value, such as Age.

  • Composite attribute: Divided into meaningful subparts, such as Address containing Street, City, and PostalCode.

  • Multivalued attribute: Can contain multiple values, such as PhoneNumber. In a relational design, it is commonly normalized into a separate table.

  • Derived attribute: Calculated from other data, such as EnrollmentCount; it is not necessarily stored.

  • Key attribute: Identifies an entity. A composite key may use several attributes together.

Relationships and Structural Constraints

The degree of a relationship is the number of participating entity sets:

  • Unary: An entity relates to itself, such as an employee managing another employee.

  • Binary: Two entity sets participate, such as students enrolling in courses. This is the most common case.

  • Ternary: Three entity sets participate, such as a student enrolling in a section of a course.

Relationships are commonly classified by mapping cardinality:

Cardinality Meaning Example
One-to-one Each entity on one side relates to at most one on the other One passport belongs to one citizen
One-to-many One entity may relate to many others One department employs many employees
Many-to-many Entities on both sides may relate to many others Students enroll in courses

Participation constraints specify whether an entity must participate:

  • Total participation: Every entity must participate in the relationship. Represented by a double line in Chen notation.

  • Partial participation: Participation is optional. Represented by a single line.

A weak entity lacks a complete key and depends on an owner entity through an identifying relationship. Its owner’s key normally becomes part of its own key in the relational schema.

Worked Example

Consider a university database containing:

  • STUDENT(StudentID, StudentName)

  • COURSE(CourseID, CourseTitle)

  • ENROLLMENT(StudentID, CourseID, Grade)

ENROLLMENT is a many-to-many relationship between STUDENT and COURSE. Grade belongs to the relationship because it describes a particular student’s enrollment in a particular course, rather than either entity independently.

StudentID StudentName
101 Asha
102 Ravi
CourseID CourseTitle
CS101 Database Systems
CS201 Operating Systems
StudentID CourseID Grade
101 CS101 A
102 CS101 B

Mapping ER Designs to Relational Tables

The ER model is transformed into relational tables as follows:

  • Each strong entity becomes a table.

  • A one-to-many relationship is usually implemented with a foreign key on the “many” side.

  • A one-to-one relationship can use a foreign key with a UNIQUE constraint.

  • A many-to-many relationship becomes a junction table containing foreign keys to both entity sets.

  • Relationship attributes become columns in that junction table.

  • A weak entity’s identifying relationship becomes foreign keys, often combined with its local key.

For the example, ENROLLMENT is represented by a table with the composite primary key (StudentID, CourseID).

Practical Considerations

PostgreSQL and MySQL/InnoDB do not natively create or maintain an ER model at runtime. They implement its rules using primary keys, foreign keys, UNIQUE and CHECK constraints, indexes, and sometimes triggers.

Multivalued attributes are usually normalized into separate tables, while derived attributes are calculated with queries, views, or application logic. The ER model is therefore best understood as a design and communication tool, while the relational schema and its constraints provide the implementation that the database engine enforces.

6

What are strong and weak entities in ER modeling?

A strong entity has a key that uniquely identifies each of its instances, while a weak entity has no complete key of its own and is identified through its owner entity’s key together with a partial key.

Read full answer

Applies toER modeling in all relational database management system versions; PostgreSQL 16 and MySQL 8.4 (InnoDB) as reference systems

Core Concepts

  • Strong entity: Has a key composed of its own attributes and can be identified independently of other entity types.

  • Weak entity: Has no complete key of its own. A partial key, also called a discriminator, distinguishes its instances only within a particular owner.

  • Owner entity: The strong entity whose key participates in identifying the weak entity.

  • Existence dependency: A weak entity cannot exist independently of its owner under the intended business rules.

  • Identifying relationship: Connects a weak entity to its owner and is normally mapped using a foreign key and an appropriate participation constraint.

A foreign key does not automatically make an entity weak. Weakness depends on the real-world meaning of the relationship, particularly whether the entity has an independent key and depends on its owner for existence.

Strong Versus Weak Entities

Property Strong entity Weak entity
Unique identification Identified by its own key Identified by owner key plus partial key
Relational primary key Derived from its own attributes Usually the owner’s key combined with the partial key
Existence May exist independently Depends on its owner
Foreign key May have one, but it is not needed for identification References the owner’s key and is required for identification
Identifying-relationship participation May be total or partial Normally total in the identifying relationship

Relational Mapping Example

Consider Employee and Dependent:

  • Employee is strong because employee_id uniquely identifies an employee.

  • Dependent is weak because a dependent is identified only in the context of an employee.

  • Assume dependent_no is unique among the dependents of one employee but may be reused for a different employee. It is therefore the partial key.

  • The complete relational key is (employee_id, dependent_no).

The conceptual mapping is:

Relation Attributes and constraints
employee employee_id is the primary key; employee_name is a normal attribute
dependent employee_id is a non-null foreign key referencing employee; dependent_no is the partial key; (employee_id, dependent_no) is the primary key

Example employee rows:

employee_id employee_name
101 Aarav Sharma
102 Meera Patel

Example dependent rows:

employee_id dependent_no dependent_name relationship
101 1 Riya Sharma Daughter
101 2 Aman Sharma Son
102 1 Kabir Patel Son

Here, dependent_no is the partial key, while (employee_id, dependent_no) forms the complete primary key.

Textbook Model Versus Real Database Systems

In the traditional Chen ER model, weak entities are represented explicitly using entity types, identifying relationships, double ovals for partial keys, and double lines for total participation. The identifying relationship may also be drawn with a double diamond.

PostgreSQL and MySQL InnoDB do not provide a native STRONG_ENTITY or WEAK_ENTITY declaration. Instead, the model is implemented through:

  • Primary-key constraints

  • Foreign-key constraints

  • NOT NULL constraints on owner references

  • Referential actions such as ON DELETE CASCADE

  • Application-level and business-rule validation

A non-null foreign key prevents a dependent from referring to a nonexistent employee. Whether deleting an employee also deletes the employee’s dependents is a separate design decision; cascading deletion is appropriate only when that matches the business rules.

Common Pitfalls

  • Foreign keys alone do not establish weakness: The same schema pattern can represent a strong entity if the child has an independent key and can exist without the parent.

  • Surrogate keys require careful interpretation: A globally unique surrogate key can identify a row independently, so the physical design no longer uses owner key plus partial key as its primary key. It does not remove any business-rule existence dependency, and conceptual weak or strong classification must still follow the entity’s semantics.

  • Weak does not mean unimportant: A weak entity can represent a central business concept.

  • Names are usually poor keys: Business identifiers or surrogate keys are generally preferable when names are not guaranteed to be unique or stable.

7

How do you map an ER diagram to relational tables?

Relational schema mapping converts the entities, attributes, relationships, keys, and cardinality constraints in an ER diagram into tables, primary keys (PK), and foreign keys (FK). The mapping preserves the diagram’s structure while applying relational-model and normalization principles.

Read full answer

Applies toDBMS (relational model; PostgreSQL 16 examples)

Mapping Rules

ER construct Relational representation
Strong entity A table containing the entity’s simple attributes and a primary key
Weak entity A table containing its partial key and an FK to its owner; use the owner’s key plus the partial key as the PK
1:1 relationship Place the PK of one entity as an FK in the other; making this FK UNIQUE enforces the 1:1 rule
1:N relationship Place the PK of the “1” side as an FK in the “N” side
M:N relationship Create a junction table containing FKs to both entities; usually their combination forms the PK
Multivalued attribute Create a separate table with an FK to the owner and the attribute value
Composite attribute Normally store its component attributes as separate columns
N-ary relationship Create an associative table containing an FK to each participating entity

NOT NULL represents mandatory participation. Optional participation generally permits NULL, although a separate relationship table is better when an entity can participate without a relationship.

Worked Example

Consider an ER model where:

  • A department employs many employees.

  • A department manages many projects.

  • An employee works on many projects, and a project has many employees.

The resulting schemas are:

  • department(department_id PK, name, budget)

  • employee(employee_id PK, email, name, department_id FK)

  • project(project_id PK, title, owning_department_id FK)

  • assignment(employee_id FK, project_id FK, allocation_pct, PK(employee_id, project_id))

The department to employee and department to project relationships are implemented with direct foreign keys. The M:N employee-project relationship requires assignment.

Code Example

The following PostgreSQL 16 schema implements the mapping and enforces the main constraints:

CREATE TABLE department (
    department_id INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
    name VARCHAR(100) NOT NULL UNIQUE,
    budget NUMERIC(12,2) NOT NULL CHECK (budget >= 0)
);

CREATE TABLE employee (
    employee_id INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
    email VARCHAR(255) NOT NULL UNIQUE,
    name VARCHAR(100) NOT NULL,
    department_id INTEGER NOT NULL,
    CONSTRAINT fk_employee_department
        FOREIGN KEY (department_id)
        REFERENCES department(department_id)
);

CREATE TABLE project (
    project_id INTEGER GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
    title VARCHAR(200) NOT NULL,
    owning_department_id INTEGER NOT NULL,
    CONSTRAINT fk_project_department
        FOREIGN KEY (owning_department_id)
        REFERENCES department(department_id)
);

CREATE TABLE assignment (
    employee_id INTEGER NOT NULL,
    project_id INTEGER NOT NULL,
    allocation_pct NUMERIC(5,2) NOT NULL
        CHECK (allocation_pct > 0 AND allocation_pct <= 100),
    PRIMARY KEY (employee_id, project_id),
    CONSTRAINT fk_assignment_employee
        FOREIGN KEY (employee_id)
        REFERENCES employee(employee_id),
    CONSTRAINT fk_assignment_project
        FOREIGN KEY (project_id)
        REFERENCES project(project_id)
);

INSERT INTO department (department_id, name, budget) VALUES
    (1, 'Engineering', 150000.00),
    (2, 'Sales', 90000.00);

INSERT INTO employee (employee_id, email, name, department_id) VALUES
    (10, 'alice@example.com', 'Alice', 1),
    (20, 'bob@example.com', 'Bob', 2);

INSERT INTO project (project_id, title, owning_department_id) VALUES
    (100, 'Atlas', 1),
    (110, 'CRM', 2);

INSERT INTO assignment (employee_id, project_id, allocation_pct) VALUES
    (10, 100, 80.00),
    (10, 110, 40.00),
    (20, 110, 100.00);

SELECT e.name AS employee, p.title AS project, a.allocation_pct
FROM assignment AS a
JOIN employee AS e ON e.employee_id = a.employee_id
JOIN project AS p ON p.project_id = a.project_id
ORDER BY e.name, p.title;

Result:

employee project allocation_pct
Alice Atlas 80.00
Alice CRM 40.00
Bob CRM 100.00

Best Practices and Pitfalls

  • Preserve candidate keys: Do not automatically make every attribute part of the PK; identify the attributes that uniquely identify each entity.

  • Apply normalization: After mapping, list functional dependencies and decompose repeating groups or redundant data into 3NF or BCNF relations where appropriate.

  • Model optionality carefully: A foreign key alone does not enforce total participation or prevent an entity from having multiple relationships in a 1:1 design.

  • Choose deletion behavior deliberately: Decide whether ON DELETE CASCADE, RESTRICT, or another action matches the business rules.

  • Match the database system: PostgreSQL enforces these foreign-key constraints directly. MySQL’s InnoDB engine also supports them, but uses AUTO_INCREMENT instead of PostgreSQL’s identity syntax; check constraints and accepted SQL syntax should also be verified against the selected MySQL version.

8

What do cardinality and participation constraints mean in ER modeling?

In ER modeling, cardinality constraints specify the maximum number of relationship instances with which an entity may be associated. Participation constraints specify the minimum participation—whether an entity must participate in the relationship or may remain uninvolved.

Read full answer

Applies todatabase management systems (general ER modeling; PostgreSQL 16 and MySQL 8.4 with InnoDB as reference systems)

Cardinality Constraints

Cardinality describes the maximum number of entities on the opposite side of a relationship that can be associated with one entity.

Cardinality Meaning Example
1:1 Each entity is associated with at most one entity on the other side An employee may be assigned one parking space, and a space may be assigned to at most one employee
1:N One entity can be associated with many entities on the other side A department can be associated with many employees
M:N Entities on both sides can be associated with many entities on the other side Students can enroll in many courses, and each course can have many students

In the textbook ER model, the cardinality ratio describes the maximum number of relationship instances in which an entity set may participate. Some ER and UML notations use min-max notation, such as (1,1) or (0,N), to represent both the minimum and maximum participation of each entity set.

Participation Constraints

Participation describes whether an entity is required to participate in a relationship:

  • Total participation: Every entity instance must participate in at least one relationship instance.

  • Partial participation: Some entity instances may participate, while others may have no relationship instance.

For example, if every employee must belong to a department but a department may have no employees, Employee has total participation and Department has partial participation.

Constraint Min-max representation Database interpretation
Optional participation (0,N) The entity may have no relationship instance
Mandatory participation (1,N) The entity must have at least one relationship instance
At most one association (0,1) or (1,1) The foreign-key column requires a UNIQUE constraint; (1,1) additionally requires NOT NULL

Worked ER Example

Consider a relationship in which:

  • Department manages Employee.

  • One department can manage many employees.

  • Each employee must belong to exactly one department.

  • A department may manage zero or more employees.

The relationship therefore has:

  • Cardinality ratio: Department:Employee = 1:N.

  • Department participation: partial, represented by (0,N).

  • Employee participation: total, represented by (1,1).

Illustrative department counts are:

Department Employee count
Engineering 2
Sales 1
Support 0

Best Practices and Pitfalls

  • Implement cardinalities explicitly: Put the foreign key on the many side of a 1:N relationship. For a 1:1 relationship, add a UNIQUE constraint to the foreign-key column.

  • Implement participation deliberately: Use a NOT NULL foreign key when every child must have a parent. Combined with the foreign-key constraint, this ensures both that the value is present and that it references an existing parent.

  • Do not confuse referential integrity with participation: A foreign key ensures that a referenced entity exists; it does not require every parent to have a child.

  • Handle M:N relationships with a junction table: Include foreign keys to both entity sets and normally use a composite primary key to prevent duplicate associations.

  • Recognize database limits: PostgreSQL and MySQL enforce keys, uniqueness, and nullability, but cross-entity or aggregate participation requirements may require triggers or application logic.

9

What are generalization, specialization, and aggregation in ER modelling?

Generalization and specialization are opposite operations for building an ISA hierarchy, while aggregation allows a relationship between entity sets to be treated as a higher-level abstraction. Together, these ER modelling extensions express real-world structures that basic ER diagrams cannot represent cleanly.

Read full answer

Applies toDBMS (ER/EER modelling, with PostgreSQL 16 and MySQL InnoDB as reference systems)

Core Differences

Concept Direction Purpose Typical ER construct
Specialization Top-down Divides a superclass into more specific subclasses ISA hierarchy
Generalization Bottom-up Combines entities with shared properties into a superclass ISA hierarchy
Aggregation Relationship abstraction Treats a relationship set as a higher-level entity for further relationships Relationship participating in another relationship

Generalization and specialization are therefore two perspectives on the same structure; they are not independent modelling techniques.

Specialization Example

Suppose PERSON has attributes PersonID and Name. Some persons are employees and others are customers:

  • EMPLOYEE has HireDate and Salary.

  • CUSTOMER has CreditLimit.

  • Both inherit PersonID and Name from PERSON.

  • ISA PERSON indicates that employee and customer are subtypes of person.

This specialization is partial because a person need not be an employee or customer. It is overlapping if an employee can also be a customer. Alternatively, the hierarchy could be disjoint if those categories are mutually exclusive.

Generalization Example

Consider two entity sets:

  • EMPLOYEE(EmployeeID, Name, HireDate)

  • CUSTOMER(CustomerID, Name, CreditLimit)

Because they share Name and conceptually represent different kinds of persons, they can be generalized into:

  • PERSON(PersonID, Name)

  • EMPLOYEE(PersonID, HireDate, Salary)

  • CUSTOMER(PersonID, CreditLimit)

The subtype tables use PersonID as both their primary key and a foreign key referencing PERSON. This eliminates duplication of shared attributes.

Specialization is normally performed from the domain model downward, while generalization is often used when existing entity definitions reveal common structure.

Aggregation Example

Assume these relationships exist:

  • EMPLOYEE works on PROJECT through WORKS_ON.

  • DEPARTMENT monitors particular work assignments.

MONITORS therefore does not relate only to an employee and a department; it relates a department to an employee’s assignment on a project. Aggregating WORKS_ON allows MONITORS to participate in the model.

A relational implementation might use:

  • WORKS_ON(EmployeeID, ProjectID, Hours)

  • MONITORS(DepartmentID, EmployeeID, ProjectID)

For example:

EmployeeID ProjectID Hours
E1 P10 20
DepartmentID EmployeeID ProjectID
D1 E1 P10

MONITORS references the employee-project combination representing the aggregated WORKS_ON relationship. Aggregation here is an EER concept; it is unrelated to SQL aggregate functions and differs from UML aggregation or composition.

Constraints and Design Choices

A specialization may specify:

  • Total participation: every superclass entity must belong to at least one subtype.

  • Partial participation: some superclass entities may belong to no subtype.

  • Disjointness: an entity can belong to at most one subtype.

  • Overlap: an entity can belong to multiple subtypes.

Subtype-specific constraints should be enforced by the database where practical. For example, PostgreSQL can use a CHECK constraint for a single-table discriminator design, while a multi-table design can use foreign keys and conditional triggers.

Trade-offs and Practical Guidance

  • Specialization avoids duplicated shared data and supports precise subtype attributes, but queries may require joins across superclass and subtype tables.

  • Generalization improves reuse and consistency, but an overly broad superclass can produce many null values or weak constraints.

  • Aggregation captures relationships involving relationships accurately, but increases schema and update complexity.

  • PostgreSQL and MySQL InnoDB do not directly implement EER generalization, specialization, or aggregation. They implement the resulting relational schema using primary keys, foreign keys, junction tables, discriminators, and constraints.

  • Prefer a multi-table hierarchy when subtype attributes are sparse or subtype rules are complex. A single-table hierarchy is simpler when most entities share the same attributes and a reliable discriminator exists.

10

How do superkeys, candidate keys, and primary keys differ?

A superkey is any set of attributes that uniquely identifies each row, a candidate key is a minimal superkey, and a primary key is the candidate key selected to identify rows officially. Every candidate key is a superkey, but only one candidate key is normally designated as the primary key.

Read full answer

Applies todatabase management systems (relational model; PostgreSQL 16 and MySQL 8.4 InnoDB)

Key Differences

Key type Uniquely identifies rows? Minimal set of attributes? Officially selected? May contain extra attributes?
Superkey Yes No No Yes
Candidate key Yes Yes It could be No
Primary key Yes Yes Yes No
  • Superkey: Any attribute or combination of attributes whose values uniquely identify each tuple in a relation. It may contain unnecessary attributes.

  • Candidate key: A superkey from which no attribute can be removed without losing uniqueness. A relation can have multiple candidate keys.

  • Primary key: One candidate key chosen as the relation’s official identifier. It is used by foreign keys and provides a stable target for relationships.

The hierarchy is therefore:

Superkey → Candidate key → Primary key

Worked Example

Consider a table recording student course registrations:

StudentID CourseID Email Score
101 CS101 alice@example.com 88
101 CS102 alice@example.com 91
202 CS101 bob@example.com 79

Assuming a student can register only once for a course:

  • {StudentID, CourseID} is a candidate key because it uniquely identifies each registration row.

  • {StudentID, CourseID, Email} is also a superkey, but it is not minimal because removing Email still preserves uniqueness.

  • If the schema designates {StudentID, CourseID} as the primary key, it is both a candidate key and the table’s primary key.

A composite key such as {StudentID, CourseID} is often necessary because neither StudentID nor CourseID alone uniquely identifies a registration.

SQL Representation

A primary key and an alternative candidate key can be enforced with SQL constraints. A PRIMARY KEY constraint both declares the selected candidate key and rejects NULL values in its columns. A UNIQUE constraint can enforce another candidate key when the relevant columns are also declared NOT NULL.

Because PostgreSQL and MySQL allow multiple NULL values in a UNIQUE constraint, an explicit NOT NULL constraint is necessary when a nullable column is intended to form an alternative candidate key.

Choosing a Primary Key

  • Prefer a natural key when its values are already stable, meaningful and guaranteed unique, such as an official registration number.

  • A surrogate key, such as an auto-generated integer or UUID, is often simpler and avoids changes to business identifiers.

  • Avoid columns that can change frequently because updates to primary-key values may also require updating referencing foreign keys.

  • Do not assume a foreign key must reference the primary key; SQL permits it to reference a UNIQUE candidate key.

  • PostgreSQL normally implements a primary key with a unique B-tree index, but the key does not determine physical row order.

  • MySQL InnoDB uses the primary key as its clustered-index key. Compact, sequential surrogate keys can therefore improve index locality, although larger keys such as UUIDs increase storage requirements.

11

What is a foreign key in relational databases?

A foreign key is a column or ordered set of columns in a relation that references a candidate key—normally a PRIMARY KEY or UNIQUE key—in another relation or the same relation. It enforces referential integrity by requiring matching child rows to reference existing parent rows, subject to defined null-handling and referential-action rules.

Read full answer

Applies todatabase management systems (PostgreSQL 16 and MySQL 8.0 with InnoDB)

Definition and Role

The referenced table is the parent table, and the table containing the foreign key is the child table:

  • The parent’s referenced key is usually its primary key or another unique candidate key.

  • The child’s foreign-key columns contain values copied from that parent key.

  • A parent row may be referenced by many child rows, while each child row references at most one parent row.

Foreign keys do not require the child values to be unique. For example, several employees may reference the same department. A relation may also contain a self-referencing foreign key, such as an employee.manager_id that references employee.employee_id.

How Referential Integrity Is Enforced

When a child row is inserted or updated, the DBMS checks that its foreign-key value corresponds to a row in the referenced parent table. Under the usual null-handling rules, a foreign key containing NULL need not reference a parent row.

The constraint is also checked when the referenced parent row is deleted or its key is updated. The declared referential action determines whether the operation is rejected, child rows are changed or deleted, or their foreign-key columns are set to NULL or a default.

Referencing a primary or unique candidate key is the portable approach because the referenced value must identify one parent row. Updating such a key is generally unnecessary because a stable, generated identifier can remain unchanged for the life of the row.

Concrete Example

Suppose department contains:

department_id name
1 Engineering
2 Sales

And employee contains a foreign key named department_id:

employee_id name department_id
101 Aisha 1
102 Rahul 2
103 Meera 1

Joining the tables on the foreign key produces:

employee_id name department_name
101 Aisha Engineering
102 Rahul Sales
103 Meera Engineering

An employee with department_id = 99 would be rejected because no matching department exists. If the foreign key were defined with ON DELETE SET NULL, deleting department 1 would set department_id to NULL for employees 101 and 103; those columns must therefore permit NULL.

Referential Actions

Action Referenced parent row is deleted Referenced key is updated Version behavior
NO ACTION Rejects the operation if it would leave dependent rows Rejects the operation if it would leave dependent rows PostgreSQL checks at statement end by default or transaction end when explicitly deferrable; MySQL/InnoDB treats it like RESTRICT
RESTRICT Rejects immediately Rejects immediately Supported by PostgreSQL and MySQL/InnoDB
CASCADE Deletes dependent child rows Updates dependent child foreign-key values Supported by PostgreSQL and MySQL/InnoDB
SET NULL Sets dependent foreign-key columns to NULL Sets dependent foreign-key columns to NULL Supported when the relevant columns allow NULL
SET DEFAULT Sets dependent foreign-key columns to their declared default Sets dependent foreign-key columns to their declared default Implemented by PostgreSQL 16; MySQL 8.0 parses this action but does not implement it for InnoDB

Constraints and Trade-offs

  • Composite foreign keys: Multiple child columns can reference a matching composite primary or unique key.

  • Null handling: Under PostgreSQL’s default MATCH SIMPLE behavior, a composite foreign key containing any NULL is not required to match a parent row. PostgreSQL’s MATCH FULL requires all foreign-key columns to be NULL or all to be non-NULL; MySQL/InnoDB does not implement MATCH FULL.

  • Indexing: PostgreSQL does not automatically index referencing columns, while MySQL/InnoDB automatically creates or reuses a suitable index for a foreign key.

  • Constraint versus join algorithm: A foreign key is a logical integrity rule, not a prescribed join algorithm. The query planner independently chooses how to execute a join.

  • Cascade risk: Cascading actions simplify maintenance but can modify or delete many rows unexpectedly. SET NULL may preserve dependent records while removing their relationship.

Best Practices and Common Pitfalls

  • Choose ON DELETE and ON UPDATE deliberately rather than using CASCADE merely to avoid constraint errors.

  • Prefer immutable primary keys; update-related cascades are rarely necessary.

  • Index foreign-key columns in PostgreSQL when they are frequently joined or checked.

  • Use RESTRICT or the default no-action behavior when accidental parent deletion should fail.

  • Remember that foreign keys enforce parent-child existence only. Additional static, row-local rules may use a CHECK constraint, while time-dependent or cross-row rules generally require triggers or application logic.

12

What are composite keys and surrogate keys in the relational model?

A composite key identifies a row using two or more attributes, while a surrogate key identifies a row using an artificial key that does not encode the row’s business attributes. Both are commonly used as primary keys, but they describe different properties: structure versus origin.

Read full answer

Applies toDBMS (relational model; PostgreSQL 16 and MySQL 8.0 InnoDB)

Composite Keys

A composite key is a key made from multiple attributes. No individual column in the key necessarily identifies a row by itself; their combination does.

For example, consider course enrollment:

student_id course_id enrolled_on
101 CS201 2025-01-15
101 CS301 2025-01-16
102 CS201 2025-01-17

If course_id identifies a particular course offering, (student_id, course_id) uniquely identifies each enrollment. It can therefore be used as the enrollment table’s composite primary key.

  • Uniqueness: The combination of all key columns must be unique.

  • Not null: In PostgreSQL and MySQL, primary-key columns must contain non-null values.

  • Foreign keys: Another table can reference the composite primary key as a whole.

  • Indexing: PostgreSQL 16 maintains a unique B-tree index on the primary-key columns, while MySQL InnoDB uses the primary key as its clustered index.

A composite key is especially useful when the real-world identity of an entity depends on a relationship between several stable attributes.

Surrogate Keys

A surrogate key is an artificial key that uniquely identifies a row without representing a business attribute. It is often implemented as a single generated column, although generation and assignment are design choices rather than requirements of the relational model.

The enrollment table could instead be designed as follows:

enrollment_id student_id course_id enrolled_on
1 101 CS201 2025-01-15
2 101 CS301 2025-01-16
3 102 CS201 2025-01-17

Here, enrollment_id is a surrogate key:

  • As the primary key in this design, it is unique and non-null.

  • It does not encode a business attribute.

  • Its value can be generated automatically rather than supplied by the user.

  • PostgreSQL 16 can use an identity column, which is backed by an internally managed sequence; MySQL InnoDB can use AUTO_INCREMENT.

  • It should be treated as immutable, although being a surrogate key does not automatically prevent updates.

For example, if an enrollment’s business student_id is corrected, that enrollment row must be updated, but tables referencing the enrollment through enrollment_id do not need to change.

Key Comparison

Property Composite key Surrogate key
Composition Two or more columns Often one generated column
Business meaning May reflect the entity’s natural identity Does not encode a business attribute
Example (student_id, course_id) enrollment_id
Changes when business data changes Key columns may need updating Should remain unchanged when treated as immutable
Storage May require a larger composite index Usually has a compact single-column index
Human readability Business attributes are visible directly Often requires another table to interpret the identifier
Generation Usually supplied by the application or source system; generated composite keys are possible Often generated by the DBMS; it may also be application-assigned

Composite and surrogate keys are not strictly opposites. A key can be both composite and generated, although that is uncommon because it combines a multi-column key with generated values.

Worked Example and Trade-offs

Suppose a university wants to prevent the same student from enrolling twice in the same course section. A sound composite primary key is:

(student_id, section_id)

The section_id is important because the same course may be offered in multiple sections or semesters. Using only (student_id, course_id) would incorrectly prevent enrollment in two sections if course_id identifies the catalog course rather than a particular section.

A surrogate alternative is:

enrollment_id, with UNIQUE (student_id, section_id)

This design keeps a compact primary-key index while enforcing the business rule through a separate unique constraint. PostgreSQL and MySQL both implement that constraint with a unique index.

Best Practices

  • Use a composite key when the business relationship itself defines uniqueness and the participating attributes are stable.

  • Use a surrogate key when business identifiers are lengthy, mutable, non-numeric, or awkward as foreign-key targets.

  • Do not assume a natural key such as email or student number is permanently unique; verify the business rule.

  • Prefer database-generated surrogate values when centralized generation is appropriate, while allowing standards-based application-generated UUIDs where distributed generation is required.

  • If a surrogate key is used, enforce the natural business rule separately with a UNIQUE constraint.

  • Avoid redundant indexes; UNIQUE (student_id, section_id) is not redundant with an enrollment_id primary key because their column sets differ.

13

How do integrity constraints protect relational database data?

Integrity constraints are declarative rules that ensure data stored in a relational database remains valid, consistent, and correctly related. The DBMS enforces these rules when affected rows are inserted, updated, or deleted rather than trusting every application to maintain correctness; PostgreSQL also permits some checks to be explicitly deferred until transaction end.

Read full answer

Applies torelational database management systems (PostgreSQL 16 and MySQL 8.0.16+/8.4 InnoDB)

Core Integrity Rules

The relational model defines three principal categories:

Constraint type Purpose Example
Entity integrity Identifies every row uniquely A student_id is a non-null primary key
Referential integrity Maintains relationships between tables Every non-null department_id references an existing department
Domain integrity Ensures each attribute contains an allowed value age must be greater than or equal to zero

These rules prevent problems such as duplicate identifiers, orphaned child records, invalid dates, and contradictory status values.

SQL Constraint Types

  • PRIMARY KEY: Uniquely identifies each row and prohibits null values in the key columns.

  • UNIQUE: Prevents duplicate values in a column or combination of columns. Multiple nulls may still be allowed unless NOT NULL is also specified.

  • NOT NULL: Requires a value in a column.

  • CHECK: Allows only rows satisfying a boolean expression, such as CHECK (age >= 0).

  • FOREIGN KEY: Links rows in a child table to a candidate key in a parent table.

  • Domain definitions: Column types such as INTEGER, VARCHAR(255), and DATE define the permitted representation of values.

A foreign key may permit nulls unless it is explicitly declared NOT NULL. Referential actions such as ON DELETE RESTRICT, ON DELETE CASCADE, or ON UPDATE CASCADE define what the DBMS should do when a referenced row is changed.

How Enforcement Works

The DBMS normally checks constraints while executing an affected INSERT, UPDATE, or DELETE, rather than waiting until the transaction commits. PostgreSQL 16 also supports deferrable PRIMARY KEY, UNIQUE, and FOREIGN KEY constraints; when such a constraint is deferred, its violation is detected at transaction end and the commit fails. MySQL InnoDB does not support deferrable constraints.

If enforcement fails, the database rejects the offending statement—or the commit for a deferred PostgreSQL constraint—and the transaction can be rolled back.

For example, inserting a student with a nonexistent department_id violates referential integrity. Deleting a referenced department may also be rejected when ON DELETE RESTRICT is used. With ON DELETE CASCADE, the related student rows would instead be removed automatically.

Constraints are therefore stronger than application-only validation because every client uses the same rules, including concurrent transactions and manual SQL statements.

Code Example

CREATE TABLE department (
    department_id INTEGER PRIMARY KEY,
    name VARCHAR(100) NOT NULL UNIQUE
);

CREATE TABLE student (
    student_id INTEGER PRIMARY KEY,
    email VARCHAR(255) NOT NULL UNIQUE,
    age INTEGER CHECK (age >= 0),
    department_id INTEGER,
    FOREIGN KEY (department_id)
        REFERENCES department (department_id)
        ON DELETE RESTRICT
        ON UPDATE CASCADE
);

INSERT INTO department (department_id, name)
VALUES (1, 'Computer Science'), (2, 'Electronics');

INSERT INTO student (student_id, email, age, department_id)
VALUES
    (101, 'asha@example.com', 20, 1),
    (102, 'ravi@example.com', 22, 2);

SELECT student_id, email, age, department_id
FROM student
ORDER BY student_id;

Result:

student_id email age department_id
101 asha@example.com 20 1
102 ravi@example.com 22 2

Attempting to insert (103, 'invalid@example.com', 19, 99) would fail because department 99 does not exist.

Best Practices and Pitfalls

  • Define constraints in the database schema so all applications inherit the same rules.

  • Use a stable primary key and avoid natural attributes that may change, such as an email address.

  • Pair CHECK conditions with NOT NULL when null is not a valid value. In SQL, a CHECK expression evaluating to UNKNOWN does not reject the row.

  • Choose foreign-key deletion actions deliberately; cascading deletes can remove many rows unexpectedly.

  • Use normalization to reduce data redundancy, while constraints protect relationships and permitted values.

  • PostgreSQL and modern MySQL InnoDB enforce CHECK constraints. MySQL versions before 8.0.16 parsed but did not enforce them.

14

What are the fundamental operations of relational algebra?

Relational algebra is a mathematical query language for manipulating relations, where each relation is a set of tuples with a defined schema. In the common six-operation textbook formulation, its fundamental operations are selection, projection, rename, union, difference, and Cartesian product; other operations are derived or extended forms.

Read full answer

Applies torelational algebra (all versions); PostgreSQL 16; MySQL 8.4 LTS with InnoDB

Relational Model

Relational algebra assumes each relation has:

  • Schema: A fixed set of attributes and their domains, such as Employee(EmpID, Name, DeptID, Salary).

  • Tuples: Rows containing one value for each attribute.

  • Set semantics: Duplicate tuples do not occur in the classical mathematical model.

  • Unordered rows: A relation has no inherent row order.

  • Atomic values: Each field contains one indivisible value in the basic textbook model.

Every relational-algebra operation produces another relation. This property is called the closure property.

Fundamental Operations

Using the common six-operation textbook formulation:

Operation Symbol Purpose SQL analogue
Selection σ Keeps tuples satisfying a predicate WHERE
Projection π Keeps selected attributes SELECT
Rename ρ Changes an attribute or relation name AS
Union ∪ Combines tuples from compatible relations UNION
Difference − Keeps tuples present in one relation but not the other EXCEPT
Cartesian product × Combines every tuple of one relation with every tuple of another CROSS JOIN

Some textbooks define only five fundamental operations and treat rename as an auxiliary operation. Set operations such as union and difference require relations with the same degree and compatible corresponding attribute domains.

Other commonly used operations are classified as follows:

Classification Operation Symbol Purpose SQL analogue
Derived Intersection ∩ Keeps tuples common to both relations INTERSECT
Derived Join ⋈ Combines related tuples from relations JOIN ... ON
Derived Division ÷ Finds tuples related to every tuple in another relation Usually expressed with subqueries or anti-joins
Extended Aggregation γ Groups tuples and computes functions such as SUM or AVG GROUP BY and aggregate functions

For example, intersection can be derived as R ∩ S = R − (R − S), while a join can be constructed using Cartesian product, selection, and projection.

Worked Example

Consider:

Employee(EmpID, Name, DeptID, Salary)

EmpID Name DeptID Salary
1 Asha 10 60000
2 Rahul 20 45000
3 Meera 10 75000

Department(DeptID, DeptName, Location)

DeptID DeptName Location
10 Engineering Bengaluru
20 Sales Mumbai

Select employees earning more than 50000, join them with their departments, and project the requested attributes:

π_{Name, DeptName, Location}(σ_{Employee.Salary > 50000}(Employee ⋈_{Employee.DeptID = Department.DeptID} Department))

The result is:

Name DeptName Location
Asha Engineering Bengaluru
Meera Engineering Bengaluru

The same operation can be expressed using Cartesian product, followed by selection for both the join condition and salary predicate, and then projection.

Relational Algebra and SQL

Relational algebra and SQL describe related operations, but they have different evaluation models:

  • Evaluation model: Relational algebra traditionally specifies a sequence of logical transformations, while SQL is declarative and leaves execution-plan selection to the optimizer.

  • Duplicate handling: Classical relational algebra uses set semantics, so projection removes duplicates. SQL generally uses bag semantics, so SELECT retains duplicates unless DISTINCT is specified.

  • Null values: Classical relational algebra usually assumes atomic, non-null values. SQL uses three-valued logic because NULL represents an unknown value.

  • Ordering: SQL can explicitly request ordered output with ORDER BY; classical relational algebra has no inherent ordering.

  • Derived and extended features: SQL exposes joins, grouping, aggregation, subqueries, and set operators that correspond to common relational-algebra extensions.

Textbook Model and Real Database Systems

PostgreSQL and MySQL with InnoDB do not literally execute textbook relational-algebra expressions. A submitted SQL query is generally:

  1. Parsed and analyzed for syntax, names, types, and semantic validity.

  2. Transformed and optimized using statistics, cost estimates, and available access paths.

  3. Executed using methods such as index scans, hash joins, merge joins, or nested-loop joins.

PostgreSQL may choose a hash join, merge join, or nested-loop plan. InnoDB may use index lookups to reduce the amount of data examined. Relational algebra describes the logical meaning of these transformations, while each database optimizer determines an efficient physical implementation.

15

How do relational algebra and relational calculus differ?

Relational algebra is a procedural language for transforming relations through operations such as selection, projection, and join. Relational calculus is a non-procedural, predicate-logic-based language that specifies which tuples must satisfy a condition.

Read full answer

Applies todatabase management systems (relational model; PostgreSQL 16 and MySQL 8.0.18 or later with InnoDB)

Core Distinctions

Aspect Relational algebra Relational calculus
Query style Procedural or operational Declarative or non-procedural
Main idea Specifies how to compute the result using relational operations Specifies what the result should contain using predicates and quantifiers
Typical operations Selection, projection, join, union, difference, Cartesian product Tuple and domain variables, predicates, ∀ and ∃
Logical foundation Operations over relations Predicate logic, especially first-order logic
Optimization Supports algebraic rewrites such as pushing selections before joins Relies more heavily on the query optimizer to choose an execution strategy
Closest SQL analogue The physical execution operators used by a DBMS resemble algebraic operations SQL’s declarative WHERE conditions are closer to tuple relational calculus

Both languages describe the same class of relational queries. Codd’s relational-equivalence theorem establishes that relational algebra and relational calculus have equivalent expressive power.

How Relational Algebra Works

A relational algebra expression represents an execution sequence over relations:

  • Selection σ: Filters tuples using a predicate.

  • Projection π: Chooses required attributes.

  • Join ⋈: Combines tuples from related relations according to a condition.

  • Union ∪: Combines tuples from compatible relations.

  • Difference −: Produces tuples found in one relation but not another.

  • Cartesian product ×: Combines every tuple from two relations.

Although the expression looks procedural, it does not necessarily prescribe the physical execution plan. An optimizer can rewrite equivalent algebraic expressions—for example, apply a selective filter before an expensive join.

How Relational Calculus Works

Relational calculus uses mathematical logic to characterize the tuples in the answer.

  • Tuple relational calculus: Uses tuple variables, attributes, predicates, and quantifiers. A typical formula has the form {t | P(t, ...)}.

  • Domain relational calculus: Uses domain variables, such as individual attribute values, to characterize the result.

  • Universal quantifier ∀: Requires the predicate to hold for every qualifying tuple.

  • Existential quantifier ∃: Requires the predicate to hold for at least one qualifying tuple.

Relational calculus does not specify the order in which data should be searched or joined. That responsibility belongs to the database optimizer.

Worked Example

Assume:

Employee(EmpID, EmpName, DeptID, Salary) contains (1, Alice, 10, 60000), (2, Bob, 20, 55000), and (3, Cara, 10, 40000).

Department(DeptID, DeptName) contains (10, Sales) and (20, HR).

The request is: return each employee earning more than 50000, together with the employee’s department name.

The relational algebra expression is π_{EmpName, DeptName}(σ_{Salary > 50000}(Employee) ⋈_{Employee.DeptID = Department.DeptID} Department).

The equivalent tuple relational calculus expression is {<t.EmpName, u.DeptName> | Employee(t) ∧ Department(u) ∧ t.DeptID = u.DeptID ∧ t.Salary > 50000}.

Both produce:

EmpName DeptName
Alice Sales
Bob HR

Relationship to SQL and Real Systems

SQL is declarative like relational calculus, but it is not a direct implementation of classical relational calculus:

  • Classical relational algebra and calculus generally use set semantics, while SQL uses bag semantics and can retain duplicate rows.

  • SQL supports NULL, aggregate functions, grouping, subqueries, and ORDER BY, which extend the classical model.

  • PostgreSQL and MySQL do not expose formal relational algebra or relational calculus interfaces. Instead, they parse declarative SQL and optimize it into an internal execution plan containing scans, joins, aggregates, and index operations.

For example, PostgreSQL may implement a join using a hash join, nested-loop join, or merge join. MySQL InnoDB may choose nested-loop, hash-join, or index-based strategies depending on available indexes, predicates, and optimizer decisions.

Interview Takeaway

Relational algebra answers “How can the result be derived?” through a sequence of relation operations. Relational calculus answers “Which tuples satisfy the requested conditions?” through logical predicates. SQL resembles relational calculus at the user level, while optimized database execution plans resemble relational algebra internally.

16

What is a functional dependency in the relational model?

A functional dependency is a rule stating that one set of attributes uniquely determines the values of another set. It is written as (X rightarrow Y), meaning that any two rows with the same values for (X) must also have the same values for (Y).

Read full answer

Applies torelational databases (PostgreSQL 16 and MySQL 8.0 InnoDB)

How It Works

For a relation schema ®, an attribute set (X) functionally determines (Y), written (X rightarrow Y), when the following holds for every valid instance of ®:

  • If two tuples have identical values for (X), they must have identical values for (Y).

Important terminology includes:

  • Determinant: The attribute set on the left side, such as StudentID in StudentID → StudentName.

  • Dependent attributes: The attributes on the right side, such as StudentName.

  • Nontrivial dependency: (X rightarrow Y) where (Y) is not already contained in (X).

  • Trivial dependency: (X rightarrow Y) where (Y) is contained in (X), such as {StudentID} → {StudentID}.

  • Attribute closure: The set of attributes functionally determined by (X), calculated by repeatedly applying known dependencies.

A functional dependency describes a rule for all valid data, not merely the rows currently stored. A sample table can disprove a dependency, but a small sample cannot prove that a dependency will always hold.

Concrete Example

Consider these STUDENT rows:

StudentID StudentName MajorID
1001 Asha 10
1002 Bilal 20
1003 Chen 10

Assume the schema stipulates that StudentID is unique. The relation then has the functional dependency:

StudentID → StudentName, MajorID

Each student identifier determines exactly one student name and major. A row with StudentID = 1001 but a different StudentName would violate this dependency and the uniqueness constraint.

Now consider ENROLLMENT:

StudentID CourseID Semester Grade
1001 CS101 2025 A
1001 CS201 2025 B
1002 CS101 2025 C
1002 CS201 2025 A
1003 CS101 2025 B

Assuming a student can enroll only once in a particular course during a semester, the dependency is:

(StudentID, CourseID, Semester) → Grade

However, StudentID → Grade cannot hold because student 1001 has both an A and a B. This distinction explains why composite keys are often necessary.

Role in Normalization

Functional dependencies are the formal basis of relational normalization:

  • Second Normal Form (2NF): Every non-prime attribute must be fully functionally dependent on every candidate key; it cannot depend on only part of a composite candidate key.

  • Third Normal Form (3NF): For every nontrivial dependency (X rightarrow A), either (X) is a superkey or (A) is a prime attribute.

  • BCNF: For every nontrivial dependency (X rightarrow Y), (X) must be a superkey.

A prime attribute is one that belongs to at least one candidate key.

For example, consider Enrollments(StudentID, CourseID, StudentName, Grade), where one row is permitted for each student-course pair and (StudentID, CourseID) is the candidate key. If it has:

StudentID → StudentName

(StudentID, CourseID) → Grade

then StudentName is partially dependent on the composite candidate key, so the relation violates 2NF. Decomposing it into Students(StudentID, StudentName) and Enrollments(StudentID, CourseID, Grade) removes that redundancy.

Enforcement in Real Systems

  • PostgreSQL 16 and MySQL 8.0 InnoDB: Primary keys and suitable non-null unique constraints enforce uniqueness of attribute combinations. A candidate key functionally determines every attribute in its relation, but ordinary SQL constraints do not directly enforce arbitrary functional dependencies.

  • Foreign keys: Enforce references between relations, but not arbitrary functional dependencies within a relation.

  • Query optimization: Optimizers may use uniqueness metadata and index information, but they do not automatically enforce every dependency expressed during schema design.

  • Denormalization: Real systems sometimes intentionally violate normalization to avoid expensive joins. Such redundancy must be managed carefully to prevent inconsistent values.

Common Pitfalls

  • Treating dependencies as facts inferred only from current rows.

  • Confusing a functional dependency with a foreign-key relationship.

  • Assuming (X rightarrow Y) means that (X) is always the table’s primary key; it may be a unique, composite, or alternate determinant.

  • Ignoring NULL semantics, since null values require careful treatment when reasoning about equality and uniqueness.

17

Which inference rules form the complete basis for functional dependencies in relational databases?

Armstrong’s axioms are a sound and complete set of rules for deriving functional dependencies in the relational model. They allow a database designer to determine which additional dependencies follow from a given set of dependencies.

Read full answer

Applies torelational database theory (version-independent); PostgreSQL 16 and MySQL 8.0 with InnoDB for implementation notes

Core Rules

For attribute sets (X), (Y), and (Z), Armstrong’s axioms are:

Axiom Formal rule Meaning
Reflexivity If (X subseteq Y), then (Y rightarrow X) A set determines all of its own attributes and any smaller subset.
Augmentation If (X rightarrow Y), then (XZ rightarrow YZ) Adding the same attributes to both sides preserves a dependency.
Transitivity If (X rightarrow Y) and (Y rightarrow Z), then (X rightarrow Z) Dependencies can be combined through a chain.

Here, (X rightarrow Y) means that X functionally determines Y: any two rows with the same X value must have the same Y value.

Worked Example

Consider an Employee relation:

EmployeeID DepartmentID DepartmentName
101 10 Sales
102 20 Engineering

The business rules imply:

  • EmployeeID → DepartmentID

  • DepartmentID → DepartmentName

Using transitivity:

  1. EmployeeID → DepartmentID

  2. DepartmentID → DepartmentName

  3. Therefore, EmployeeID → DepartmentName

Using augmentation, adding ProjectID to both sides gives EmployeeID, ProjectID → DepartmentID, ProjectID.

Using reflexivity, the relation also satisfies dependencies such as EmployeeID, DepartmentID → EmployeeID.

These derived dependencies can be found by computing an attribute closure, (X^+): start with X, then repeatedly add any attribute whose determinant is already contained in the closure.

Why Completeness Matters

Armstrong’s axioms provide two important guarantees:

  • Soundness: Every dependency derived using the axioms is logically implied by the original dependencies.

  • Completeness: Every dependency implied by the original set can be derived using these three axioms.

The resulting set of all implied dependencies is called the closure (F^+). This completeness guarantee applies to functional dependencies specifically; it does not directly cover multivalued dependencies or join dependencies.

Practical Use

During normalization, a designer typically:

  1. Lists the functional dependencies of a relation.

  2. Computes attribute closures to identify candidate keys.

  3. Tests whether a proposed primary key functionally determines all remaining attributes.

  4. Finds a minimal or canonical cover of the dependencies.

  5. Decomposes relations to remove redundancy and update anomalies.

For example, a dependency such as EmployeeID → DepartmentName may be logically implied even when it is not explicitly written in the business requirements.

Database-System Differences

PostgreSQL 16 and MySQL 8.0 with InnoDB enforce selected constraints, such as PRIMARY KEY, UNIQUE, and FOREIGN KEY, but they do not directly enforce arbitrary functional dependencies. A foreign key represents a referential relationship, not necessarily a general functional dependency. Also, SQL NULL values and their treatment by unique constraints must be considered when translating textbook dependency assumptions into a physical schema.

18

How do you compute attribute closure and derive candidate keys?

The attribute closure of an attribute set is every attribute functionally determined by that set under a given set of functional dependencies (FDs). A candidate key is a minimal superkey: its closure contains every relation attribute, but no proper subset has that property.

Read full answer

Applies torelational database theory; PostgreSQL 16; MySQL 8.0 (InnoDB); Python 3.13

Closure Algorithm

To compute (X^+), the closure of an attribute set (X):

  1. Initialize (X^+ = X).

  2. Examine each FD (A rightarrow B).

  3. If (A subseteq X^+), add every attribute in (B) to (X^+).

  4. Repeat step 3 until no new attribute can be added.

  5. If (X^+) contains every relation attribute, (X) is a superkey.

Only the left-hand side of an FD determines when its right-hand side may be added. Use the schema’s logical FDs, not merely values observed in a sample table.

Worked Example

Consider:

Enrollment(StudentID, CourseID, Grade, CourseTitle, Instructor, Department)

StudentID CourseID Grade CourseTitle Instructor Department
S1 C101 88 Database Alice CS
S2 C101 92 Database Alice CS
S3 C102 75 Operating Systems Bob CS

The business rules define these FDs:

  • {StudentID, CourseID} → Grade

  • CourseID → CourseTitle, Instructor

  • Instructor → Department

The relevant closures are:

  • StudentID+ = {StudentID}

  • CourseID+ = {CourseID, CourseTitle, Instructor, Department}

  • Instructor+ = {Instructor, Department}

  • {StudentID, CourseID}+ = {StudentID, CourseID, Grade, CourseTitle, Instructor, Department}

The final closure contains all attributes, so {StudentID, CourseID} is a superkey.

Deriving the Candidate Key

A superkey becomes a candidate key after checking that it is minimal:

  • Remove StudentID: CourseID+ does not contain every attribute.

  • Remove CourseID: StudentID+ does not contain every attribute.

Therefore, {StudentID, CourseID} is a candidate key.

The set {StudentID, CourseID, CourseTitle} also determines every attribute, but it is only a superkey because it contains the smaller superkey {StudentID, CourseID}.

This is the only candidate key under the stated FDs:

  • StudentID never appears on an FD’s right-hand side, so every candidate key must contain it.

  • Grade also never appears on the right-hand side, so every candidate key must determine it.

  • The only FD determining Grade requires both StudentID and CourseID.

Finding All Candidate Keys

A systematic approach is:

  1. Identify attributes that never appear on an FD’s right-hand side; they must belong to every candidate key.

  2. Build combinations containing those mandatory attributes and other plausible attributes.

  3. Compute each combination’s closure.

  4. Retain combinations whose closure contains the entire relation.

  5. Remove each constituent attribute in turn; reject the combination if any smaller set remains a superkey.

The brute-force implementation below examines attribute subsets. Its cost grows exponentially with the number of attributes, so larger schemas require pruning or smarter key-discovery algorithms.

Code Example

from itertools import combinations


def closure(attributes, fds):
    result = frozenset(attributes)

    while True:
        previous = result
        for left, right in fds:
            if left <= result:
                result |= right
        if result == previous:
            return result


def candidate_keys(attributes, fds):
    attributes = frozenset(attributes)
    keys = []

    for size in range(1, len(attributes) + 1):
        for combination in combinations(sorted(attributes), size):
            candidate = frozenset(combination)

            if closure(candidate, fds) != attributes:
                continue

            if all(
                closure(candidate - {attribute}, fds) != attributes
                for attribute in candidate
            ):
                keys.append(candidate)

    return keys


attributes = {
    "StudentID", "CourseID", "Grade",
    "CourseTitle", "Instructor", "Department"
}

fds = [
    (
        frozenset({"StudentID", "CourseID"}),
        frozenset({"Grade"}),
    ),
    (
        frozenset({"CourseID"}),
        frozenset({"CourseTitle", "Instructor"}),
    ),
    (
        frozenset({"Instructor"}),
        frozenset({"Department"}),
    ),
]

print("Closure:", sorted(closure({"StudentID", "CourseID"}, fds)))
print("Candidate keys:", [sorted(key) for key in candidate_keys(attributes, fds)])

# Closure: ['CourseID', 'CourseTitle', 'Department', 'Grade', 'Instructor', 'StudentID']
# Candidate keys: [['CourseID', 'StudentID']]

Database-System Considerations

PostgreSQL 16 and MySQL 8.0 with InnoDB do not maintain complete catalogs of logical FDs for automatic closure computation, so the dependency assumptions must normally be documented separately.

A declared primary key is a chosen unique, non-null superkey; it need not be minimal. Other candidate keys can be enforced with UNIQUE and NOT NULL constraints. Both systems permit multiple NULL values in a unique column by default, so NOT NULL is required for ordinary key semantics.

Primary keys are logical constraints, although InnoDB also uses the primary key as its clustered-index key. PostgreSQL creates a unique B-tree index for a primary key but does not require the table’s physical storage to be clustered by it. Foreign keys normally reference a primary key or another suitable unique key.

19

Why is normalization needed in relational database design?

Normalization is the process of organizing relational data into tables so each fact is stored appropriately, reducing redundancy and update anomalies while preserving the data’s meaning and dependencies. It is needed because duplicated or improperly related data can cause inconsistent results and insertion, update, and deletion anomalies.

Read full answer

Applies torelational database management systems; PostgreSQL 16 and MySQL 8.4 with InnoDB

Core Idea

In the relational model, every table represents a relation, every row represents a tuple, and a functional dependency describes a relationship between attributes. For example, if CustomerID → CustomerName, a customer identifier determines one customer name.

Normalization decomposes large or improperly structured relations into smaller relations based on their keys and functional dependencies. A good decomposition should be:

  • Lossless: joining the decomposed relations recreates the original information without creating incorrect matches.

  • Dependency-preserving: important functional dependencies can still be enforced using constraints within individual relations.

  • Anomaly-free: data is not unnecessarily repeated across multiple rows.

Common Normal Forms

  • First Normal Form (1NF): Every attribute contains an atomic value. Repeating groups such as Keyboard, Mouse must be separated into rows.

  • Second Normal Form (2NF): The relation is in 1NF, and every non-prime attribute depends on the entire candidate key, not only part of a composite key.

  • Third Normal Form (3NF): For every nontrivial functional dependency X → A, X must be a superkey or A must be a prime attribute. In practical terms, non-key attributes should not depend transitively on the key.

  • BCNF: Every nontrivial functional dependency has a superkey as its determinant. It is stricter than 3NF for some dependency structures.

  • Higher forms such as 4NF and 5NF address multivalued and join dependencies, but are used less frequently.

Concrete Normalization Example

Consider these 1NF relations:

OrderID CustomerID CustomerName OrderDate
1001 C10 Ada 2025-01-05
1002 C11 Lin 2025-01-06
1003 C10 Ada 2025-01-07

The functional dependencies are:

  • OrderID → CustomerID, OrderDate

  • CustomerID → CustomerName

OrderID is the candidate key. Because CustomerName depends on CustomerID, which depends on OrderID, the table has a transitive dependency and is not in 3NF.

Now consider the order-line relation:

OrderID ProductID ProductName CatalogPrice Quantity
1001 P20 Keyboard 49.00 2
1001 P30 Mouse 19.50 1
1002 P30 Mouse 19.50 4

Its candidate key is (OrderID, ProductID), while:

  • (OrderID, ProductID) → Quantity

  • ProductID → ProductName, CatalogPrice

ProductName and CatalogPrice depend only on part of the composite key, so this relation is not in 2NF.

Decomposition Steps

  1. Apply 2NF to the order-line relation:

  2. Products(ProductID, ProductName, CatalogPrice)

  3. OrderLines(OrderID, ProductID, Quantity)

The join is lossless because the common attribute ProductID is the key of Products.

  1. Apply 3NF to the order relation:

  2. Customers(CustomerID, CustomerName)

  3. Orders(OrderID, CustomerID, OrderDate)

The join is lossless because CustomerID is the key of Customers.

The resulting rows are:

Relation Rows
Customers (C10, Ada), (C11, Lin)
Orders (1001, C10, 2025-01-05), (1002, C11, 2025-01-06), (1003, C10, 2025-01-07)
Products (P20, Keyboard, 49.00), (P30, Mouse, 19.50)
OrderLines (1001, P20, 2), (1001, P30, 1), (1002, P30, 4)

Anomalies Prevented

Before decomposition, the original design could not cleanly store a customer without an order. It could also produce inconsistent customer names when one row was updated, or delete a customer’s details when their last order was removed.

After decomposition:

  • Customers and products can exist independently of orders.

  • A customer name is updated in one place.

  • Deleting an order does not remove unrelated customer or product data.

  • Primary-key, UNIQUE, NOT NULL, and foreign-key constraints can enforce the intended relationships.

Trade-offs and Practical Guidance

Normalization improves consistency but can require additional joins, so read-heavy systems may deliberately use denormalization, materialized views, or caching after establishing a sound logical model. Both PostgreSQL and MySQL InnoDB support normalized designs but do not automatically detect every normalization violation; developers must define the appropriate keys and constraints.

Physical storage also differs from the textbook model: PostgreSQL commonly stores rows in a heap and uses separate indexes, while InnoDB organizes table data around the clustered primary key. This affects index size and join performance, but not the logical principles of normalization.

For historical orders, the price actually charged should normally be stored in OrderLines as a transaction-time snapshot rather than obtained from the current Products catalog price.

20

What is first normal form in relational databases?

First normal form (1NF) requires each attribute to contain one atomic value, with respect to its domain, and prohibits repeating groups within a relation. It is the minimum normalization level in the relational model.

Read full answer

Applies torelational database fundamentals (all versions); PostgreSQL 16; MySQL 8.4 InnoDB

First Normal Form Requirements

A relation is in 1NF when:

  • Each non-NULL attribute value is indivisible with respect to the operations performed on that attribute.

  • A varying number of related facts is represented by separate rows rather than by repeating column groups.

  • The same value may occur in multiple rows; repetition of values is not itself a 1NF violation.

  • SQL NULL, which represents the absence of a value rather than an atomic value itself, does not automatically violate 1NF.

“Atomic” is domain-relative. It does not necessarily mean that the value must use a primitive storage type, although scalar columns such as integer, date, and varchar usually produce the clearest relational design.

The relational model already provides named attributes, domains, and tuples. Designing each row to represent one fact is an important modeling convention, but atomicity and the absence of repeating groups are what specifically distinguish 1NF.

Unnormalized Example

Consider an employee record with two numbered project groups:

employee_id employee_name department_id department_name project_1_code project_1_name project_2_code project_2_name
1 Alice 10 Engineering P101 Apollo P102 Artemis
2 Bob 20 Sales P101 Apollo NULL NULL

This structure is not in 1NF because the numbered project columns form repeating groups. It limits each employee to two projects and would require adding project_3, project_4, and further columns as the number of projects grows.

The individual project_1_code and project_1_name values are atomic; the violation comes from repeating the project structure across numbered column groups.

Functional Dependencies and Decomposition

Assume:

  • An employee has one name and belongs to one department.

  • A department has one name.

  • A project code identifies one project.

  • An employee may participate in multiple projects.

  • An employee participates at most once in a particular project; otherwise an additional attribute such as assignment_id would be needed in the key.

Under these rules, the functional dependencies are:

  • employee_id → employee_name, department_id

  • department_id → department_name

  • project_code → project_name

  • employee_id → department_name follows transitively.

Step 1 — Remove the repeating groups:

  • Employee_Department(employee_id, employee_name, department_id, department_name)

  • Project(project_code, project_name)

  • Employee_Project(employee_id, project_code)

The assignment relation becomes:

employee_id project_code
1 P101
1 P102
2 P101

Each cell now contains one value, and each employee-project assignment occupies its own row. Employee_Department is still in 1NF even though it contains a transitive dependency.

Step 2 — Remove the transitive dependency:

  • Employee(employee_id, employee_name, department_id)

  • Department(department_id, department_name)

  • Project(project_code, project_name)

  • Employee_Project(employee_id, project_code)

Assuming no functional dependencies beyond those stated, this design also satisfies 3NF and BCNF. That higher-normal-form cleanup is not required merely to achieve 1NF.

Practical Guidance and System Differences

  • Represent a many-to-many relationship with a junction table such as employee_project, rather than numbered columns or comma-separated values.

  • PostgreSQL 16 supports ARRAY and JSON types, while MySQL 8.4 supports JSON but has no native general-purpose ARRAY type. A list can be one SQL value, but storing independently meaningful business facts inside it often violates the intended atomicity and makes joins, foreign keys, and indexing less effective.

  • PostgreSQL and MySQL InnoDB do not validate the business-level atomicity of a column; schema and application design remain responsible for normalization.

  • Normalization reduces redundancy and update anomalies but can require additional joins. Intentional denormalization or JSON documents may improve selected read workloads, at the cost of update flexibility and referential integrity.

21

What is 2NF and partial dependency in relational databases?

Second normal form (2NF) is a normalization level in which every non-key attribute depends on the entire candidate key, not merely part of it. A partial dependency exists when a non-prime attribute functionally depends on only a proper subset of a composite candidate key.

Read full answer

Applies torelational database normalization concepts (all versions); PostgreSQL 16 and MySQL 8 with InnoDB

Core Concepts

  • Candidate key: A minimal set of attributes that uniquely identifies each relation row.

  • Prime attribute: An attribute belonging to any candidate key.

  • Non-prime attribute: An attribute that is not part of any candidate key.

  • Composite key: A candidate key containing two or more attributes.

  • Full functional dependency: For a dependency X → Y, no proper subset of X determines Y; in 2NF this is applied to non-prime attributes and candidate keys.

  • Partial dependency: A non-prime attribute functionally depends on a proper subset of a composite candidate key.

A relation is in 2NF if:

  1. It is already in first normal form (1NF): each attribute holds a single atomic value under its domain, and there are no repeating groups.

  2. For every candidate key, every non-prime attribute is fully functionally dependent on that key.

For example, suppose StudentID and CourseID together form the candidate key. If StudentName depends only on StudentID, then StudentName has a partial dependency on the key.

Partial-Dependency Example

Consider this Enrollment relation:

StudentID CourseID StudentName CourseTitle Grade
S1 C101 Alice Database Systems 88
S1 C102 Alice Algorithms 91
S2 C101 Bob Database Systems 85
S2 C102 Bob Algorithms 78

The important functional dependencies are:

  • {StudentID, CourseID} → Grade

  • {StudentID} → StudentName

  • {CourseID} → CourseTitle

The candidate key is {StudentID, CourseID}.

The dependencies violate 2NF because:

  • StudentName depends only on part of the key: StudentID.

  • CourseTitle depends only on part of the key: CourseID.

This creates update anomalies. For example, changing Alice’s name might require updating multiple rows, while storing course titles repeatedly can produce inconsistent values.

Decomposition Into 2NF

Separate each non-prime attribute with a partial dependency into a relation whose candidate key is the proper subset that determines it. In this example, those determining subsets are single attributes.

Student

StudentID StudentName
S1 Alice
S2 Bob

Course

CourseID CourseTitle
C101 Database Systems
C102 Algorithms

Enrollment

StudentID CourseID Grade
S1 C101 88
S1 C102 91
S2 C101 85
S2 C102 78

In the decomposed design:

  • Student has candidate key StudentID.

  • Course has candidate key CourseID.

  • Enrollment has composite candidate key {StudentID, CourseID}.

  • Grade depends on the complete key {StudentID, CourseID}.

  • No non-prime attribute has a partial dependency.

The decomposition is lossless because StudentID determines Student and CourseID determines Course; joining these relations to Enrollment on their candidate keys cannot create spurious tuples. It also preserves the original functional dependencies.

2NF Compared with Other Normal Forms

Normal form Main requirement Example of violation
1NF Attributes contain atomic values and no repeating groups A cell stores multiple phone numbers
2NF No partial dependency on a composite candidate key StudentName depends only on StudentID
3NF No prohibited transitive dependency of non-prime attributes EmployeeID → DepartmentID → DepartmentName

In the 3NF example, if EmployeeID is the candidate key of an employee relation and DepartmentName depends on the non-key attribute DepartmentID, then DepartmentName transitively depends on EmployeeID.

2NF does not prevent every anomaly. A relation can satisfy 2NF but violate 3NF when a non-prime attribute determines another non-prime attribute and the determinant is not a superkey.

Practical Guidance

  • Check every candidate key: If a table has multiple candidate keys, examine each one.

  • Single-attribute keys: A relation whose candidate keys are all single-attribute is automatically in 2NF once it is in 1NF.

  • Use foreign keys: In the decomposed schema, Enrollment.StudentID references Student, and Enrollment.CourseID references Course.

  • Do not rely on automatic enforcement: PostgreSQL 16 and MySQL 8 with InnoDB enforce declared PRIMARY KEY, UNIQUE, and FOREIGN KEY constraints, but they do not automatically verify that a table satisfies 2NF.

  • Prefer 3NF or BCNF for transactional schemas: 2NF is often an intermediate step. Most production database designs proceed beyond it to eliminate transitive dependencies and further reduce update anomalies.

22

What is third normal form in relational databases?

Third normal form (3NF) is a relational normalization property in which every non-key attribute is non-transitively dependent on the candidate key. Formally, for every nontrivial functional dependency X → A, either X is a superkey or A is a prime attribute; every relation in 3NF also satisfies 2NF.

Read full answer

Applies torelational database normalization (PostgreSQL 16 and MySQL 8.4 InnoDB as reference systems)

Core Definition and Terminology

The formal 3NF condition is:

For every nontrivial functional dependency X → A, X must be a superkey, or A must be a prime attribute.

The relevant terms are:

  • Candidate key: A minimal superkey that cannot be reduced while still uniquely identifying a row.

  • Superkey: A set of attributes that uniquely identifies each row, although it need not be minimal.

  • Prime attribute: An attribute belonging to at least one candidate key.

  • Non-prime attribute: An attribute belonging to no candidate key.

  • Nontrivial dependency: A dependency X → A in which A is not already contained in X.

The condition primarily eliminates dependencies of non-prime attributes on other non-key attributes.

Transitive-Dependency Example

Consider an Enrollment relation:

StudentID CourseID TutorID TutorName
1 10 7 Dr. Rao
2 10 8 Dr. Shah
1 11 7 Dr. Rao

Given the following complete set of functional dependencies:

  • (StudentID, CourseID) → TutorID

  • TutorID → TutorName

The candidate key is (StudentID, CourseID). By transitivity:

  • (StudentID, CourseID) → TutorName

Here, TutorID is not a superkey, and TutorName is a non-prime attribute because it does not belong to any candidate key. Therefore, the relation violates 3NF.

The relation is in 2NF because its non-prime attributes depend on the whole composite candidate key rather than on either proper subset of that key.

Step-by-Step Decomposition

Decompose the original relation into:

  1. Tutor

  2. TutorID — primary key

  3. TutorName

  4. Enrollment

  5. StudentID

  6. CourseID

  7. TutorID

  8. Primary key: (StudentID, CourseID)

  9. Foreign key: TutorID referencing Tutor(TutorID)

This decomposition is:

  • Lossless: The intersection attribute, TutorID, functionally determines the entire Tutor relation, so joining the decomposed relations reconstructs the original rows without creating false matches.

  • Dependency-preserving: The dependency TutorID → TutorName can still be enforced directly within Tutor.

  • Anomaly-reducing: A tutor’s name is stored once rather than being repeated for every enrollment.

3NF, BCNF, and Practical Trade-offs

Property 3NF BCNF
Condition for every nontrivial X → A X is a superkey or A is prime X must be a superkey
Permits some dependencies involving prime attributes Yes No
Strictness Standard practical normalization target Stricter than 3NF
  • Benefit: 3NF reduces update anomalies, insertion anomalies, and duplicated facts.

  • Cost: Joining normalized relations can add query complexity and, in some workloads, runtime cost.

  • Automatic enforcement: PostgreSQL 16 and MySQL 8.4 InnoDB do not detect functional dependencies or verify that tables are in 3NF. They enforce only constraints declared in the schema, such as primary-key, unique, and foreign-key constraints.

  • Practical guidance: 3NF or BCNF is a common default for transactional schemas. Intentional denormalization can be appropriate for reporting or read-heavy workloads when its consistency and maintenance costs are explicitly managed.

23

How does Boyce–Codd normal form differ from 3NF?

Boyce–Codd normal form (BCNF) requires every determinant of a nontrivial functional dependency to be a superkey. Third normal form (3NF) is weaker because it also permits a dependency whose right-hand side is a prime attribute, even when the determinant is not a superkey.

Read full answer

Applies torelational database design (PostgreSQL 16 and MySQL 8.0 with InnoDB)

Concrete Relation

Consider a university relation where each instructor teaches one course, but a course may have multiple instructors:

Student Course Instructor
S1 C101 I1
S2 C101 I1
S2 C102 I2

Assume the following business rules:

  • {Student, Course} → Instructor

  • Instructor → Course

These are functional dependencies (FDs) based on the organization’s rules; they should not be inferred from only the sample rows.

The candidate keys are:

  • {Student, Course}

  • {Student, Instructor}

Therefore, Student, Course, and Instructor are all prime attributes because each belongs to at least one candidate key.

Formal Definitions

For a relation schema R and a set of functional dependencies F:

  • Superkey: a set of attributes that functionally determines every attribute in R.

  • Candidate key: a minimal superkey.

  • Prime attribute: an attribute belonging to at least one candidate key.

  • Nontrivial FD: X → A, where A is not already contained in X.

A relation is in:

  • 3NF if, for every nontrivial FD X → A, either:

  • X is a superkey, or

  • A is a prime attribute.

  • BCNF if, for every nontrivial FD X → A in the dependency closure, X is a superkey.

These tests apply to every projected dependency, not only those explicitly listed in F.

Why the Relation Is 3NF but Not BCNF

Dependency Is the determinant a superkey? Is the RHS prime? 3NF BCNF
{Student, Course} → Instructor Yes Yes Pass Pass
Instructor → Course No Yes, Course is prime Pass Fail

The dependency Instructor → Course violates BCNF because Instructor alone does not determine Student and therefore is not a superkey.

It satisfies 3NF because the right-hand-side attribute, Course, is prime. Thus, every BCNF relation is in 3NF, but a 3NF relation need not be in BCNF.

BCNF Decomposition

To remove the violating dependency, decompose the relation into:

  • R1(Student, Instructor)

  • R2(Instructor, Course)

The resulting rows are:

R1

Student Instructor
S1 I1
S2 I1
S2 I2

R2

Instructor Course
I1 C101
I2 C102

Both relations are in BCNF:

  • R1 has no projected nontrivial FD that violates BCNF.

  • In R2, Instructor is a candidate key and therefore a superkey for the dependency Instructor → Course.

The decomposition is lossless because the intersection is Instructor, which determines all of R2; joining the relations cannot produce additional valid combinations.

However, it is not dependency-preserving here: {Student, Course} → Instructor cannot be enforced using only the local constraints of R1 and R2. A real implementation could retain the 3NF design, enforce this dependency with additional application logic or a trigger, or accept controlled redundancy.

Trade-offs and Implementation

  • BCNF: Provides a stricter dependency structure and reduces update anomalies caused by non-key determinants. The standard BCNF decomposition algorithm guarantees a lossless decomposition, but the result is not always dependency-preserving and can require additional joins.

  • 3NF: Often offers a better balance between normalization, dependency preservation, and query cost. A standard 3NF synthesis procedure can produce a lossless, dependency-preserving decomposition.

  • Textbook versus real systems: Normalization is a logical-design technique based on a chosen set of functional dependencies. PostgreSQL and MySQL/InnoDB do not automatically label a table as 3NF or BCNF or reject redundant schemas.

  • Practical guidance: Use BCNF when its stricter structure and reduced anomalies justify the join cost. Retain 3NF or deliberately denormalize when preserving important dependencies or avoiding frequent joins is more valuable.

24

What are 4NF and 5NF in relational database design?

Fourth normal form (4NF) removes redundancy caused by independent multivalued dependencies, while fifth normal form (5NF) removes redundancy caused by nontrivial join dependencies. Both use dependency-aware decomposition, normally with a lossless join.

Read full answer

Applies torelational database normalization (all versions; PostgreSQL 16 and MySQL 8.4 InnoDB as reference systems)

Core Definitions

Form Requirement Problem addressed
4NF For every nontrivial multivalued dependency (X twoheadrightarrow Y), (X) must be a superkey of the relation Independent repeating facts create redundant combinations
5NF For every nontrivial join dependency (*{R_1,ldots,R_n}), each (R_i) must be a superkey A multiway relationship can require overlapping binary projections

A multivalued dependency (X twoheadrightarrow Y) means that, for a fixed (X), the values of (Y) are independent of the remaining attributes. A join dependency means that joining particular projections reconstructs the original relation. A superkey determines every attribute of the relation.

Both forms are stronger than BCNF, and 5NF implies 4NF.

4NF Example

Consider StudentHobbySport:

student_id hobby sport
1 Reading Tennis
1 Reading Football
1 Running Tennis
1 Running Football

The multivalued dependencies are:

  • student_id ->> hobby

  • student_id ->> sport

Neither student_id -> hobby nor student_id -> sport holds because the student has multiple hobbies and sports. The hobby and sport collections are independent, so student_id is not a superkey and the relation violates 4NF.

Decomposing it produces:

StudentHobby

student_id hobby
1 Reading
1 Running

StudentSport

student_id sport
1 Tennis
1 Football

Joining them on student_id returns:

student_id hobby sport
1 Reading Tennis
1 Reading Football
1 Running Tennis
1 Running Football

The decomposition is lossless because it reproduces every original row without invalid combinations.

5NF Example

Consider SupplierPartProject, where the business rule is: if a supplier supplies a part, the supplier supplies a project, and the project uses that part, then the supplier supplies that part to that project.

supplier part project
S1 P1 J1
S1 P1 J2
S1 P2 J1
S2 P1 J1

There are no nontrivial functional dependencies, so the only candidate key is all three columns, and the relation is in BCNF and 4NF. However, the business rule creates a join dependency over three projections:

SupplierPart

supplier part
S1 P1
S1 P2
S2 P1

SupplierProject

supplier project
S1 J1
S1 J2
S2 J1

PartProject

part project
P1 J1
P1 J2
P2 J1

Joining SupplierPart with PartProject on part produces five rows, including the spurious row (S2, P1, J2). Joining that result with SupplierProject removes it, because (S2, J2) is not in SupplierProject, and leaves exactly the original four rows. The relation therefore satisfies the join dependency *{SupplierPart, SupplierProject, PartProject}, which is not implied by its key, so it is not in 5NF. Storing the three binary tables instead puts the design in 5NF.

No two of the three projections are enough on their own; all three are required to rebuild the relation without spurious rows.

Lossless Decomposition and Trade-offs

A normalization decomposition should normally be lossless: joining its result must reproduce the original information without extra or missing rows.

  • 4NF commonly handles independent repeating collections such as hobbies, tags, or phone numbers.

  • 5NF is rarer because it requires explicit, well-understood multiway join dependencies.

  • Excessive decomposition can require more joins, complicate queries, and make some dependencies harder to enforce locally.

  • A lossless decomposition does not automatically guarantee preservation of every dependency.

Practical Guidance

  • Normalize progressively through 1NF, 2NF, 3NF, BCNF, 4NF, and 5NF.

  • Base dependencies on business rules, not only on patterns visible in current rows.

  • PostgreSQL and MySQL do not detect normal forms or automatically normalize tables. They enforce declared constraints such as primary keys, unique constraints, and foreign keys.

  • Design relations in 4NF for independent repeating collections; require 5NF only when a multiway relationship has a demonstrable, lossless decomposition.

25

What are insertion, update, and deletion anomalies in DBMS?

Insertion, update, and deletion anomalies are data-consistency problems caused by storing facts together in one relation. They make it difficult to insert, modify, or delete information without unintentionally affecting unrelated data.

Read full answer

Applies torelational DBMS concepts (all versions), with PostgreSQL 16 and MySQL 8.4 with InnoDB as reference systems

Anomalies Explained

Anomaly Problem Cause
Insertion anomaly A valid fact cannot be stored without inserting an unrelated or unwanted fact. Unrelated entities are stored in the same relation.
Update anomaly One logical change must be repeated across multiple rows. The same fact is stored redundantly.
Deletion anomaly Deleting one fact unintentionally removes another fact. The relation mixes facts with different dependencies.

Concrete Example

Suppose this relation stores student, enrollment, course, instructor, and instructor-office information:

StudentID StudentName CourseID CourseName InstructorID InstructorOffice
1 Alice C1 Database Systems I1 Office-A
2 Bob C1 Database Systems I1 Office-A
3 Carol C2 Operating Systems I2 Office-B

Assuming each course has one instructor, the relevant functional dependencies are:

  • StudentID → StudentName

  • CourseID → CourseName, InstructorID

  • InstructorID → InstructorOffice

  • (StudentID, CourseID) identifies an enrollment

Insertion Anomaly

A student who has not enrolled in a course cannot be stored without inventing course information or using nulls. Similarly, a new instructor cannot be recorded until the instructor is assigned to a course that has an enrolled student.

Update Anomaly

If instructor I1 moves from Office-A to Office-C, both rows containing I1 must be updated. Updating only one row produces contradictory office information.

Deletion Anomaly

If Carol’s enrollment in C2 is deleted, the only row containing instructor I2 may also be deleted. This incorrectly removes the facts that I2 teaches C2 and works in Office-B.

Normalization Remedy

Decomposing the original relation produces the following relations:

Relation Columns and constraints Sample rows
Student StudentID primary key; StudentName (1, Alice), (2, Bob), (3, Carol)
Course CourseID primary key; CourseName; InstructorID foreign key (C1, Database Systems, I1), (C2, Operating Systems, I2)
Instructor InstructorID primary key; InstructorOffice (I1, Office-A), (I2, Office-B)
Enrollment Composite primary key (StudentID, CourseID); both columns are foreign keys (1, C1), (2, C1), (3, C2)

This decomposition:

  • Allows a student to be inserted independently in Student.

  • Stores each instructor’s office once in Instructor.

  • Prevents deleting an enrollment from deleting instructor or course facts.

  • Represents enrollment through the composite key (StudentID, CourseID).

Normalization and Functional Dependencies

Normalization reduces redundancy by ensuring that non-key attributes depend on the appropriate key.

  • Second Normal Form (2NF): Removes partial dependencies. For example, StudentName depends on StudentID, not on part of the composite enrollment key.

  • Third Normal Form (3NF): Removes transitive dependencies. In the original relation, InstructorOffice depends on InstructorID, while InstructorID depends on CourseID.

  • BCNF: Requires every nontrivial functional dependency to be determined by a candidate key and is stronger than 3NF.

For the listed dependencies, the decomposed design is in BCNF: each non-key attribute in Student, Course, and Instructor depends on that relation’s candidate key, while Enrollment contains only its composite key.

Trade-offs and Real-System Behavior

Normalization improves consistency and maintenance, but it can require additional joins and make some read queries more complex. Some systems deliberately denormalize for performance, provided that the resulting redundancy is controlled and consistency is maintained through application logic, constraints, or other mechanisms.

PostgreSQL and MySQL/InnoDB do not automatically normalize tables. They provide constraints such as PRIMARY KEY, FOREIGN KEY, and UNIQUE, while transactions and locking help maintain consistency. The database designer remains responsible for identifying functional dependencies and choosing an appropriate schema.

26

What distinguishes lossless join decomposition from dependency preservation?

A lossless join decomposition divides a relation so that joining its components reconstructs the original relation without losing or inventing tuples. Dependency preservation ensures that the original functional dependencies can still be enforced using constraints on the individual components, without joining them.

Read full answer

Applies toDBMS (relational model; PostgreSQL 16 and MySQL 8.0/InnoDB)

Core Definitions

  • Lossless join decomposition: For a decomposition of relation ® into (R_1, R_2, ldots), their natural join must produce exactly the information in ®.

  • No legitimate tuple is lost.

  • No spurious tuple, created by combining unrelated records, is introduced.

  • For a binary decomposition of (r) into (R_1) and (R_2), the standard textbook condition is that the intersection (R_1 cap R_2) functionally determines at least one side: [ (R_1 cap R_2) rightarrow R_1 quadtext{or}quad (R_1 cap R_2) rightarrow R_2 ]

  • Dependency preservation: If the original dependency set is (F), and the projected dependency sets are (F_1, F_2, ldots), the decomposition is dependency-preserving when: [ (F_1 cup F_2 cup cdots)^+ = F^+ ] In simpler terms, the dependencies enforced locally on the decomposed relations must imply all original dependencies.

Concrete Decomposition Example

Consider:

emp_id dept_id dept_name
101 D10 Sales
102 D20 Engineering
103 D10 Sales

The functional dependencies are:

  • emp_id → dept_id

  • dept_id → dept_name

  • emp_id is the candidate key.

Decompose it into:

EmployeeAssignment

emp_id dept_id
101 D10
102 D20
103 D10

Department

dept_id dept_name
D10 Sales
D20 Engineering

The join result is:

emp_id dept_id dept_name
101 D10 Sales
102 D20 Engineering
103 D10 Sales

This decomposition is:

  • Lossless: The common attribute is dept_id, and dept_id → dept_name; therefore, dept_id is a key of Department and determines one decomposed relation.

  • Dependency-preserving: emp_id → dept_id is enforced in EmployeeAssignment, while dept_id → dept_name is enforced in Department.

Lossless but Not Dependency-Preserving

Consider the alternative decomposition:

  • EmployeeName(emp_id, dept_name)

  • EmployeeAssignment(emp_id, dept_id)

The common attribute is emp_id. Because emp_id → dept_name, it is a key of EmployeeName, so the decomposition is lossless.

However, its local dependencies are:

  • emp_id → dept_name in EmployeeName

  • emp_id → dept_id in EmployeeAssignment

These do not imply the original dependency dept_id → dept_name. Local constraints can therefore be satisfied while the combined data violates that dependency. For example, two different employee IDs could both use dept_id = D10 but have different department names. Checking or enforcing the original dependency therefore requires examining the joined data or maintaining an additional constraint.

Key Differences

Property Main concern Typical failure
Lossless join Preservation of relation data Reconstruction may introduce spurious tuples
Dependency preservation Preservation of integrity rules Original dependencies require joining relations to enforce

A decomposition can possess one property without the other. The earlier EmployeeAssignment and Department decomposition has both, while the alternative decomposition is lossless but not dependency-preserving.

Best Practices and Real-System Behavior

  • During normalization, prioritize decompositions that are both lossless and dependency-preserving. The standard 3NF synthesis algorithm produces such a decomposition for functional dependencies, whereas a BCNF decomposition may require joins to enforce dependencies.

  • Textbook normalization is a logical design process. PostgreSQL and MySQL/InnoDB do not automatically prove losslessness or dependency preservation.

  • Both systems enforce declared PRIMARY KEY, UNIQUE, FOREIGN KEY, and CHECK constraints, but do not generally enforce arbitrary functional dependencies directly.

  • Denormalization, materialized views, and duplicated columns may improve read performance, but they create consistency risks that the application, triggers, or reconciliation jobs must manage.

27

When is denormalization appropriate in relational database design?

Denormalization is the deliberate introduction of redundant or derived data into a relational design to improve selected read queries or simplify access patterns. It trades additional storage and update complexity for fewer joins, aggregations, or repeated computations.

Read full answer

Applies torelational database design (all versions); PostgreSQL 16 and MySQL 8.0 (InnoDB) as reference systems

Definition and Relational Model

A normalized schema seeks to minimize redundancy by storing each fact in an appropriate relation. For example, customer details belong in customer, order metadata belongs in orders, and purchased products belong in order_item.

For an illustrative design, the relevant functional dependencies might include:

  • customer_id → customer_name

  • order_id → customer_id, order_date

  • (order_id, product_name) → unit_price, quantity

A report containing each order’s total can aggregate order_item; it also joins orders when order metadata is needed and customer when customer attributes such as customer_name are selected.

Denormalization can store commonly requested values, such as customer_name and order_total, directly in a summary relation. For example, an order containing a keyboard priced at 10.00 with quantity 2 and a mouse priced at 5.00 with quantity 1 has a stored order total of 25.00.

This redundancy exists between relations. The order_summary relation may still satisfy the normal forms internally because its duplication and derived value are consequences of storing data already represented elsewhere.

How It Works

A typical denormalized design has the following structure:

  1. The normalized source relations remain authoritative.

  2. A summary relation or materialized query result stores values shaped for frequent reads.

  3. An application, database trigger, or event-processing workflow maintains the summary when relevant source data changes.

  4. The consistency requirement determines whether updates happen immediately, transactionally, or asynchronously.

The main risk is inconsistency. If a customer changes their name but existing summary rows are not updated, the database contains two representations of the same fact. When source and summary data are stored in the same transactional database, immediate updates should occur in one transaction. Asynchronous workflows can be appropriate when eventual consistency is explicitly acceptable.

When It Is Appropriate

Denormalization is appropriate when:

  • Reads dominate writes: The same large result sets are requested repeatedly, while updates are comparatively rare.

  • Join overhead is material: Queries repeatedly combine several large relations or access data across shards.

  • Expensive aggregates are common: Totals, counts, averages, or rankings are recalculated frequently.

  • A stable read model is required: Dashboards and APIs need simple, predictable access patterns.

  • Data is distributed by sharding: Co-locating frequently read fields can avoid cross-shard joins.

  • Historical snapshots are intentional: A summary can preserve the customer name or price recorded at the time of an order rather than tracking later changes to the source data.

It is usually not the first response to a slow query. Missing or unsuitable indexes, stale statistics, poor SQL, and an inefficient query plan should be investigated before adding redundant data.

Alternatives and Trade-offs

Approach Read-performance effect Consistency and maintenance
Normalized relations with suitable indexes May be sufficient with good indexing and query plans Strongest consistency and simplest update path
Denormalized summary relation Can make targeted reads predictable and inexpensive Requires duplicate-data maintenance and additional writes
Database view Simplifies query structure, but the optimizer still executes its underlying plan Does not itself add stored redundancy
PostgreSQL materialized view Stores a query result and can avoid repeated computation of an expensive query Requires refreshes and has stale data between refreshes
MySQL 8.0 summary relation Can support a purpose-built reporting workload Requires application or trigger-based maintenance

PostgreSQL materialized views are not automatically indexed, so their performance still depends on the view query, indexes, and refresh strategy. MySQL 8.0 has no native materialized-view feature; generated columns can derive values from columns in the same row but cannot replace a stored cross-table aggregate.

Best Practices and Common Pitfalls

  • Measure representative queries and the actual read/write workload before changing the schema.

  • Identify the authoritative source for every fact.

  • Define the required consistency level before choosing transactional, trigger-based, or asynchronous maintenance.

  • Monitor storage growth, write amplification, and the cost of rebuilding summaries.

  • Add reconciliation queries or jobs to detect stale data.

  • Document each redundant field, its source, and the process responsible for maintaining it.

  • Prefer targeted denormalization over broadly duplicating entire relations.

28

How do DDL, DML, DCL and TCL differ in SQL?

DDL, DML, DCL and TCL are SQL command categories distinguished by their purpose: defining database structure, retrieving or modifying data, controlling access, and controlling transactions. These categories help identify a statement’s effect, although transaction behavior also depends on the DBMS implementation.

Read full answer

Applies toSQL in PostgreSQL 16 and MySQL 8.4 (InnoDB)

Core Distinction

Category Full name Purpose Common commands
DDL Data Definition Language Creates or changes database objects and their definitions CREATE TABLE, ALTER TABLE, DROP TABLE, CREATE INDEX
DML Data Manipulation Language Retrieves or modifies rows stored in tables SELECT, INSERT, UPDATE, DELETE; MERGE in PostgreSQL 16
DCL Data Control Language Manages users, roles, and privileges GRANT, REVOKE
TCL Transaction Control Language Defines transaction boundaries and rollback points START TRANSACTION, COMMIT, ROLLBACK, SAVEPOINT

The boundaries are a teaching convention rather than a universally enforced SQL standard. In the broad convention used here, SELECT belongs to DML. Some classifications separate it as DQL—Data Query Language—and reserve DML for INSERT, UPDATE, and DELETE.

What Each Category Does

  • DDL — structural changes: DDL changes database objects or their definitions. For example, CREATE TABLE employees defines a relation, ALTER TABLE employees ADD COLUMN salary integer changes its attributes, and CREATE INDEX creates an access structure used by the query optimizer.

  • DML — data operations: DML retrieves or changes rows. SELECT reads rows, INSERT adds tuples, UPDATE changes existing tuples, and DELETE removes tuples. PostgreSQL 16 also supports MERGE for conditional inserts, updates, and deletes; MySQL 8.4 does not support the SQL-standard MERGE statement.

  • DCL — authorization changes: DCL controls who may access an object or perform an operation. For example, GRANT SELECT ON employees TO analyst allows an existing role to read the table. Authentication and password management are related but distinct administrative functions.

  • TCL — transaction management: TCL starts and ends transactions and controls intermediate rollback points. A successful COMMIT ends the transaction, after which that transaction’s ROLLBACK cannot undo its changes. ROLLBACK discards uncommitted changes, while savepoints allow selected portions of a transaction to be rolled back.

Transaction Behavior Across Systems

The command category alone does not determine whether a statement can be committed or rolled back.

  • PostgreSQL 16: DDL and DML statements are generally transactional when executed inside an explicit transaction. Most object-creation and schema-change operations can therefore be rolled back. Commands such as CREATE DATABASE and CREATE INDEX CONCURRENTLY cannot run inside a transaction block.

  • MySQL 8.4 InnoDB: InnoDB supports transactional DML, including rollback of uncommitted inserts, updates, and deletes. Most ordinary DDL performs an implicit commit, so a table-definition change is not rolled back with the surrounding transaction.

  • PostgreSQL privileges: GRANT and REVOKE participate in transactions and can be rolled back.

  • MySQL privileges: GRANT and REVOKE cause an implicit commit.

  • Other engines: DML may be immediately committed or may lack rollback support when the storage engine is not transactional.

Common Pitfalls

  • Do not assume DDL is always transactional: PostgreSQL and MySQL behave differently here.

  • Do not classify SELECT inconsistently: State whether you use the broad DML convention or the separate DQL convention.

  • Distinguish DCL from authentication: DCL manages SQL privileges; user creation and password management are often classified separately as administration operations.

  • Recognize implicit commits: In MySQL, statements that perform an implicit commit also end the current transaction, so unexpected commit behavior should be investigated.

  • Check engine support: Transaction guarantees apply to transactional storage engines such as PostgreSQL and MySQL InnoDB, not automatically to every database or table.

29

How do DELETE, TRUNCATE, and DROP differ in SQL?

The core distinction is the object affected: DELETE removes rows, TRUNCATE removes all rows while preserving the table definition, and DROP removes the table itself, including its data and structure. Their transaction, trigger, foreign-key, identity-sequence, and performance behavior also differ between PostgreSQL and MySQL.

Read full answer

Applies toSQL in PostgreSQL 16 and MySQL 8.4 with InnoDB

How They Differ

Aspect DELETE TRUNCATE DROP
What is removed Selected rows or all rows All rows Table definition and data
Supports WHERE Yes No Not applicable
Table remains Yes Yes No
Row-level delete triggers Yes No No
Foreign-key effects Can trigger ON DELETE CASCADE, SET NULL, and other referential actions Usually blocked when another table references it May require dependency handling before removal
Identity behavior Does not reset counters PostgreSQL defaults to CONTINUE IDENTITY; MySQL resets AUTO_INCREMENT Counter and table-owned sequences are removed
Typical performance Slower when deleting many rows Faster for complete cleanup Fast structural removal
PostgreSQL rollback Yes Yes Yes
MySQL InnoDB rollback Yes No; causes an implicit commit No; causes an implicit commit

Rows, Structure, and Storage

  • DELETE FROM employee WHERE employee_id = 2;

  • Removes only matching rows.

  • Leaves indexes, constraints, triggers, sequences, and the table definition intact.

  • DELETE FROM employee; removes every row but behaves differently from TRUNCATE.

  • TRUNCATE TABLE employee;

  • Removes all rows without evaluating a row-level WHERE clause.

  • Preserves the table, columns, constraints, indexes, and views defined over it.

  • PostgreSQL can truncate multiple related tables in one statement when foreign-key relationships require it.

  • MySQL InnoDB cannot truncate a table referenced by a foreign key.

  • DROP TABLE employee;

  • Removes the table, so subsequent queries against it fail.

  • In PostgreSQL, dependent views may prevent the drop unless CASCADE is used or the dependencies are removed first.

  • PostgreSQL also drops sequences owned by the dropped table. MySQL removes the associated InnoDB table definition and data.

Transactions and Concurrency

In PostgreSQL:

  • All three commands participate in transactional DML or DDL behavior.

  • DELETE uses MVCC, so existing readers can continue seeing previous row versions until their transactions finish.

  • Deleted rows become dead tuples. Space can later be reused, but PostgreSQL generally does not immediately return it to the operating system; VACUUM performs cleanup.

  • TRUNCATE and DROP TABLE acquire an ACCESS EXCLUSIVE lock and can be rolled back if their transaction is rolled back.

  • TRUNCATE is not MVCC-safe for concurrent transactions: after it executes, concurrent transactions may observe the table as empty even with an older snapshot.

In MySQL InnoDB:

  • DELETE is transactional and can be rolled back before commit.

  • InnoDB records changes in undo logs and acquires row locks as needed.

  • TRUNCATE TABLE and DROP TABLE are DDL operations that cause an implicit commit, so they cannot roll back earlier transactional work.

Triggers and Identity Columns

  • PostgreSQL DELETE fires BEFORE DELETE, AFTER DELETE, and statement-level delete triggers.

  • PostgreSQL TRUNCATE fires BEFORE TRUNCATE and AFTER TRUNCATE statement-level triggers.

  • MySQL fires delete triggers for DELETE, but not for TRUNCATE or DROP.

  • PostgreSQL TRUNCATE continues identity sequences by default; TRUNCATE TABLE employee RESTART IDENTITY; explicitly restarts the associated identity sequence.

  • MySQL TRUNCATE resets the AUTO_INCREMENT counter.

  • DELETE does not reset PostgreSQL identity sequences or MySQL AUTO_INCREMENT counters.

Concrete PostgreSQL Example

Assume employee has an identity primary key and contains:

employee_id employee_name
1 Alice
2 Bob
3 Charlie

After DELETE FROM employee WHERE employee_id = 2;, the result is:

employee_id employee_name
1 Alice
3 Charlie

After TRUNCATE TABLE employee RESTART IDENTITY;, the result is an empty table:

employee_id employee_name

After DROP TABLE employee;, the table no longer exists. SELECT to_regclass('public.employee'); returns null.

Best Practices and Common Pitfalls

  • Use DELETE for selective removal, row-level auditing, and transactional cleanup in MySQL.

  • Use TRUNCATE for a complete reset when the table definition must remain and triggers and foreign keys permit it.

  • Use DROP when the table is no longer part of the schema; inspect dependencies before choosing CASCADE.

  • Do not assume TRUNCATE can be rolled back in MySQL. PostgreSQL and MySQL have materially different transaction semantics here.

  • Do not rely on DELETE to reclaim disk space immediately. PostgreSQL cleanup generally depends on VACUUM, while InnoDB cleanup depends on undo-log purging.

  • Avoid using TRUNCATE merely as a faster substitute for DELETE: it bypasses delete triggers, cannot target individual rows, and changes identity-counter behavior.

30

What are the different types of SQL joins?

A SQL join combines rows from two or more tables according to a specified condition. The join type determines whether only matching rows are retained or whether unmatched rows from one or both tables are preserved.

Read full answer

Applies tostandard SQL, PostgreSQL 16, and MySQL 8.4 with InnoDB

Core Semantics

For two tables, A JOIN B:

  • Matching rows: Rows satisfying the join condition in ON.

  • Unmatched rows: Rows that exist in only one table.

  • Outer-join extension: Columns from the missing side are populated with NULL.

  • Result cardinality: A matching pair of input rows produces an output row, so one-to-many relationships can multiply rows.

JOIN without a type means INNER JOIN. A condition in ON controls row matching, whereas a condition in WHERE filters the completed join result and can accidentally eliminate unmatched rows preserved by an outer join.

Join Types

Join type Rows retained Typical use
INNER JOIN Only rows with a match in both tables Retrieve records that exist on both sides
LEFT JOIN Every left-table row, plus matching right-table rows Show every customer and any associated orders
RIGHT JOIN Every right-table row, plus matching left-table rows Preserve the right table; equivalent to a reversed LEFT JOIN
FULL OUTER JOIN Every row from both tables, matched or unmatched Reconcile datasets without losing discrepancies
CROSS JOIN Every combination of rows from both tables Generate pairings or test possible combinations
NATURAL JOIN Matches rows using all identically named columns Convenient joins, but fragile when schemas evolve
SELF JOIN Uses an ordinary join between two aliases of the same table Model employee-manager or category-parent relationships

Worked Example

Consider customers 1 Alice, 2 Bob, and 3 Carol. Consider orders 101 and 102 for customer 1, order 103 for customer 2, and order 104 for the nonexistent customer 99.

Join Result rows
INNER JOIN Alice with orders 101 and 102; Bob with order 103
LEFT JOIN The three inner rows plus Carol with NULL order fields
RIGHT JOIN The three inner rows plus a NULL customer for order 104
FULL OUTER JOIN The three inner rows plus both unmatched rows
CROSS JOIN 12 rows: each of the three customers combined with each of the four orders

SQL does not guarantee row order unless the query includes ORDER BY.

Best Practices and System Differences

  • Use INNER JOIN when both records must exist.

  • Prefer LEFT JOIN over RIGHT JOIN in most application queries because the preserved table is easier to identify.

  • Put join conditions in ON. A predicate in WHERE that rejects NULL values can turn a LEFT JOIN into an inner-join-like result.

  • Index commonly joined columns, including foreign-key columns such as orders.customer_id, although the query planner may reorder joins while preserving their semantics.

  • PostgreSQL 16 supports FULL OUTER JOIN. MySQL 8.4 does not support it directly and requires emulation using outer and anti-join logic.

  • PostgreSQL 16 and MySQL 8.4 support the other listed join forms, but their planners, index-selection strategies, and execution plans differ.

31

How does SQL WHERE differ from HAVING?

WHERE filters rows before grouping, while HAVING filters groups after grouping and aggregation. The logical distinction determines which conditions can reference source rows, grouped rows, or aggregate results.

Read full answer

Applies toSQL in PostgreSQL 16 and MySQL 8.0 with InnoDB

How It Works

The conceptual SQL processing order is:

  1. FROM identifies the source rows.

  2. WHERE filters individual rows.

  3. GROUP BY forms groups.

  4. HAVING filters those groups.

  5. SELECT produces output columns.

  6. ORDER BY sorts the result.

This is a logical evaluation order, not a guarantee of physical execution order. PostgreSQL and MySQL query optimizers may reorder predicates or transform equivalent queries, so execution plans should be checked with EXPLAIN when performance matters.

Consider these orders:

customer_id order_date amount
101 2025-01-10 75
101 2025-02-12 90
102 2025-01-15 200
103 2025-03-01 40
104 2025-03-05 60

The condition WHERE amount > 50 removes customer 103’s order before grouping. The condition HAVING SUM(amount) > 100 then removes customer 104’s group because its qualifying total is only 60.

The remaining summaries are:

customer_id total_amount
101 165
102 200

Key Differences

Aspect WHERE HAVING
Filtering level Individual source rows Groups or aggregate results
Position relative to grouping Before GROUP BY After GROUP BY
Aggregate functions Cannot directly reference SUM, COUNT, or AVG Can reference aggregate functions
Used without GROUP BY Filters the input rows before evaluation Evaluates the single overall group; without an aggregate, it acts as a result-wide predicate
Typical use Restricting rows before summarization Keeping only groups that satisfy an aggregate condition

Both clauses use SQL’s three-valued logic. A retained row or group must satisfy a predicate that evaluates to TRUE; a predicate evaluating to FALSE or UNKNOWN does not retain it.

Practical Guidance and Pitfalls

  • Use WHERE for conditions on source columns, such as status = 'paid', because filtering before aggregation usually reduces the amount of data processed.

  • Use HAVING for conditions involving aggregates, such as COUNT(*) > 5 or AVG(balance) < 1000.

  • Do not assume WHERE is always faster merely because it appears earlier. Optimizers can transform equivalent queries, and the actual execution plan determines performance.

  • Avoid relying on HAVING without GROUP BY; it operates on one overall group and is often less intuitive than using an explicit grouping query.

  • Keep selected columns consistent with GROUP BY. PostgreSQL 16’s default grouping rules and MySQL 8.0’s default ONLY_FULL_GROUP_BY mode generally reject ungrouped, non-aggregated columns unless they are recognized as functionally dependent on the grouped columns.

32

How do subqueries differ from correlated subqueries in SQL?

A subquery is a query nested inside another SQL statement, such as a SELECT used in a WHERE clause. A correlated subquery additionally references a column from the outer query, so its result depends on the current outer row.

Read full answer

Applies toSQL (PostgreSQL 16 and MySQL 8.4 InnoDB)

Core Concepts

In the relational model, a subquery appears as a nested query block:

  • Outer query: The query containing the subquery.

  • Inner query: The nested query that produces a condition or value.

  • Uncorrelated subquery: Does not reference the outer query. It can conceptually be evaluated independently.

  • Correlated subquery: References the outer query, creating a dependency between the two query blocks.

Property Uncorrelated subquery Correlated subquery
Outer-query reference None References at least one outer-query column
Logical evaluation Can be evaluated independently Evaluated in the context of each candidate outer row
Result dependence Same inner result for every outer row May differ for each outer row
Typical optimization Materialization or decorrelation into a join Rewrite into a join, semijoin, index lookup, or other equivalent plan

The distinction describes dependency, not result shape. For example, a scalar, IN, or EXISTS subquery may be either correlated or uncorrelated.

Common Forms

Form Purpose Behaviour
Scalar subquery Produces one value Must return exactly one row and one column
IN subquery Tests membership in a set Accepts a subquery producing multiple rows
EXISTS subquery Tests whether matching rows exist Returns a Boolean; duplicate matches do not change the result
Derived table Supplies rows as a table Appears in FROM and normally requires an alias

In PostgreSQL and MySQL, a scalar subquery returning zero or multiple rows causes an error. IN accepts a multi-row subquery result, whereas EXISTS evaluates whether at least one match exists and returns only TRUE or FALSE.

How Evaluation Works

For an uncorrelated subquery, the textbook nested-loop model can evaluate the inner relation once and reuse its result to filter or transform the outer relation.

For a correlated subquery, logical evaluation follows these steps:

  1. Select a candidate outer tuple.

  2. Make that tuple’s values available to the inner query.

  3. Evaluate the inner query in that context.

  4. Test the inner result against the outer tuple.

  5. Continue with the next outer tuple.

This does not guarantee repeated physical execution. PostgreSQL and MySQL optimizers commonly rewrite correlated subqueries into joins, semijoins, aggregated joins, or index-based plans.

Concrete Example

Suppose Engineering has a budget of 1000000, Sales has 500000, and Support has 300000, and the employees are:

employee_id employee_name department salary
101 Alice Engineering 130000
102 Bob Engineering 100000
103 Carol Sales 70000
104 Dan Support 60000

An uncorrelated IN subquery that selects departments with budgets greater than 500000 finds Engineering only. Its result is therefore:

employee_id employee_name
101 Alice
102 Bob

Carol is not included because Sales has a budget of exactly 500000, not greater than 500000.

A correlated scalar subquery that calculates the average salary within each employee’s department produces a different result. Engineering’s average salary is 115000, so only Alice qualifies. Carol and Dan are excluded because their salaries equal their respective department averages:

employee_id employee_name
101 Alice

The reference from the inner query to the outer employee’s department_id is what makes the second subquery correlated.

Best Practices and Pitfalls

  • Use the predicate that matches the requirement: EXISTS directly expresses an existence test, while IN expresses set membership. Duplicate rows normally do not require special handling with either predicate.

  • Watch NULL semantics: NOT IN can produce no qualifying rows if the subquery returns NULL and no equal value is found. NOT EXISTS often expresses the intended anti-membership test more safely.

  • Avoid unnecessary correlation: If an uncorrelated subquery or equivalent join is clearer and more efficient, prefer it.

  • Use indexes carefully: Indexes on filtering, correlation, and join columns can reduce work, but the actual benefit depends on selectivity and statistics.

  • Inspect the execution plan: Use EXPLAIN ANALYZE in PostgreSQL and MySQL rather than assuming that textual nesting determines physical execution order.

33

UNION vs UNION ALL in SQL: what is the difference?

UNION returns distinct rows by eliminating duplicates, while UNION ALL returns every row produced by both queries, including duplicates. In relational-model terms, UNION has set semantics; UNION ALL has bag or multiset semantics.

Read full answer

Applies toSQL standard; PostgreSQL 16 and MySQL 8.0 with InnoDB

Core Semantics

Operator Duplicate handling Result
UNION Removes duplicate output rows Each distinct row appears once
UNION ALL Preserves all output rows Duplicate rows can appear multiple times

Duplicates are determined by the selected output columns, not by the complete source rows. Comparisons also follow the database’s type, collation, and equality rules.

Both operators require the two queries to return the same number of columns and compatible data types. Column names in the combined result normally come from the first query.

Worked Example

CREATE TEMP TABLE orders (
    id integer,
    customer_id integer,
    status varchar(20)
);

INSERT INTO orders (id, customer_id, status) VALUES
    (1, 10, 'paid'),
    (2, 10, 'new'),
    (1, 20, 'paid'),
    (3, 20, 'pending');

Using UNION:

SELECT id, status
FROM orders
WHERE customer_id = 10

UNION

SELECT id, status
FROM orders
WHERE customer_id = 20

ORDER BY id, status;

Result:

id status
1 paid
2 new
3 pending

The paid row occurs in both branches, but UNION returns it only once.

Using UNION ALL:

SELECT id, status
FROM orders
WHERE customer_id = 10

UNION ALL

SELECT id, status
FROM orders
WHERE customer_id = 20

ORDER BY id, status;

Result:

id status
1 paid
1 paid
2 new
3 pending

UNION ALL retains both occurrences of (1, 'paid').

How Database Engines Execute Them

  • UNION: Engines commonly use sorting or hashing to identify and remove duplicate output rows. This requires additional processing and temporary storage.

  • UNION ALL: Engines can generally append the second result to the first without duplicate detection, making it faster and more memory-efficient.

  • The exact implementation is engine-specific. PostgreSQL may use sort-based or hash-based duplicate elimination, while MySQL may use temporary structures. The observable SQL semantics remain the same.

Type and Collation Considerations

  • PostgreSQL 16: The branches must have compatible types. Combining unrelated types, such as integer and text, may raise an error unless an explicit cast is provided.

  • MySQL 8.0: Type compatibility is evaluated using MySQL’s coercion rules, so some mixed numeric and string expressions can be converted automatically.

  • Text comparison: Collation can determine whether values are considered duplicates. For example, case-insensitive collations may treat differently cased strings as equal.

  • Output naming: Use aliases in the first query when the desired result-column names do not match the source column names.

When to Use Each

Use UNION when duplicate rows are meaningless or would create incorrect results, such as combining mutually exclusive date ranges and then deduplicating the resulting entries.

Use UNION ALL when duplicates are valid or useful, such as combining historical events, log records, or partitioned audit data. It is usually the better choice when the input branches are already guaranteed to be disjoint.

Do not use UNION merely to “clean up” data unless duplicate elimination is intentional; it can hide genuine repeated events and add sorting or hashing overhead.

34

How do SQL window functions differ from GROUP BY?

A window function calculates a value across a set of related rows while preserving each original row in the result. In contrast, GROUP BY combines rows into groups and usually returns one result row per group.

Read full answer

Applies toSQL window functions in PostgreSQL 16 and MySQL 8.0/8.4

How Window Functions Work

A window function uses an OVER clause to define its window. The window determines which rows participate in the calculation and how they are ordered.

function_name(...) OVER (
    [PARTITION BY ...]
    [ORDER BY ...]
    [frame_clause]
)

The main components are:

  • Partition: Divides rows into independent sets. PARTITION BY region calculates separately for each region.

  • Ordering: Defines row order inside a partition, which is important for running totals, rankings, and functions such as LAG.

  • Frame: Selects the portion of the partition used by the calculation. Common frames include the current row, preceding rows, following rows, or the entire partition.

Common categories include:

  • Aggregate functions: SUM, AVG, COUNT, MIN, MAX

  • Ranking functions: ROW_NUMBER, RANK, DENSE_RANK, NTILE

  • Value functions: LAG, LEAD, FIRST_VALUE, LAST_VALUE

Window Functions vs. GROUP BY

Aspect Window function GROUP BY
Number of output rows Generally preserves the input rows Produces one row per group
Calculation scope A partition, optionally ordered and framed All rows belonging to each group
Row-level details Retained Collapsed
Typical use Running totals, rankings, comparisons with neighboring rows Summaries, reporting, aggregation
Result size Can be larger Usually smaller

For example, suppose a sale table contains:

id region salesperson amount
1 East Alice 100
2 East Bob 120
3 West Alice 80
4 West Bob 150

A GROUP BY query returns one row per region:

SELECT region, SUM(amount) AS region_total
FROM sale
GROUP BY region
ORDER BY region;
region region_total
East 220
West 230

A window function can retain the sale details while adding a running regional total.

Code Example

CREATE TABLE sale (
    id         INTEGER PRIMARY KEY,
    region     TEXT NOT NULL,
    salesperson TEXT NOT NULL,
    amount     INTEGER NOT NULL
);

INSERT INTO sale (id, region, salesperson, amount) VALUES
    (1, 'East', 'Alice', 100),
    (2, 'East', 'Bob',   120),
    (3, 'West', 'Alice', 80),
    (4, 'West', 'Bob',   150);

SELECT
    id,
    region,
    salesperson,
    amount,
    SUM(amount) OVER (
        PARTITION BY region
        ORDER BY amount, id
        ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS running_region_total
FROM sale
ORDER BY region, amount, id;

Result:

id region salesperson amount running_region_total
1 East Alice 100 100
2 East Bob 120 220
3 West Alice 80 80
4 West Bob 150 230

Here, PARTITION BY region separates the regions, while ORDER BY amount, id makes the running-total order deterministic. ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW includes every row from the partition’s start through the current row.

Frame and Version Details

  • With ORDER BY but no explicit frame, PostgreSQL and MySQL default to a RANGE frame ending at the current row. This includes rows tied on the ordering values.

  • Without ORDER BY, an aggregate window normally considers the entire partition.

  • ROWS counts physical rows, while RANGE groups rows with equal ordering values as peers.

  • PostgreSQL and MySQL 8.0/8.4 both support an empty window specification such as SUM(amount) OVER (), which treats the whole result as one partition.

PostgreSQL commonly implements window execution with sorting and a WindowAgg execution node. MySQL performs the operation in its SQL execution layer; the InnoDB storage engine mainly handles persistence, indexes, locking, and recovery rather than window calculation.

Best Practices and Pitfalls

  • Use GROUP BY when only aggregated group-level results are required; it is usually the more direct and efficient choice.

  • Use window functions when the query must retain row-level details alongside totals, rankings, or neighboring-row comparisons.

  • Specify the frame explicitly when the exact set of included rows matters.

  • Add a unique tie-breaker, such as id, to ORDER BY when deterministic ordering is required.

  • Window operations may require sorting large intermediate datasets, so monitor temporary storage and execution time on high-volume tables.

  • A window function is evaluated after FROM, WHERE, GROUP BY, and HAVING. Therefore, when both are present, the window operates over the grouped rows unless the query structure explicitly joins or aggregates them first.

35

How do you find the second highest salary with SQL?

The second-highest salary is the second-largest distinct, non-NULL salary. Use DENSE_RANK() to rank unique salary levels, ensuring tied highest salaries do not cause the next salary to be skipped.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.0 (InnoDB)

How It Works

DENSE_RANK() OVER (ORDER BY salary DESC) assigns:

  • Rank 1 to the highest salary.

  • Rank 2 to the next-lowest distinct salary.

  • The same rank to employees with equal salaries.

Selecting the row with rank 2 and applying DISTINCT returns one salary value even if several employees earn it.

Handling Ties and Alternative Interpretations

Requirement Recommended approach Behavior
Second-highest distinct salary DENSE_RANK() Correctly handles tied salaries
Second row after sorting employees ROW_NUMBER() Requires a deterministic tie-breaker such as employee_id
Second ranked row when ties share a rank RANK() A tie at the top makes the next rank 3
Second row using pagination LIMIT 1 OFFSET 1 Incorrect for distinct values because the second row may repeat the highest salary

For example, if two employees earn 90000.00, that salary remains rank 1. A salary of 80000.00 is still rank 2.

Query Alternatives

The window-function approach is clear and handles ties correctly. A simpler alternative uses two MAX() calls:

SELECT MAX(salary) AS second_highest_salary
FROM employees
WHERE salary < (
    SELECT MAX(salary)
    FROM employees
    WHERE salary IS NOT NULL
);

This returns the largest salary strictly below the maximum. The window-function version is generally easier to extend and more explicit about ranking semantics.

Code Example

CREATE TABLE employees (
    employee_id integer PRIMARY KEY,
    name text NOT NULL,
    salary numeric(12, 2)
);

INSERT INTO employees (employee_id, name, salary) VALUES
    (1, 'Aisha', 90000.00),
    (2, 'Ben',   90000.00),
    (3, 'Chloe', 80000.00),
    (4, 'Dan',   80000.00),
    (5, 'Eve',   70000.00);

WITH ranked_salaries AS (
    SELECT
        salary,
        DENSE_RANK() OVER (ORDER BY salary DESC) AS salary_rank
    FROM employees
    WHERE salary IS NOT NULL
)
SELECT DISTINCT salary
FROM ranked_salaries
WHERE salary_rank = 2;

Result:

salary
80000.00

Best Practices and Trade-offs

  • Define tie behavior: Confirm whether the question asks for the second-highest distinct value or the second employee in sorted order.

  • Exclude NULL values: NULL is not a salary level. The explicit filter also prevents nullable columns from affecting the ranking.

  • Avoid LIMIT/OFFSET for distinct values: ORDER BY salary DESC LIMIT 1 OFFSET 1 can return the highest salary again when multiple employees share it.

  • Use fixed-point numeric types: numeric(12,2) or decimal(12,2) avoids floating-point inaccuracies in salary calculations.

  • Consider performance: Ranking processes and sorts candidate rows. An index on salary DESC may help ordering, but the query planner decides whether it avoids a separate sort.

  • Use deterministic ordering for ROW_NUMBER(): Add employee_id to the ORDER BY clause when selecting one specific employee from tied rows.

36

How do you find duplicate rows with SQL?

Duplicate rows are records with matching values in the columns selected for comparison. Use GROUP BY with HAVING COUNT(*) > 1 to identify duplicate groups, then join those groups back to the original table to retrieve every matching row.

Read full answer

Applies toDBMS (PostgreSQL 16 and MySQL 8.0/InnoDB)

Core Idea

The standard SQL pattern has two stages:

  1. Group rows by the columns that define a duplicate.

  2. Use HAVING COUNT(*) > 1 to retain only groups containing multiple rows.

The condition must be written with HAVING, not WHERE, because WHERE is evaluated before rows are grouped. If every matching row is required rather than just the duplicate groups, join the grouped result back to the source table.

PostgreSQL Example

Suppose an employee is identified by employee_id, but duplicate business records are determined by department, employee_name, and email.

CREATE TABLE employees (
    employee_id integer PRIMARY KEY,
    department text NOT NULL,
    employee_name text NOT NULL,
    email text
);

INSERT INTO employees
    (employee_id, department, employee_name, email)
VALUES
    (1, 'Sales', 'Ava', 'ava@example.com'),
    (2, 'Sales', 'Ava', 'ava@example.com'),
    (3, 'Engineering', 'Ben', NULL),
    (4, 'Engineering', 'Ben', NULL),
    (5, 'Sales', 'Ava', 'ava@example.com');

WITH duplicate_groups AS (
    SELECT
        department,
        employee_name,
        email
    FROM employees
    GROUP BY department, employee_name, email
    HAVING COUNT(*) > 1
)
SELECT
    e.employee_id,
    e.department,
    e.employee_name,
    e.email
FROM employees AS e
JOIN duplicate_groups AS d
    ON e.department IS NOT DISTINCT FROM d.department
   AND e.employee_name IS NOT DISTINCT FROM d.employee_name
   AND e.email IS NOT DISTINCT FROM d.email
ORDER BY e.employee_id;

The query returns every row belonging to a duplicate group:

employee_id department employee_name email
1 Sales Ava ava@example.com
2 Sales Ava ava@example.com
3 Engineering Ben NULL
4 Engineering Ben NULL
5 Sales Ava ava@example.com

Duplicate Detection Details

  • Chosen columns: Define precisely which columns establish duplication. For example, two employees may legitimately share a name but have different email addresses.

  • Primary keys: A table containing a unique PRIMARY KEY cannot have exact duplicates when that key is included in the comparison.

  • NULL values: GROUP BY treats matching NULL values as one group. In PostgreSQL, IS NOT DISTINCT FROM provides the same null-safe behavior when joining the groups back.

  • MySQL difference: Replace each PostgreSQL IS NOT DISTINCT FROM comparison with MySQL’s null-safe equality operator, <=>.

  • Representative rows: If only one row per duplicate group is needed, select from duplicate_groups directly instead of joining back to employees.

Best Practices and Pitfalls

  • Prefer a unique constraint on the business key after resolving existing duplicates. PostgreSQL and MySQL InnoDB can enforce this with a UNIQUE constraint or unique index.

  • Add a composite index on the columns used for duplicate detection if the table is large and this check is frequent. The aggregation still processes the relevant rows, but indexing can reduce I/O.

  • Do not group by every column automatically when a surrogate employee_id is present, because that prevents duplicates from being detected.

  • Decide whether NULL means “same value” for the business rule. SQL grouping considers NULL values equivalent, while ordinary = comparisons do not match NULL.

  • Use EXCEPT or set-based logic when comparing two tables; do not rely on NOT IN with a nullable subquery because its NULL semantics can unintentionally remove valid rows.

37

Which employees earn more than their managers in SQL?

A self-join finds employees whose salary exceeds that of their direct manager by treating the employees table twice—once for the employee and once for the manager. The join uses manager_id to relate each employee to the row in employees containing their manager’s salary.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.0.16+ (InnoDB)

Core Approach

Assume the schema stores each employee and their manager in the same table:

  • employee_id: Unique employee identifier and primary key.

  • employee_name: Employee’s name.

  • salary: Employee’s salary.

  • manager_id: Employee ID of the employee’s manager.

The relationship is:

employees.manager_id → employees.employee_id

The employee is the row on the left side of the join, while the manager is the matching row on the right side.

How It Works

  1. Join employees AS e to employees AS m.

  2. Match e.manager_id = m.employee_id.

  3. Keep rows where e.salary > m.salary.

  4. Use an INNER JOIN because the query only evaluates employees who have a matching manager row.

In the textbook relational model, this is a self-relation expressed through a self-join. PostgreSQL and MySQL implement it as an ordinary join, although their query planners may use different physical strategies depending on the version, available indexes, and query statistics.

Code Example

CREATE TABLE employees (
    employee_id   INTEGER PRIMARY KEY,
    employee_name VARCHAR(100) NOT NULL,
    salary        NUMERIC(12, 2) NOT NULL CHECK (salary >= 0),
    manager_id    INTEGER,
    CONSTRAINT fk_employee_manager
        FOREIGN KEY (manager_id)
        REFERENCES employees (employee_id)
);

INSERT INTO employees
    (employee_id, employee_name, salary, manager_id)
VALUES
    (1, 'Alice', 120000.00, NULL),
    (2, 'Bob',   90000.00, 1),
    (3, 'Carol', 110000.00, 1),
    (4, 'Dan',   60000.00, 2),
    (5, 'Erin',  95000.00, 2);

SELECT
    e.employee_id,
    e.employee_name,
    e.salary AS employee_salary,
    m.employee_name AS manager_name,
    m.salary AS manager_salary
FROM employees AS e
INNER JOIN employees AS m
    ON m.employee_id = e.manager_id
WHERE e.salary > m.salary
ORDER BY e.employee_id;

Result

employee_id employee_name employee_salary manager_name manager_salary
5 Erin 95000.00 Bob 90000.00

Alice is excluded because she has no manager. Bob, Carol, and Dan are excluded because their salaries do not exceed their managers’ salaries.

Trade-offs and Best Practices

  • Index the foreign key: An index on employees(manager_id) can improve join performance. PostgreSQL does not automatically index foreign keys, while MySQL/InnoDB generally creates one.

  • Index the primary key: employee_id should remain indexed because it identifies the matching manager.

  • Handle missing managers deliberately: INNER JOIN excludes employees with NULL or nonexistent manager_id values. A LEFT JOIN is preferable when the report must also display employees without a manager, but the WHERE condition still excludes unknown salary comparisons.

  • NULL behavior: NULL > 10000 evaluates to unknown, so employees with a NULL salary are not returned.

  • Avoid strict equality when that is not intended: Employees earning exactly the same amount as their manager are excluded because the query requires > rather than >=.

  • Preserve the relationship in the database: A self-referencing foreign key prevents employees from referencing a nonexistent manager, although additional application logic may be needed to prevent invalid management cycles.

38

How do SQL views differ from materialized views?

A view is a named query exposed as a virtual table, while a materialized view stores the query’s result as a separate database object. A view normally shows current base-table data when queried; a materialized view can contain stale results until it is refreshed.

Read full answer

Applies toDBMS concepts generally; PostgreSQL 16 views and materialized views; MySQL 8.4 views

Core Concepts

  • View: Stores a query definition rather than independent result rows. The query planner may rewrite, inline, or optimize the view as part of the surrounding SQL statement.

  • Column names and types are derived from the query.

  • Data is fetched from the underlying tables whenever the view is queried.

  • Simple views may be updatable, but joins, aggregates, GROUP BY, and other complex queries often prevent direct updates.

  • Materialized view: Executes its defining query and stores the resulting rows physically.

  • Queries can read the stored result without recomputing expensive joins or aggregations.

  • The stored data reflects the base tables only as of the last refresh.

  • PostgreSQL permits indexes on materialized views, making them useful for reporting and dashboard queries.

Concrete Example

Suppose an orders table contains:

order_id customer_id amount
1001 C1 120
1002 C1 80
1003 C2 200

A view defined as SELECT customer_id, SUM(amount) FROM orders GROUP BY customer_id returns:

customer_id total
C1 200
C2 200

If a new order of 50 is inserted for C2:

  • The ordinary view returns 250 for C2 immediately.

  • A materialized view initialized with the earlier results still returns 200 until it is refreshed.

Comparison

Aspect View Materialized view
Storage Query definition; normally no result rows Physical result rows
Freshness Current base-table data Snapshot valid until refresh
Query cost May recompute joins or aggregation Usually faster reads
Maintenance Little to no refresh work Requires refresh strategy
Indexes Uses indexes on underlying objects Can have its own indexes
Updates Some simple views are updatable Not directly updatable in PostgreSQL
Consistency Reflects data visible to the current transaction May lag behind base tables

Behavior in PostgreSQL and MySQL

  • PostgreSQL supports both ordinary views and materialized views. Materialized views are refreshed with REFRESH MATERIALIZED VIEW; concurrent refreshes are possible when the required index conditions are satisfied.

  • MySQL supports ordinary views but does not provide native materialized views. Applications sometimes emulate them with tables maintained by scheduled jobs or events, although this requires explicit design.

  • In both systems, the query optimizer can optimize an ordinary view much like the equivalent inline query. A view therefore does not automatically improve performance.

Trade-offs

A materialized view is most useful for frequently executed, expensive queries such as daily sales summaries or multi-table reporting datasets. It trades freshness and maintenance cost for predictable read latency. Refreshes may consume substantial CPU, I/O, and temporary storage and can temporarily affect concurrent readers.

An ordinary view is preferable when current data is required, the query is inexpensive, or the main purpose is to centralize business-query logic and presentation.

Best Practices and Pitfalls

  • Use ordinary views for reusable joins, filtering, row-level access patterns, and consistently defined calculations.

  • Use materialized views when the same expensive computation is repeated and some delay is acceptable.

  • Define refresh frequency, failure handling, and acceptable data lag before deploying a materialized view.

  • Monitor refresh duration and materialized-view size in production.

  • Use EXPLAIN ANALYZE to verify that a view is optimized effectively; do not assume a view is faster than the underlying query.

  • Remember that a materialized view is a snapshot, not a source of authoritative current data.

39

What are stored procedures, functions and triggers in SQL databases?

Stored procedures, functions, and triggers are server-side SQL constructs that execute database logic within the DBMS. A stored procedure performs an action, a function returns a value, and a trigger runs automatically when a defined table event occurs.

Read full answer

Applies togeneral SQL database concepts; PostgreSQL 16 and MySQL 8.0 (InnoDB)

Definitions at a Glance

Construct Invocation Result Automatic execution Typical use
Stored procedure Explicitly, usually with CALL No function-style return value; may have output parameters or result sets No Multi-step transactional work
Function From an expression or query A scalar value; PostgreSQL can also return rows No Calculations and reusable query logic
Trigger In response to an INSERT, UPDATE, or DELETE event No direct result set; a BEFORE trigger may alter the affected row Yes Auditing, validation, and derived data

Stored Procedures

A stored procedure is a named routine containing SQL and procedural statements stored in the database catalog. Calling one server-side can reduce network traffic and centralize multi-step operations.

PostgreSQL 16 and MySQL 8.0 both support CREATE PROCEDURE and CALL. PostgreSQL procedures can contain transaction-control statements such as COMMIT and ROLLBACK, but only when the CALL is not inside an explicit transaction block. MySQL procedures support IN, OUT, and INOUT parameters.

For example, a transfer procedure can lock the source and destination rows in a consistent order, validate the amount and account IDs, check the source balance, and update both rows. Transferring 500 from a row with balance 1500 to a row with balance 0 leaves balances of 1000 and 500. The procedure is not automatically atomic unless its execution and error handling provide that guarantee; in PostgreSQL, an exception block can create a subtransaction, while an uncaught error aborts the surrounding transaction.

Functions

A function is a named routine that returns a value and can be used in SQL expressions. PostgreSQL functions may return a scalar, SETOF rows, or a TABLE; MySQL 8.0 functions return one scalar value.

PostgreSQL uses volatility attributes to describe a function’s data access:

  • IMMUTABLE: the function does not access the database or change state.

  • STABLE: the function reads data using a snapshot consistent with the calling statement.

  • VOLATILE: the default; the function may read or modify data and may have side effects.

PostgreSQL generated-column expressions and index expressions require IMMUTABLE functions. In MySQL, when binary logging is enabled and log_bin_trust_function_creators is disabled, function creation is rejected with error 1418 unless the function is declared DETERMINISTIC, NO SQL, or READS SQL DATA.

Triggers

A trigger is a routine associated with a table event and executed automatically by the DBMS. It is normally not invoked directly by an application.

In PostgreSQL 16, the trigger logic is a function returning trigger, attached with CREATE TRIGGER and EXECUTE FUNCTION. OLD and NEW are available as applicable to the operation. PostgreSQL supports BEFORE and AFTER timing, row-level and statement-level triggers, and INSTEAD OF triggers on views. Row-level triggers on partitioned tables are supported since PostgreSQL 13.

MySQL 8.0 supports BEFORE and AFTER row-level triggers for INSERT, UPDATE, and DELETE, and permits multiple triggers for the same event. It does not support INSTEAD OF triggers. A row-level BEFORE trigger for INSERT or UPDATE can modify NEW; an AFTER trigger is normally used for side effects such as inserting an audit record.

Best Practices and Common Pitfalls

  • Choose deliberately: use a function for a value, a procedure for coordinated state changes, and a trigger only for behavior that must occur automatically for every client.

  • Avoid hidden business logic: triggers can surprise ad hoc SQL sessions and make behavior harder to test and deploy. Keep them small and document their effects.

  • Prevent recursion: in PostgreSQL, a trigger that modifies its own table can fire again; use suitable conditions and WHEN clauses to prevent unbounded recursion. MySQL prohibits a trigger from modifying a table already used by the invoking statement.

  • Secure elevated routines: PostgreSQL’s SECURITY DEFINER functions should use a safe search_path and restricted EXECUTE privileges. MySQL’s SQL SECURITY DEFINER routines should use a least-privileged definer account and avoid ambiguous unqualified object names.

  • Consider performance: a row-level trigger runs once per affected row, so trigger logic can dominate bulk updates and deletes.

  • Check portability: GENERATED ALWAYS AS IDENTITY is supported by PostgreSQL 16, while MySQL 8.0 uses AUTO_INCREMENT instead. PostgreSQL supports RETURNING and the EXECUTE FUNCTION trigger syntax; MySQL 8.0 supports neither of those forms. MERGE is available in PostgreSQL 15 and later but not in MySQL 8.0.

40

How does a SQL cursor work?

A SQL cursor is a stateful database object that lets procedural code traverse a query’s rows incrementally instead of processing the result only as a complete set. It tracks a position in the associated result and supports fetching rows according to the DBMS’s cursor capabilities.

Read full answer

Applies togeneral DBMS concepts; PostgreSQL 16; MySQL 8.0 (InnoDB)

Core Concept

SQL is fundamentally set-oriented: a query returns a collection of rows. A cursor adds a procedural, row-at-a-time or batch-oriented interface to that collection for stored routines, embedded SQL, reports, and applications that require incremental processing.

A cursor commonly has the following components:

  • Result association: It is associated with a query or its result.

  • Position: It identifies the current location within that result.

  • Fetch operation: It retrieves one or more rows and updates the position.

  • Movement operation: Where supported, MOVE changes the position without returning row values.

  • Lifecycle and options: It may be scrollable or forward-only, read-only or updatable, and transaction-bound or holdable.

A cursor is not necessarily the same thing as the result set. It is the stateful access mechanism through which rows are retrieved. Depending on the DBMS and query, the underlying result may remain in a portal, be generated incrementally, or be materialized in memory.

How It Works

A typical cursor lifecycle is:

  1. Declare: Associate the cursor with a query and specify supported options.

  2. Open or make available: The DBMS prepares the query for retrieval; execution and materialization timing vary by implementation.

  3. Fetch: Retrieve the current row, a batch of rows, or rows in a particular direction.

  4. Process or reposition: Use the fetched values or move the cursor without returning them.

  5. Close: Release the cursor and any associated resources.

For example, suppose employees have salaries for IDs 101, 102, and 103, ordered by ID. A cursor that fetches two rows initially exposes 101 and 102; the next forward fetch exposes 103. Fetching a batch generally reduces network traffic and procedural overhead compared with fetching every row separately.

PostgreSQL 16 and MySQL 8.0 Differences

Aspect PostgreSQL 16 MySQL 8.0 with InnoDB
Declaration DECLARE ... CURSOR FOR query makes a cursor available for fetching Declared inside a stored procedure, function, or trigger, then opened separately
Fetching Supports forward, relative, and absolute directions Supports forward fetching with FETCH NEXT; it has no MOVE command
Navigation Can be declared SCROLL or NO SCROLL Cursors are not scrollable and are read-only
Lifetime A cursor without WITH HOLD closes when its transaction ends; a holdable cursor can survive commit A routine’s cursor is implicitly closed when the routine ends
Materialization A holdable cursor’s result is fully materialized when the transaction commits Some server-side cursor queries may still be materialized when they cannot be streamed
Client access Drivers may buffer results or retrieve them incrementally through the protocol Client libraries may buffer or stream results according to the connector and configuration

A PostgreSQL WITH HOLD cursor can outlive its transaction, but it cannot remain usable if the query depends on an object whose lifetime ends. For example, a temporary table declared ON COMMIT DROP is unavailable after the commit.

Trade-offs and Best Practices

Approach Advantages Disadvantages
Set-oriented SQL Declarative, efficient, and easy for the optimizer to optimize May transfer or materialize a large result
Row-by-row cursor Fine-grained procedural control High iteration overhead and possible network round trips
Batched cursor fetch Retains procedural control with fewer round trips Still less natural than set-based processing
  • Prefer set-based SQL using joins, aggregation, GROUP BY, and ORDER BY whenever possible.

  • Use a cursor when genuine procedural control is required, such as performing an external action for each row.

  • Fetch batches rather than issuing one round trip per row.

  • Keep transactions short and close cursors promptly.

  • For large results, inspect the connector’s buffering and streaming behavior rather than assuming that “server-side” means constant-memory execution.

  • Account for transaction isolation and concurrent updates; a cursor’s visibility behavior depends on the DBMS, its isolation level, and whether it is holdable or updatable.

41

How does a database index accelerate query execution?

A database index is an auxiliary data structure that helps the query optimizer locate matching rows without examining every row in a table. It can reduce disk and buffer-pool I/O for selective searches, ranges, joins, and some ordering operations, but it also consumes storage and adds work during inserts, updates, and deletes.

Read full answer

Applies todatabase management systems (PostgreSQL 16 and MySQL 8.4 with InnoDB)

Common Index Structures and Access Paths

An index stores search keys and information identifying the corresponding table rows.

Structure or path Useful queries Characteristics
B-tree index Equality, ranges, sorting Used by PostgreSQL and InnoDB; prefix-matching support depends on collation and, in PostgreSQL, the operator class
Hash index Exact equality PostgreSQL 16 supports hash indexes; MySQL 8.4 InnoDB does not support user-defined hash indexes
Full-text index Word searching and relevance ranking PostgreSQL and MySQL provide specialized implementations with different tokenization and ranking behavior
Bitmap index scan Low-cardinality filters, especially combined conditions PostgreSQL can combine bitmaps produced by ordinary indexes; this is an access plan, not a general-purpose bitmap index type

Most general-purpose indexes in PostgreSQL and MySQL InnoDB use B-tree variants because one structure supports equality, ranges, joins, and ordered output.

How It Speeds Up Queries

Without an index, a predicate such as department_id = 20 may require a sequential scan, reading every table row and testing the condition.

For a suitable B-tree index, the engine can:

  1. Traverse the ordered index using a small number of key comparisons.

  2. Locate the first entry matching the search key.

  3. Continue through adjacent entries for a range scan.

  4. Follow row locators to fetch only the required table rows.

  5. Avoid a separate sort when the index order matches the requested ORDER BY.

The main benefit is usually fewer pages read, especially when the table is much larger than the working set and the predicate is selective.

An index may also make a query covering: if every column needed by the query is available from the index, the optimizer may use an index-only scan. PostgreSQL still checks MVCC visibility and may fetch heap tuples when the visibility map does not establish that all required rows are visible. InnoDB secondary-index entries include the primary-key columns needed to locate complete rows.

Concrete Example

Consider an employees table:

employee_id employee_name department_id
1 Amit 10
2 Bella 20
3 Carlos 20
4 Divya 30

A query filtering department_id for 20 and ordering by employee_name returns:

employee_id employee_name
2 Bella
3 Carlos

A suitable composite index on (department_id, employee_name) supports the equality condition on its leading column and can provide the requested ordering. On this tiny table, PostgreSQL or MySQL may still choose a sequential scan because reading four rows can be cheaper than reading index pages. Indexes become more beneficial as table size, row width, and result selectivity make full scans expensive.

Textbook and Real-System Differences

  • Textbook model: An index is often described as a separate ordered file containing search keys and pointers to records.

  • PostgreSQL: A B-tree index stores entries pointing to heap tuple locations. The planner uses table statistics to estimate selectivity and compare access paths and join strategies, while queries still require MVCC visibility checks.

  • MySQL InnoDB: Table records are stored in a clustered index keyed by the primary key. Secondary-index entries include the primary key so InnoDB can locate complete rows.

  • Both systems: The optimizer, statistics, buffer pool, storage layout, and query cost model determine whether an index is used. Creating an index does not guarantee faster execution.

Trade-offs and Best Practices

Aspect Benefit Cost or risk
Reads Faster selective lookups and ranges Extra pages may be read for poor matches
Writes Can enforce uniqueness Every index must normally be updated
Storage Improves access paths Consumes additional disk and memory
Sorting May avoid a separate sort Only when index order matches the query
Constraints Efficiently checks uniqueness Requires an appropriate unique index or constraint

Practical guidance:

  • Base indexes on frequently filtered, joined, or ordered columns.

  • Apply the composite-index leading-column rule: (department_id, employee_name) can efficiently serve predicates on department_id, but generally not one on employee_name alone.

  • Judge indexes by estimated and measured work rather than selectivity alone.

  • Use PostgreSQL EXPLAIN (ANALYZE, BUFFERS) or MySQL EXPLAIN ANALYZE to inspect chosen plans and page access.

  • Avoid indexing expressions or columns without clear query benefit, and keep index statistics current.

  • Remove redundant indexes, especially when another index already provides the same access path.

42

How do clustered and non-clustered indexes differ in databases?

A clustered index stores or organizes table rows in clustering-key order, while a non-clustered index is a separate search structure whose entries point to table rows. Systems that support clustered indexes generally allow one per table and multiple secondary indexes; PostgreSQL instead uses heap tables and ordinary indexes.

Read full answer

Applies toSQL Server 2022, PostgreSQL 16, and MySQL 8.4 InnoDB

How They Work

  • Clustered index: In SQL Server and InnoDB, leaf entries contain the complete table rows. Because the index defines row order, scanning a range of the clustering key usually reads rows sequentially.

  • Non-clustered index: Its leaf entries contain the indexed columns plus a locator for the corresponding row. The database may need an additional lookup to retrieve columns not included in the index.

  • Covering index: A non-clustered index that contains every column needed by a query can satisfy that query without fetching the base table row.

  • Write cost: Inserting or updating indexed columns requires maintaining the relevant index. In InnoDB, changing the primary-key value can relocate the row in the clustered index, while updating a secondary-index key generally does not reorder the table.

Worked Example

In a system with a clustered index, consider this table:

customer_id customer_name city
101 Ada Pune
102 Lin Bengaluru
103 Maya Pune

If city is the clustering key with descending order, the table may be organized as:

customer_id customer_name city
101 Ada Pune
103 Maya Pune
102 Lin Bengaluru

A query searching for customers in Pune can scan the clustered index efficiently.

A non-clustered index on customer_name might contain:

customer_name Row locator
Ada Row for customer_id = 101
Lin Row for customer_id = 102
Maya Row for customer_id = 103

Finding Ada’s row requires an index lookup and, unless all required columns are stored in the index, retrieval of the base row.

Key Differences

Aspect Clustered Index Non-Clustered Index
Row storage Contains or organizes complete rows Contains keys and row locators
Row order Defines the table’s ordering Does not determine table row order
Number per table Usually limited to one Multiple can exist
Range scans Efficient when the query uses the clustering key May require sorting or additional row lookups
Covering queries The clustered structure naturally contains all columns Possible when required columns are included
Update impact Key changes may require moving rows Index entries must be updated, but rows need not move
Common use Primary-key access and range-heavy queries Alternate search paths, joins, and covering queries

Real-System Differences

  • PostgreSQL 16: PostgreSQL does not expose a traditional clustered-index feature. CREATE INDEX creates an ordinary access path similar in purpose to a non-clustered index, while the table’s rows remain in a heap. The CLUSTER command can physically reorder a table according to an existing index, but it is a one-time table rewrite rather than a continuously maintained clustered index.

  • MySQL 8.4 InnoDB: InnoDB organizes each table as a clustered index using the PRIMARY KEY as its clustering key. If no suitable primary key exists, InnoDB generates a hidden 6-byte ROW_ID and uses it as the clustered key. Secondary indexes are non-clustered and use the primary-key value—or the hidden ROW_ID—to locate the full row.

  • SQL Server 2022: A table may have one clustered index, which defines row order, and several non-clustered indexes. A table without a clustered index is stored as a heap, and its non-clustered indexes use the row identifier to locate rows.

Trade-offs and Best Practices

  • Prefer a compact, stable clustering key. In InnoDB, a sequential primary key such as an auto-increment integer generally reduces page splits compared with a random UUID.

  • In SQL Server, choose a clustered index for queries dominated by primary-key access, joins, and range scans over the clustering key. In InnoDB, make the same trade-off when selecting the primary key.

  • Create secondary or covering indexes for frequently filtered or joined columns, but remove redundant indexes to reduce insertion and update overhead. PostgreSQL users create ordinary indexes rather than “non-clustered” indexes.

  • A covering secondary index can outperform clustered-index access for a particular query when it matches the filter and contains every required column.

  • In PostgreSQL, use CLUSTER only when physical reordering provides a demonstrated benefit because it rewrites the table. It updates table statistics automatically by running ANALYZE, but it does not maintain the selected physical order for subsequent modifications.

43

Why do database indexes use B+ trees instead of binary search trees?

Database indexes commonly use B+ trees because they minimize disk-page accesses while preserving sorted order for range queries and ordered scans. A binary search tree has a much lower branching factor, so it requires more levels—and potentially more I/O operations—to locate the same record.

Read full answer

Applies todatabase management systems, including PostgreSQL 16 and MySQL 8 InnoDB

How a B+ Tree Works

A B+ tree is a balanced, multiway search tree designed around the fact that databases store and retrieve data in fixed-size pages.

  • Internal nodes contain separator keys and child pointers.

  • Leaf nodes contain the actual index entries and are linked in key order.

  • High fan-out: Each node can contain many keys, allowing one page to direct a search to one of hundreds or thousands of children.

  • Balanced structure: All leaves remain at approximately the same depth.

A lookup compares the search key with separators in an internal node, follows the appropriate child pointer, and repeats until reaching a leaf.

Why Disk Accesses Matter

For a balanced binary search tree containing (n) entries, the height is approximately:

[ log_2(n) ]

For a B+ tree with branching factor (F), the number of levels is approximately:

[ log_F(n) ]

Since (F) is usually much larger than 2, the B+ tree is significantly shallower.

Index structure Approximate height for 100 million entries
Binary search tree 27 levels
B+ tree with fan-out 500 3 levels

In practice, the upper tree levels are likely cached, so a lookup may require only one or two physical page reads. A binary search tree also causes more node-level comparisons and has a less page-efficient layout.

The key advantage is therefore not that a binary search tree cannot search efficiently in memory. It is that a page-oriented B+ tree reduces the number of disk-page accesses required per query.

Range Queries and Ordered Scans

B+ trees preserve entries in sorted order and connect adjacent leaf pages. This makes them suitable for queries such as SELECT * FROM orders WHERE created_at >= DATE '2026-01-01' AND created_at < DATE '2026-02-01';. The database can:

  1. Locate the first entry satisfying created_at.

  2. Follow leaf-level links while reading entries in the requested range.

A conventional binary search tree does not naturally provide an efficient ordered sequence of matching records; it would require additional traversal or separate range-index structures.

Comparison with Other Index Structures

Structure Main advantage Main limitation
Binary search tree Simple and efficient for in-memory ordered data Low fan-out and unsuitable for page-based storage
B+ tree Short tree, ordered range scans, predictable disk behavior More expensive updates and occasional page splits
Hash index Fast equality lookup Usually does not support ordering or efficient range scans
Full-text index Token and relevance-based search Specialized rather than a general-purpose ordered index
LSM-tree index Efficient writes and compression in some NoSQL systems More complex compaction and read behavior

B+ trees also support equality, sorting, grouping, joins, prefix searches, and ORDER BY operations, making them a strong default for general-purpose relational indexes.

PostgreSQL and MySQL Differences

In PostgreSQL, a B-tree index stores index tuples that can point to heap tuples or contain values needed for index-only scans. PostgreSQL’s MVCC system may require checking whether an indexed row is still visible to the current transaction.

In MySQL InnoDB, the primary-key index is a clustered B+ tree: leaf entries contain the complete row. Secondary indexes store secondary keys together with the corresponding primary-key values, which InnoDB uses to locate rows through the clustered index.

Trade-offs and Practical Guidance

  • Use a B+ tree index for columns commonly filtered by equality or ranges, joined, grouped, or sorted.

  • Composite indexes are most useful when queries use a prefix of their columns in the declared order.

  • For predicates that match a large portion of the table, a sequential scan is often cheaper than following a B+ tree index, although the index can still help with ordering, covering (index-only) queries, or joins.

  • Indexes consume storage and add work to INSERT, UPDATE, and DELETE operations.

  • Frequently updated indexes can suffer from page splits and fragmentation, although PostgreSQL and InnoDB implement mechanisms to reduce these costs.

44

When should you use a hash index rather than a B+ tree?

A hash index is best for fast equality lookups, while a B+ tree index is the more general-purpose choice because it also supports range queries and ordered results. In practice, a well-designed B+ tree is often fast enough for equality lookups, so a hash index is not automatically the better option.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.0 (InnoDB and MEMORY engines where noted)

How Hash and B+ Tree Indexes Work

  • Hash index: Applies a hash function to the search key and maps it directly to a bucket or page.

  • An exact-match lookup such as customer_id = 42 can usually locate the relevant bucket in average constant time.

  • Different keys may hash to the same bucket, creating a collision. The index handles collisions through techniques such as overflow buckets, chaining, or another implementation-specific method.

  • Because hash functions do not preserve key order, hash indexes generally do not support range scans, ORDER BY, or efficient MIN/MAX searches.

  • B+ tree index: Maintains search keys in a balanced, ordered tree.

  • Internal nodes contain separator keys that direct the search toward the correct leaf.

  • Leaf nodes contain the indexed entries and are usually linked in key order.

  • Equality lookup costs approximately O(log_f N), where f is the number of entries per page.

  • Ordered leaves allow consecutive ranges to be read efficiently without restarting the search for every value.

Worked Example

Consider an orders table:

order_id customer_id order_date
1001 42 2025-01-10
1002 42 2025-01-20
1003 84 2025-01-15

For the predicate customer_id = 42, both index types can efficiently return:

order_id customer_id order_date
1001 42 2025-01-10
1002 42 2025-01-20

A hash index on customer_id computes one bucket location and checks the matching entries there. A B+ tree traverses a short root-to-leaf path.

For the combined predicate customer_id = 42 AND order_date >= DATE '2025-01-15', the result is:

order_id customer_id order_date
1002 42 2025-01-20

A B+ tree index on (customer_id, order_date) can perform the range scan directly. A hash index on customer_id alone cannot use the order_date range efficiently.

Trade-Off Comparison

Characteristic Hash index B+ tree index
Equality lookup Average O(1) hash-table behavior O(log_f N)
Range predicates Generally unsupported Efficiently supported
Ordered results Not naturally supported Naturally supported
Collisions Possible and may require overflow handling Actual key comparisons; no hash collisions
Write maintenance Bucket growth or overflow management Page splits, merges, and balancing
Common use case Exact-match access Mixed equality, range, sorting, and ordering workloads
Worst-case behavior May degrade when many keys collide Remains balanced and predictable

The average constant-time hash lookup describes index navigation, not the entire query. Disk I/O, heap-page access, transaction visibility checks, and collision handling still affect actual latency.

Behavior in Real Database Systems

  • PostgreSQL 16: Supports hash indexes through USING HASH. They are intended primarily for equality access and are less useful for range scans or ordering. The query planner chooses between available indexes using cost estimates and statistics, so a hash index does not guarantee faster execution. A B+ tree is the default and usually remains the safer choice for general workloads.

  • MySQL 8.0 InnoDB: Uses clustered and secondary B+ tree indexes. It also has an internal adaptive hash index, which automatically accelerates certain repeated equality lookups on B+ tree pages. This is not a general-purpose user-created SQL hash index.

  • MySQL 8.0 MEMORY engine: Supports explicitly created HASH indexes in addition to BTREE indexes. Its limitations include the engine’s nontransactional and volatile nature.

These implementations add concurrency control, crash recovery, and MVCC behavior that the textbook hash-file and B+ tree models simplify.

Choosing the Right Index

Prefer a hash index when:

  • Queries almost always use exact equality on the indexed columns.

  • The workload does not need range scans, sorting, or index-order output.

  • The index provides a measurable benefit for a high-volume lookup workload.

Prefer a B+ tree index when:

  • Queries use inequalities, BETWEEN, range predicates, or ORDER BY.

  • The index must support ordered scans or minimum/maximum searches.

  • The same index must serve several different query patterns.

  • Predictable, broadly applicable behavior is more important than a small lookup advantage.

A common pitfall is assuming that hash indexes are always faster. Measure them with representative data and queries using tools such as PostgreSQL’s EXPLAIN (ANALYZE, BUFFERS), and include write performance, index size, cache effects, and maintenance cost in the decision.

45

How does column order affect a composite SQL index?

A composite index stores multiple columns as one ordered index key. In a B-tree, column order controls how entries are grouped and searched, which predicates can seek directly to matching keys, and which sort orders the index can provide without an additional sort.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.0.13+ (InnoDB) B-tree composite indexes

How B-Tree Ordering Works

For an index ordered by (tenant_id, last_name, first_name), entries are grouped first by tenant_id. Within one tenant, entries are ordered by last_name, and entries sharing that value are ordered by first_name.

The comparison uses each column’s relevant SQL operator class and collation; text columns therefore need not use binary or case-sensitive ordering.

This produces the leftmost-prefix behavior of a B-tree:

  • A predicate on the first key column can directly locate a range of entries.

  • Additional equality predicates on subsequent columns can narrow that range.

  • A later column cannot normally be used as a direct search key when an intervening column has no usable constraint.

  • After a range predicate on one column, later columns generally cannot substantially narrow the range, although they can still be evaluated as filters.

Effects on Predicates and Ordering

Assume two indexes exist: one ordered by (tenant_id, last_name, first_name) and another by (last_name, first_name).

Query or ordering requirement (tenant_id, last_name, first_name) (last_name, first_name)
tenant_id = 10 Direct seek by tenant No direct seek by tenant
tenant_id = 10 AND last_name = 'Patel' Direct seek using both columns Can seek by last_name, then filter tenant_id
last_name = 'Patel' No direct seek in PostgreSQL 16 Direct seek by last name
tenant_id = 10 AND first_name = 'Asha' Seeks by tenant, but cannot directly seek by first_name because last_name is unconstrained No direct seek by first_name
ORDER BY last_name, first_name Supports this order only after a fixed tenant prefix Supports the global ordering

MySQL 8.0.13 and later can sometimes use a skip scan when the first index column has low cardinality and a later column is constrained. This is an optimization exception, not a guarantee, so plans should be checked rather than assumed.

Concrete Example

Suppose a customers table contains:

tenant_id last_name first_name
10 Patel Asha
10 Patel Ravi
10 Shah Neha
20 Patel Karan

With an index ordered by (tenant_id, last_name, first_name), a query filtering for tenant 10 and ordering by last name and first name can seek directly to tenant 10 and read matching entries in the required order. Its result is:

tenant_id last_name first_name
10 Patel Asha
10 Patel Ravi
10 Shah Neha

An index ordered by (last_name, first_name) is more appropriate when filtering or sorting primarily by name across all tenants.

Choosing an Order

  • Place equality predicates before range predicates: Equality keys narrow the searchable portion of the B-tree, allowing a later range column to be evaluated efficiently.

  • Consider partial predicate reuse: An index beginning with a column that many queries constrain can support more query shapes.

  • Do not order equality columns blindly by selectivity: When several equality columns are constrained, their relative order usually does not change whether all can be used, although it can affect partial-query usability and scan cost.

  • Match common sorting requirements: Put columns used for ordering after equality columns and before any range column when the intended sort order permits it. Direction must also match.

  • Avoid unnecessary key columns: Each additional key column increases index size and the cost of inserts, updates, and deletes.

  • Consider covering indexes: PostgreSQL 16 INCLUDE columns store additional values without changing the index’s key order or uniqueness. They can enable an index-only scan when all required columns are present and the visibility requirements are satisfied.

Trade-offs and System Differences

Composite indexes consolidate related access paths, but they do not replace every single-column index. The best order depends on actual predicates, sort requirements, data distribution, and workload.

PostgreSQL 16 may choose a sequential scan, bitmap heap scan, or index scan instead of a composite-index scan. MySQL InnoDB also applies leftmost-prefix behavior, with skip scan and index condition pushdown available in applicable versions. Other index types, such as PostgreSQL GIN, GiST, and BRIN, do not provide exactly the same ordering and prefix semantics as a B-tree. Validate important designs with EXPLAIN ANALYZE using realistic data and parameter values.

46

What is a covering index in a database?

A covering index contains every column required to answer a specific query, allowing the database to retrieve the needed values from the index without reading the corresponding base-table rows. The database may still inspect the table to verify row visibility, depending on its storage engine and transaction state.

Read full answer

Applies todatabase management systems (PostgreSQL 16 and MySQL 8.4 InnoDB)

How It Works

Indexes normally organize selected key columns into a searchable structure such as a B-tree. A query is covered when all columns it needs—both filtering columns and selected output columns—are available in the index.

The important distinction is:

  • Covering index: The index contains all columns needed by a query.

  • Index-only scan: The query planner chooses an execution path that retrieves the required values from the index.

A covering index does not guarantee an index-only scan. The optimizer must consider estimated cost, available statistics, index layout, and storage-engine behavior.

Worked Example

Consider an employees table and the query SELECT name, salary FROM employees WHERE department_id = 10.

An index containing department_id, name, and salary can satisfy the entire query from the index. An index containing only department_id cannot provide the projected name and salary values without consulting the base table.

The result is:

name salary
Aisha Khan 90000.00
Rohan Shah 78000.00

In PostgreSQL 16, an index on department_id with name and salary as INCLUDE columns can cover this query. Included columns are stored in leaf entries but do not affect the index’s ordering. PostgreSQL may report an Index Only Scan, although it can still access heap pages when the visibility map cannot establish that the indexed rows are visible to the current transaction.

In MySQL 8.4 InnoDB, the equivalent design is a composite index whose key columns are department_id, name, and salary. InnoDB secondary indexes also contain the primary-key columns needed to locate rows in the clustered index.

PostgreSQL and MySQL Differences

System Covering-index behavior
PostgreSQL Supports INCLUDE columns. An index-only scan can still visit the heap to confirm row visibility under MVCC.
MySQL InnoDB Does not support PostgreSQL’s INCLUDE syntax; relevant columns are placed in a composite index. Secondary indexes also contain the primary-key values used as row locators.

MySQL’s traditional EXPLAIN output may report Using index when the selected access path is covered by an index.

Advantages and Trade-offs

  • Advantages:

  • Can avoid base-table lookups and reduce physical I/O.

  • Can improve selective point queries and range scans.

  • Is useful for read-heavy workloads with predictable access patterns.

  • Trade-offs:

  • Larger indexes consume more disk space and buffer-cache memory.

  • Inserts and updates must maintain additional index data, increasing write overhead.

  • Key-column order can limit which predicates and projections an index efficiently supports.

  • The planner may still choose a sequential scan, especially when many rows match.

Best Practices and Common Pitfalls

  • Include only columns genuinely needed by important queries.

  • Design composite indexes around realistic predicates and projections.

  • Verify actual plans with EXPLAIN rather than assuming a covering index will be used.

  • Balance read performance against index size and write cost.

  • Remember that covering indexes help most when the query returns a relatively small portion of the table; they are generally less valuable for low-selectivity predicates that match many rows.

47

When does adding an index degrade database performance?

Adding an index can make performance worse when the overhead of maintaining the index outweighs its benefits for read operations. This typically occurs in write-heavy environments, on small tables, or when the index is redundant or poorly chosen.

Read full answer

Applies toall versions

How Indexes Work and Their Overheads

  • Read acceleration: B-tree indexes allow O(log n) lookups instead of O(n) sequential scans, dramatically speeding up selective queries.

  • Write overhead: Every INSERT, UPDATE, or DELETE must modify the index structure, adding I/O and CPU time.

  • Storage cost: Each index duplicates part of the table data, increasing disk usage.

  • Lock contention: Index modifications may hold locks longer, blocking concurrent transactions.

When Adding an Index Degrades Performance

  • Small tables: If the table has few rows or fits entirely in memory, a sequential scan is already fast; the index adds unnecessary overhead for every write.

  • Low-selectivity columns: Indexing a column with few distinct values (e.g., a boolean flag) rarely helps reads but always costs writes.

  • Write-heavy workloads: In OLTP systems with many inserts/updates, each write must update all indexes on the table. The cumulative cost can dominate.

  • Unused indexes: An index that is never or rarely used still must be maintained, wasting resources.

  • Redundant indexes: Multiple indexes on the same column or overlapping columns increase maintenance cost without adding read benefit.

  • Bulk data loads: During large INSERT/LOAD operations, each row updates every index, dramatically slowing the load. It is often better to drop indexes before a bulk load and recreate them afterwards.

  • Fragmentation: Over time, index pages can become fragmented, degrading read performance and increasing I/O.

  • Optimizer confusion: Stale statistics or too many indexes can cause the query planner to choose a suboptimal plan, such as using an index where a sequential scan would be faster.

Trade-offs and Decision Guidelines

Scenario Index Recommended? Reason
Small table (< 10k rows) Usually no Sequential scan is fast; index overhead not justified
Write-heavy table Only if reads are critical Each write must update indexes; balance read gain vs write cost
Low-cardinality column No Index not selective; rarely used by optimizer
Column used in WHERE/JOIN Yes Speeds up selective queries
Covering index (includes all needed columns) Yes Avoids table lookups, but adds write cost

Best Practices

  • Index columns that appear frequently in WHERE, JOIN, ORDER BY, or GROUP BY clauses.

  • Avoid indexing low-cardinality columns unless they are part of a composite index with high-cardinality columns.

  • Use partial indexes (PostgreSQL) or filtered indexes (SQL Server) to index only a subset of rows.

  • Monitor index usage with database-specific views: pg_stat_user_indexes in PostgreSQL, sys.dm_db_index_usage_stats in SQL Server.

  • Drop or disable unused indexes; they still cost write overhead.

  • For bulk loads, consider dropping indexes before the load and recreating them afterwards.

  • Rebuild or reorganize indexes periodically to reduce fragmentation.

  • Keep statistics up to date with ANALYZE (PostgreSQL) or UPDATE STATISTICS (SQL Server).

48

What is a database transaction in a DBMS?

A database transaction is a logical unit of database work whose operations are committed together or rolled back together. A DBMS provides transaction guarantees through the ACID properties while allowing multiple transactions to execute concurrently.

Read full answer

Applies torelational DBMS transactions (PostgreSQL 16 and MySQL 8.0 with InnoDB)

Core Concept

A transaction groups one or more SQL statements, such as INSERT, UPDATE, DELETE, and SELECT, into a single unit of work. An explicit transaction typically follows this sequence:

  1. Begin with BEGIN or START TRANSACTION.

  2. Execute one or more statements.

  3. Commit with COMMIT, making the changes durable, or roll back with ROLLBACK, undoing its uncommitted changes.

With autocommit enabled, PostgreSQL and MySQL execute each statement as its own transaction. The DBMS uses logging, locking, multiversion concurrency control, or a combination of these mechanisms to provide the required guarantees.

ACID Properties

  • Atomicity: The effects of the transaction’s operations are committed as one unit or discarded when the transaction is rolled back. A statement error does not automatically discard the entire transaction in every DBMS: PostgreSQL normally marks the transaction as aborted until it is rolled back or recovered to a savepoint, while MySQL InnoDB normally rolls back only the failed statement and leaves the transaction active. The application must explicitly roll back when the entire unit should be undone.

  • Consistency: A transaction transforms data from one valid state to another according to database constraints. Business rules that database constraints cannot express must also be enforced by application logic within the transaction.

  • Isolation: Concurrent transactions should not observe intermediate or invalid combinations of one another’s work, although the exact visibility depends on the isolation level.

  • Durability: After a successful COMMIT, committed changes remain recoverable after a normal failure, subject to the database’s durability configuration and the reliability of its storage.

Isolation and Concurrency

Different isolation levels trade correctness for concurrency:

Isolation level PostgreSQL 16 MySQL 8.0 InnoDB
READ UNCOMMITTED Treated as READ COMMITTED; dirty reads are not allowed Permits dirty reads
READ COMMITTED Prevents dirty reads; each statement can observe a newer committed snapshot Prevents dirty reads; each consistent read can use a newer read view
REPEATABLE READ Provides a stable snapshot for ordinary reads, but does not guarantee serializable execution Consistent nonlocking reads use a transaction-level read view; locking reads use current reads
SERIALIZABLE Uses snapshot isolation plus predicate-lock conflict detection Uses stronger locking, including next-key locks

PostgreSQL defaults to READ COMMITTED and primarily uses multiversion concurrency control, or MVCC, for snapshot-based reads. MySQL InnoDB defaults to REPEATABLE READ and combines MVCC with locking mechanisms such as next-key locks. Serializable conflicts or deadlocks may cause the DBMS to abort one transaction so that the application can retry it.

Concrete Example

Suppose account 1 has a balance of 1000 and account 2 has a balance of 2000. A transfer of 300 can use one transaction containing both the debit and credit operations. If the transaction commits, the result is:

account_id balance
1 700
2 2300

If the transaction is rolled back, the balances remain 1000 and 2000. If the debit violates a balance constraint, PostgreSQL aborts the transaction; InnoDB rolls back the failed statement by default, so the application must request a full rollback if neither side of the transfer should remain applied.

Best Practices and Pitfalls

  • Keep transactions short because long-running transactions retain locks or snapshots and increase contention.

  • Access related tables in a consistent order to reduce deadlocks.

  • Handle commit failures and retry serialization failures or deadlocks when the complete operation is safe to repeat.

  • Do not perform network calls or user interaction inside a transaction because the transaction may wait while holding database resources.

  • Do not assume that all DDL is transactional across engines. PostgreSQL supports transactional DDL. In MySQL 8.0, most DDL statements cause implicit commits; atomic DDL makes many InnoDB DDL operations crash-safe but does not make them freely rollbackable within a larger transaction.

  • Use savepoints for recoverable subparts when supported. Rolling back to a savepoint only undoes changes made after that savepoint in the current transaction; it cannot undo an earlier committed transaction.

49

How do ACID properties apply to database transactions?

ACID properties define the guarantees a reliable database provides for transactions: Atomicity, Consistency, Isolation, and Durability. Together, they ensure that a transaction’s database effects are all-or-nothing, preserve valid database states, behave predictably under concurrency, and remain committed after failures.

Read full answer

Applies todatabase management systems (PostgreSQL 16 and MySQL 8.0 InnoDB)

What Each Property Guarantees

Property Guarantee Example
Atomicity A transaction’s database effects are indivisible: either all are committed or none become visible as a committed result. A transfer cannot commit the debit while losing the corresponding credit.
Consistency The transaction’s logical effects move the database from one valid state to another while respecting declared constraints. Application code must enforce additional business invariants. A transfer preserves the sum of account balances and does not create a negative balance.
Isolation The isolation level controls which effects of concurrent transactions a transaction may observe and which concurrency anomalies are possible. Under PostgreSQL’s default READ COMMITTED, a transaction cannot read uncommitted changes.
Durability Once a commit is acknowledged, the committed changes survive application failures, database crashes, and power failures, subject to the selected durability configuration. A successful payment remains recorded after the server restarts.

Atomicity and durability are primarily addressed by transaction logging and recovery, while isolation is primarily a concurrency-control concern. Consistency depends on correct transaction logic, schema constraints, and an appropriate isolation level—not on ACID alone.

How Database Systems Enforce Them

  • Atomicity: PostgreSQL uses write-ahead logging for crash recovery and transaction-abort handling for rollback. MySQL InnoDB uses undo information for rollback and redo logging for crash recovery.

  • Consistency: DBMSs enforce declared constraints such as PRIMARY KEY, FOREIGN KEY, UNIQUE, NOT NULL, and CHECK. Application code must still enforce multi-row business rules such as preserving the total balance during a transfer.

  • Isolation: Locking or multiversion concurrency control determines what concurrent transactions can see. Common anomalies include:

  • Dirty read: reading uncommitted data.

  • Non-repeatable read: reading the same row twice but obtaining different committed values.

  • Phantom read: a repeated query obtains additional rows inserted by a concurrent committed transaction.

  • Durability: Write-ahead logging records committed changes before they are made durable according to the database’s configuration. Recovery can then replay those changes after a crash.

PostgreSQL 16 defaults to READ COMMITTED and uses MVCC. MySQL 8.0 InnoDB defaults to REPEATABLE READ and combines MVCC with locking reads. SERIALIZABLE provides the strongest standard isolation guarantee, but it can increase contention or cause transaction failures. PostgreSQL may abort transactions with serialization failures, while InnoDB’s SERIALIZABLE level uses stronger locking and can produce deadlocks.

Worked Transfer Example

Suppose two accounts start with these balances:

Owner Before After
Asha 1000.00 900.00
Ravi 500.00 600.00

The debit and credit are performed within one transaction. If either operation fails or violates a constraint, the transaction is aborted and rollback leaves both original balances unchanged. If all operations succeed, the commit makes both changes visible together; the total balance of 1500.00 is preserved. This illustrates atomicity and consistency, while the database’s recovery mechanisms provide durability.

Trade-offs and Best Practices

  • Use transactions narrowly: Keep them short and avoid network calls or user interaction inside them, because long transactions increase lock duration and contention.

  • Choose isolation deliberately: READ COMMITTED generally permits more concurrency, while REPEATABLE READ provides more stable reads. Their exact guarantees differ between PostgreSQL and InnoDB.

  • Handle serialization failures: PostgreSQL applications should retry transactions aborted under SERIALIZABLE when the operation is safe to repeat.

  • Understand durability settings: Changing PostgreSQL’s synchronous_commit or MySQL’s innodb_flush_log_at_trx_commit can improve performance at the cost of permitting recent commits to be lost in an operating-system or power failure.

  • Do not rely on ACID for every business concern: The DBMS can enforce declared constraints, but application code must validate permissions, balances, affected-row counts, and other domain rules. External effects such as calling a payment provider are also not covered by the database transaction.

50

What are the states of a database transaction?

In database systems, a transaction progresses through a sequence of well-defined states that reflect its execution status and determine its final outcome. Understanding these transaction states is essential for grasping how DBMSs ensure ACID properties, especially atomicity and durability.

Read full answer

Applies toRelational database management systems (PostgreSQL, MySQL/InnoDB, Oracle, SQL Server) and the standard transaction model taught in database courses.

Standard Transaction States

The lifecycle of a transaction is typically divided into five or six states, depending on the textbook or system.

State Description
Active The transaction is currently executing; it has not yet issued a COMMIT or ROLLBACK. This is the normal working state.
Partially Committed The transaction has executed its final statement (e.g., COMMIT) but the system has not yet written all data to disk or completed the commit protocol. In this state, the commit is not yet durable, and its changes are normally not yet visible to other transactions.
Committed The transaction has successfully completed all its operations, and the system has guaranteed that its effects are permanently stored. The transaction is now finished.
Failed The transaction cannot proceed normally due to an error, such as a constraint violation, system crash, or deadlock. It must be rolled back.
Aborted The transaction has been rolled back; all its changes have been undone. The system may either terminate the transaction or allow it to be restarted (though typically it is terminated).
Terminated (Optional) After either commit or abort, the transaction is removed from the system. Some texts combine this with the final state.

State Transitions

  • Active → Partially Committed: The transaction executes its final statement, typically a COMMIT. At this point, the transaction’s work is logically complete, but the system must still ensure durability (e.g., by flushing log records).

  • Partially Committed → Committed: The recovery manager finishes the commit protocol (e.g., writes a commit log record and forces it to stable storage). Once this is done, the transaction is committed and its changes are durable.

  • Active → Failed: An error occurs that prevents the transaction from continuing. Common causes include constraint violations, deadlocks, system crashes, or explicit ROLLBACK statements.

  • Failed → Aborted: The system initiates rollback, using the log to undo all changes made by the transaction. After rollback, the transaction is in the aborted state.

  • Aborted → Terminated: The transaction is cleaned up and removed from the system. Some systems allow the application to restart the transaction as a new transaction, but the original transaction is considered terminated.

In practice, a transaction may go directly from Active to Aborted if a ROLLBACK is issued, skipping the Failed state.

How the DBMS Enforces These States

Internally, the DBMS maintains a transaction table that records the state of each active transaction. The recovery manager uses a write-ahead log (WAL) to ensure that changes are durable. When a transaction commits, the system forces the commit log record to disk before acknowledging the commit. If a crash occurs, the recovery system scans the log: committed transactions are redone, and aborted ones are undone, restoring the database to a consistent state.

Differences in PostgreSQL and MySQL/InnoDB

  • PostgreSQL: Uses MVCC (Multi-Version Concurrency Control) with snapshot isolation and row-level locking. Each backend tracks its transaction’s state, the outcome is recorded in the commit log (pg_xact), and a commit becomes durable when its WAL commit record is flushed; the background writer and checkpointer only write dirty data pages. The pg_stat_activity view can show the current state of a query (e.g., idle in transaction), which hints at the transaction’s state.

  • MySQL/InnoDB: Also uses a redo log and undo logs. The state transitions are similar, but the terminology may differ. InnoDB’s rollback is handled via undo logs, and the commit is made durable by flushing the redo log.

Both systems hide the internal states from users; the only visible outcomes are success or error messages. The conceptual model of active, partially committed, committed, failed, aborted, and terminated is universal across relational databases and is the foundation of transaction processing.

51

What is a schedule and serializability in DBMS?

A schedule is a chronological ordering of operations from database transactions that preserves the original order of operations within each transaction. A schedule is serializable when it is equivalent to some serial schedule—some execution in which each transaction completes before the next begins—even when the original transactions are interleaved.

Read full answer

Applies torelational DBMS theory (all versions); PostgreSQL 16; MySQL 8.0 InnoDB

Schedule and Serial Schedule

A transaction commonly contains the following operations:

  • R_i(X): transaction T_i reads database item X

  • W_i(X): transaction T_i writes database item X

  • Commit_i: transaction T_i commits

  • Abort_i: transaction T_i aborts

A serial schedule executes all operations of one transaction before any operation of another transaction. Serial execution is simple to reason about, but it provides little concurrency.

An interleaved schedule mixes operations from multiple transactions while preserving each transaction’s internal order. Such a schedule need not be incorrect: concurrency is safe when its result remains equivalent to that of an appropriate serial schedule.

Worked Example

Assume the initial values are A = 100 and B = 200, and the transactions perform these writes:

Transaction Read Write
T1 R1(A) W1(B = 100)
T2 R2(B) W2(A = 300)

Consider this interleaved schedule:

Step Operation
1 R1(A)
2 R2(B)
3 W2(A = 300)
4 W1(B = 100)
5 Commit1
6 Commit2

Compare it with the two possible serial orders:

Observable result Interleaved T1 → T2 T2 → T1
Value read by T1 from A 100 100 300
Value read by T2 from B 200 100 200
Final value of A 300 300 300
Final value of B 100 100 100

The interleaved schedule has the same final state as both serial schedules, but its values read differ from each one. Therefore, it is not serializable. This demonstrates why checking only the final database state is insufficient.

Conflict Serializability

Two operations conflict when they:

  • Belong to different transactions

  • Access the same item

  • Include at least one write operation

To test conflict serializability, construct a precedence graph:

  • Each transaction is represented by a node.

  • Add an edge Ti → Tj when a conflicting operation of Ti occurs before a conflicting operation of Tj.

A schedule is conflict-serializable exactly when this graph is acyclic.

In the example:

  • R1(A) occurs before W2(A), producing T1 → T2.

  • R2(B) occurs before W1(B), producing T2 → T1.

The graph contains the cycle T1 → T2 → T1, so the schedule is not conflict-serializable.

Real Database Behavior

Aspect Textbook model PostgreSQL 16 MySQL 8.0 InnoDB
Concurrency control Operation-level schedules and conflict analysis MVCC with snapshot-based isolation MVCC for consistent reads, with locking for writes and locking reads
Default isolation level Not applicable READ COMMITTED REPEATABLE READ
SERIALIZABLE implementation Preserves serializability through schedule equivalence Serializable Snapshot Isolation detects serialization anomalies and may abort one transaction Uses locking, including next-key and gap locking for affected ranges
Dirty reads Possible in some non-serial schedules Prevented at every isolation level Prevented at standard isolation levels
Non-repeatable and phantom reads Possible depending on the schedule READ COMMITTED permits both READ COMMITTED permits both; consistent reads under REPEATABLE READ prevent non-repeatable reads but not all phantoms

Both PostgreSQL and InnoDB use MVCC to let consistent readers and writers make progress concurrently, but they also use locks in important cases. Their SERIALIZABLE implementations therefore do not work by literally executing transactions one after another.

Practical Guidance

  • Use SERIALIZABLE when application invariants require behavior equivalent to serial execution; a lower isolation level may provide better concurrency.

  • In PostgreSQL, serialization failures normally use SQLSTATE 40001. After such a failure, roll back and retry the entire transaction, ensuring that repeating it is safe.

  • In MySQL InnoDB, applications may instead encounter blocking, lock-wait timeouts, or deadlocks. Retry according to the specific error and application policy rather than retrying every failure indiscriminately.

  • Do not equate an interleaved schedule with an incorrect one. The schedule is incorrect only when it fails the required serializability property.

52

How do conflict serializability and view serializability differ?

Conflict serializability preserves the relative order of every pair of conflicting operations, making the schedule equivalent to a serial schedule. View serializability requires only the values read and final values written to match some serial schedule; therefore, every conflict-serializable schedule is view-serializable, but the reverse is not always true.

Read full answer

Applies toDBMS transaction scheduling (general relational databases, PostgreSQL 16, and MySQL 8.0/8.4 InnoDB)

Core Definitions

Two operations conflict when they:

  • Access the same data item.

  • Belong to different transactions.

  • Include at least one write.

Examples include read(X) versus write(X), write(X) versus read(X), and write(X) versus write(X). Two reads of the same item do not conflict.

Property Conflict serializability View serializability
Required equivalence Conflict-equivalent to a serial schedule View-equivalent to a serial schedule
Preserved behavior Order of all conflicting operations Values read and final values written
Main test Precedence graph is acyclic Find a serial schedule with matching reads and final writes
Strength Stronger Weaker
Relationship Implies view serializability Does not imply conflict serializability

View serializability does not merely mean that the final database state is identical. The transactions must also observe the same values as they would in the corresponding serial schedule.

Conflict Serializability Test

Build a precedence graph:

  • Each transaction is a node.

  • Add an edge Ti → Tj when an operation in Ti precedes a conflicting operation in Tj.

  • The schedule is conflict serializable exactly when the graph contains no directed cycle.

An acyclic graph has a topological ordering that can be used as the equivalent serial transaction order. Conflict serializability is especially useful because it can be checked efficiently with standard cycle-detection algorithms.

Worked Example

Consider two items, X and Y, initially containing 0:

  • T1: W(X), W(Y)

  • T2: W(X), R(Y)

  • T3: W(X), W(Y)

The concurrent schedule is:

Step Operation Value affected or observed
1 w2(X = 1) X = 1
2 w1(X = 2) X = 2
3 w1(Y = 3) Y = 3
4 r2(Y) Reads 3 from T1
5 w3(X = 4) X = 4
6 w3(Y = 5) Y = 5

The conflict graph contains:

  • w2(X) before w1(X), producing T2 → T1.

  • w1(Y) before r2(Y), producing T1 → T2.

This forms the cycle T1 → T2 → T1, so the schedule is not conflict serializable.

However, it is equivalent to the serial schedule T1 → T2 → T3:

Observable result Concurrent schedule Serial T1 → T2 → T3
Value read by T2 Y = 3 from T1 Y = 3 from T1
Final X 4, written by T3 4, written by T3
Final Y 5, written by T3 5, written by T3

Thus, the schedule is view serializable but not conflict serializable. The overwritten intermediate writes make the difference visible.

PostgreSQL and MySQL InnoDB

  • PostgreSQL 16: The default READ COMMITTED isolation level is not serializable. SERIALIZABLE uses Serializable Snapshot Isolation, tracking read-write dependencies and aborting transactions when serialization failures are possible.

  • MySQL InnoDB: The default REPEATABLE READ level is also not fully serializable. SERIALIZABLE uses locking, including next-key locks where necessary, to prevent nonserializable execution.

  • View serializability is not normally implemented as a separate isolation level because it does not by itself prevent dangerous intermediate histories or anomalies such as write skew.

Trade-offs and Common Pitfalls

  • Conflict serializability is stricter and relatively easy to test, but it can reject schedules that are still view serializable.

  • View serializability permits more concurrency, but exact checking is computationally harder and it provides less assurance about internal execution order.

  • Do not equate snapshot isolation or repeatable-read isolation with serializability.

  • Do not confuse “same final database state” with view equivalence; the values observed by each transaction must also match the serial schedule.

  • When an interview asks how to test serializability, use the precedence graph and explain that an acyclic graph establishes a valid serial ordering.

53

How to test conflict serializability using a precedence graph?

Conflict serializability is a property of database transaction schedules; a schedule is conflict serializable if its precedence graph (or conflict graph) contains no cycles. In this model, nodes represent transactions and directed edges represent conflicting operations ordered by their execution.

Read full answer

Applies torelational database management systems (conflict serializability theory; PostgreSQL 16 and MySQL 8.0 InnoDB as reference systems)

Precedence Graph Construction

  • Nodes: Each transaction participating in the schedule becomes a node.

  • Edges: For every pair of operations from different transactions that conflict — they access the same data item and at least one of them is a write — add a directed edge from the transaction whose operation appears earlier in the schedule to the transaction whose operation appears later.

  • One edge per conflicting pair: different conflicting pairs between the same two transactions may point in opposite directions (T1 → T2 and T2 → T1), which immediately yields a two-node cycle. Never collapse them into a single edge based on the “earliest” conflict.

Testing for Conflict Serializability

  1. Build the precedence graph by enumerating all conflicting operation pairs across transactions.

  2. Check whether the graph contains a cycle, using depth-first search (three-colour marking) or any standard cycle-detection algorithm.

  3. If the graph is acyclic, the schedule is conflict serializable; any topological ordering of the nodes yields a serial schedule equivalent to it.

  4. If the graph contains a cycle, the schedule is not conflict serializable and cannot be reordered into an equivalent serial execution.

Example

Consider two transactions T1 and T2, each reading and writing data item A.

Schedule S1 (conflict serializable):

Order Operation
1 R1(A)
2 W1(A)
3 R2(A)
4 W2(A)

Conflicting pairs: - W1(A) with R2(A) → T1 → T2 - W1(A) with W2(A) → T1 → T2 - R1(A) with W2(A) → T1 → T2

Precedence graph: T1 → T2. No cycle → conflict serializable; equivalent serial order: T1, T2.

Schedule S2 (not conflict serializable):

Order Operation
1 R1(A)
2 R2(A)
3 W1(A)
4 W2(A)

Conflicting pairs: - R2(A) with W1(A) → T2 → T1 - W1(A) with W2(A) → T1 → T2 - R1(A) with W2(A) → T1 → T2

Graph: T1 → T2 and T2 → T1 → cycle → not conflict serializable. (R1(A) and R2(A) do not conflict: both are reads.)

Code Example

# S2: R1(A), R2(A), W1(A), W2(A)  -- two conflicting transactions
schedule = [("T1", "R", "A"), ("T2", "R", "A"), ("T1", "W", "A"), ("T2", "W", "A")]

# Step 1: build the precedence graph -- one edge per conflicting operation pair
graph = {txn: set() for txn, _, _ in schedule}
for i, (t1, op1, item1) in enumerate(schedule):
    for t2, op2, item2 in schedule[i + 1:]:
        # conflict = same item, different transaction, at least one write
        if t1 != t2 and item1 == item2 and "W" in (op1, op2):
            graph[t1].add(t2)   # earlier operation's transaction -> later one

# Step 2: cycle detection with DFS (three-colour marking)
WHITE, GREY, BLACK = 0, 1, 2
colour = {txn: WHITE for txn in graph}

def dfs(txn):
    colour[txn] = GREY
    for nxt in graph[txn]:
        if colour[nxt] == GREY:          # back edge -> cycle
            return True
        if colour[nxt] == WHITE and dfs(nxt):
            return True
    colour[txn] = BLACK
    return False

has_cycle = any(colour[t] == WHITE and dfs(t) for t in graph)
print("Edges:", {t: sorted(s) for t, s in graph.items()})
print("Conflict serializable:", not has_cycle)
# Edges: {'T1': ['T2'], 'T2': ['T1']}
# Conflict serializable: False

Limitations and Considerations

  • Conflict serializability is a sufficient condition for serializability but not a necessary one; view serializability is more general yet harder to test algorithmically.

  • The precedence graph is a theoretical tool; a real scheduler enforces serializability indirectly rather than by maintaining an explicit graph.

  • PostgreSQL 16 uses MVCC: the default READ COMMITTED level is not conflict serializable (write skew is possible), and only SERIALIZABLE — implemented as Serializable Snapshot Isolation (SSI) with predicate locks — guarantees serializability.

  • MySQL 8.0 InnoDB also uses MVCC: the default REPEATABLE READ is snapshot isolation and can suffer write skew, while SERIALIZABLE strengthens it (plain SELECT takes shared locks, gap locks block phantoms) and does guarantee serializability.

  • Injected conflicts are handled by rolling back one transaction: PostgreSQL’s SSI aborts on a dangerous rw-antiparallel structure, InnoDB aborts on lock waits/deadlocks.

Best Practices

  • Treat conflict serializability as the theoretical foundation for locking-based concurrency control (2PL, recoverable schedules, deadlock handling).

  • For manual testing, list the operations in order, underline the write operations as in textbook schedule notation, and pair every read/write and write/write pair across different transactions.

  • If the graph is acyclic, run a topological sort to obtain the serial order and confirm it reproduces the same final database state.

  • Missing a single conflicting pair can flip the verdict, so enumerate systematically.

  • In production, rely on the DBMS’s isolation levels (SERIALIZABLE where serializability is required) rather than testing schedules after the fact.

54

What are recoverable and cascadeless transaction schedules?

A recoverable schedule is one in which a transaction that reads another transaction’s uncommitted value commits only after the writer commits. A cascadeless schedule additionally prevents cascading rollback by requiring the writer to commit before the dependent transaction performs a write following that read.

Read full answer

Applies todatabase transaction scheduling concepts; PostgreSQL 16 and MySQL 8.0 InnoDB

Core Concepts

A schedule is an ordering of operations from multiple transactions. Common operations include:

  • rᵢ(X): transaction Tᵢ reads item X

  • wᵢ(X): transaction Tᵢ writes item X

  • cᵢ: transaction Tᵢ commits

  • aᵢ: transaction Tᵢ aborts

Suppose T₂ reads an item written by T₁. This is a read-from dependency, often represented as T₁ → T₂.

Schedule property Required ordering Main guarantee
Recoverable c₁ occurs before c₂ A dependent transaction never commits before the transaction from which it read
Cascadeless c₁ occurs before T₂’s first write after the read, and also before c₂ An abort of T₁ cannot leave committed dependent work based on T₁’s uncommitted value
Conflict-serializable Conflicting operations preserve the order of some serial schedule The result is equivalent to a serial execution

Recoverable and cascadeless schedules primarily address failure recovery. Neither property alone guarantees conflict serializability.

Recoverable Schedule Example

Consider:

Order Operation
1 w₁(X)
2 r₂(X)
3 w₂(Y)
4 c₁
5 c₂

T₂ reads the value written by T₁ and commits only after T₁ commits. Therefore, the schedule is recoverable.

However, it is not cascadeless because T₂ writes Y before T₁ commits. If T₁ had aborted instead of committing, T₂’s write would have to be rolled back. This is a cascading rollback.

Cascadeless Schedule Example

Consider:

Order Operation
1 w₁(X)
2 c₁
3 r₂(X)
4 w₂(Y)
5 c₂

Here, T₁ commits before T₂ reads X and writes Y. The schedule is both recoverable and cascadeless. If T₁ aborts, it does so before T₂ performs a dependent write, so no cascading rollback is required.

By contrast, this schedule is not recoverable:

Order Operation
1 w₁(X)
2 r₂(X)
3 c₂
4 a₁

T₂ commits after reading uncommitted data from T₁, and T₁ subsequently aborts. Since T₂ has already committed, it cannot simply be rolled back to remove the dependency.

Recoverability Versus Cascadelessness

  • Recoverable schedules permit cascading rollback because a dependent transaction may write before its source transaction commits.

  • Cascadeless schedules prevent cascading rollback by requiring the source transaction to commit before the dependent transaction’s subsequent write.

  • Strict two-phase locking provides both conflict serializability and cascadelessness: exclusive locks are held until commit, preventing other transactions from reading uncommitted writes.

  • Basic two-phase locking guarantees conflict serializability but does not necessarily provide strictness or cascadelessness.

Real Database Behavior

PostgreSQL 16 uses MVCC, so ordinary reads observe committed row versions rather than dirty data. MySQL 8.0 InnoDB also uses MVCC, and its consistent snapshot reads avoid dirty reads.

Concurrent updates may block rather than immediately abort. Under SERIALIZABLE isolation, PostgreSQL can abort a transaction with a serialization failure, while InnoDB may block and encounter a deadlock or lock-wait timeout. These systems do not normally implement textbook-style cascading rollback after dirty reads because dirty reads are not exposed.

When application semantics require stronger isolation, use SERIALIZABLE isolation or appropriate explicit locking. Applications should handle serialization failures, deadlocks, and lock timeouts explicitly and retry only when doing so is safe and the transaction is idempotent.

55

What anomalies occur with concurrent database transactions?

Concurrent transactions can cause concurrency-control anomalies when their reads and writes interleave. A transaction may observe uncommitted data, overwrite another transaction’s update, retrieve different values on repeated reads, or calculate an aggregate that corresponds to no valid serial execution.

Read full answer

Applies todatabase transactions in general; PostgreSQL 16 and MySQL 8.4 with InnoDB

Common Concurrency Anomalies

Anomaly Textbook term What happens
Uncommitted-data read Temporary update problem or dirty read A transaction reads a value that another transaction later rolls back. The reader used data that never became valid.
Overwritten update Lost update Two transactions read the same value and write conflicting results. The later write replaces the earlier one without combining both changes.
Inconsistent repeated read Unrepeatable read or inconsistent retrieval A transaction reads the same row twice, but another transaction commits a change between the reads.
Changing row set Phantom read A repeated query using the same predicate returns additional or missing rows because another transaction inserted or deleted matching records.
Invalid aggregate Incorrect summary problem A transaction calculates an aggregate while concurrent changes make the underlying rows represent no single consistent point in time.

These schedules are nonserializable when their outcome cannot be reproduced by executing the transactions one at a time in some serial order.

Worked Lost Update Example

Suppose an account starts with these rows:

account_id owner balance
1 Alice 100
2 Bob 100

Two transactions transfer money from Alice:

Step Transaction T1 Transaction T2
1 Reads Alice’s balance as 100
2 Reads Alice’s balance as 100
3 Adds 50 and writes 150
4 Subtracts 30 and writes 70
5 Commits Commits

The resulting row is:

account_id owner balance
1 Alice 70

However, either valid serial order should produce a balance of 120: 100 + 50 - 30. The final value 70 is therefore incorrect because T1’s update was lost.

A safe application design performs the addition directly in SQL, for example UPDATE account SET balance = balance + 50 ..., rather than reading a balance and later writing a value calculated in application code.

Isolation Levels

Isolation levels define which anomalies the database permits. Higher levels provide stronger consistency but may reduce concurrency or cause more transaction aborts.

Isolation level Main guarantee and limitation
Read Uncommitted May allow dirty reads; rarely appropriate in production systems.
Read Committed Prevents dirty reads. A transaction can still encounter unrepeatable reads and phantoms because each statement may use a newer snapshot.
Repeatable Read Prevents dirty and unrepeatable reads. Its exact phantom and serialization guarantees depend on the database implementation.
Serializable Prevents the listed anomalies by ensuring serializable execution. Conflicting transactions may be aborted and must be retried.

The Serializable level is the strongest normal isolation level. It is not identical to strict serializability, which additionally preserves real-time ordering between transactions.

PostgreSQL and MySQL Differences

  • PostgreSQL 16 uses MVCC and snapshot-based reads. Read Committed is the default; each statement normally receives a fresh snapshot. Repeatable Read uses a transaction-level snapshot and prevents phantoms, but it does not guarantee serializability and does not raise serialization errors. Serializable uses Serializable Snapshot Isolation and aborts transactions whose dependency cycles prevent a serial order.

  • MySQL 8.4 InnoDB defaults to Repeatable Read. Plain consistent reads normally use a transaction snapshot, so they are repeatable. Locking reads can instead observe the latest committed version, and InnoDB’s locking behavior differs from PostgreSQL’s.

  • Both systems use MVCC to reduce reader–writer blocking, but MVCC alone does not guarantee serializable execution. Write skew and other dependency problems can still require stronger isolation or explicit locking.

Additional Operational Problems

  • Deadlock: Transactions wait for each other in a circular dependency. The DBMS detects the cycle and aborts one transaction, typically called the victim.

  • Lock contention: Long transactions hold locks unnecessarily, increasing waiting time and reducing throughput.

  • Starvation: A repeatedly blocked transaction may never obtain enough resources to complete.

  • Cascading rollback: If one transaction reads another transaction’s uncommitted work, rolling back the first transaction may force additional dependent transactions to roll back.

Best Practices

  • Keep transactions short and commit promptly.

  • Use the lowest isolation level that satisfies the business requirement.

  • Use atomic SQL updates for counters and balances instead of application-level read-modify-write logic.

  • Use SELECT ... FOR UPDATE when a decision must be protected against concurrent changes.

  • Retry serialization failures and deadlocks from the application, using bounded backoff.

  • Add indexes for predicates and joins, but avoid indexes that unnecessarily slow required writes.

  • Treat repeatable-read or snapshot behavior as implementation-specific rather than assuming it is equivalent to serializable isolation.

56

What are dirty, non-repeatable, and phantom reads in DBMS transactions?

Dirty reads, non-repeatable reads, and phantom reads are concurrency anomalies in which one transaction observes inconsistent or uncommitted data because of another transaction’s changes. They represent increasing levels of isolation concerns: dirty reads expose uncommitted state, non-repeatable reads expose changed rows, and phantom reads expose changes to a query’s result set.

Read full answer

Applies toDBMS isolation levels; PostgreSQL 16 and MySQL 8.0 InnoDB

Definitions

Anomaly What the second transaction observes Typical cause
Dirty read Data written by a transaction that has not committed and may still roll back Insufficient isolation or an explicit READ UNCOMMITTED level
Non-repeatable read Different values after reading and updating the same existing row The row was updated or deleted by another transaction between two reads
Phantom read A different set of rows when executing the same predicate twice Rows matching the predicate were inserted or deleted between two queries

The main distinction is:

  • A non-repeatable read concerns an existing row whose value changes.

  • A phantom read concerns membership in a result set changing.

  • If an update causes a row to enter or leave a predicate’s result, it can have a phantom-like effect, but the categories are usually distinguished by whether the row identity or result-set membership changed.

Concrete Example

Suppose the initial employee table contains:

id department salary
1 engineering 5000
2 engineering 6000

Dirty read

  1. T1 executes UPDATE employee SET salary = 7000 WHERE id = 1; but does not commit.

  2. T2 executes SELECT salary FROM employee WHERE id = 1; and observes 7000.

  3. T1 rolls back. The observed 7000 never became committed data.

Non-repeatable read

  1. T2 reads salary for employee 1 and obtains 5000.

  2. T1 updates the salary to 7000 and commits.

  3. T2 reads the same row again and obtains 7000.

The row is the same, but its committed value changed.

Phantom read

  1. T2 executes SELECT COUNT(*) FROM employee WHERE department = 'engineering'; and obtains 2.

  2. T1 inserts another engineering employee and commits.

  3. T2 repeats the same query and obtains 3.

No previously visible row changed; instead, a new row appeared in the predicate’s result set.

Standard Isolation Levels

Isolation level Dirty reads Non-repeatable reads Phantom reads
READ UNCOMMITTED Possible Possible Possible
READ COMMITTED Prevented Possible Possible
REPEATABLE READ Prevented Prevented Possible in the standard model
SERIALIZABLE Prevented Prevented Prevented

Higher isolation levels provide stronger consistency, but usually increase locking, reduce concurrency, or require failed transactions to be retried.

PostgreSQL and InnoDB Behavior

  • PostgreSQL 16

  • READ COMMITTED prevents dirty reads but permits non-repeatable and phantom reads.

  • REPEATABLE READ prevents dirty and non-repeatable reads; PostgreSQL’s documented isolation-level table still identifies phantoms as possible.

  • SERIALIZABLE uses Serializable Snapshot Isolation, or SSI. It prevents anomalous results by detecting dangerous dependencies and aborting one transaction with a serialization error, commonly requiring a retry.

  • MySQL 8.0 InnoDB

  • READ COMMITTED prevents dirty reads but permits non-repeatable and phantom reads.

  • REPEATABLE READ uses MVCC snapshots for consistent reads and prevents dirty or non-repeatable reads.

  • Locking range reads use next-key locks, combining record locks with gap locks to prevent matching rows from being inserted into the locked range.

  • SERIALIZABLE strengthens reads into locking reads and prevents all three anomalies, generally with greater contention.

How DBMSs Prevent Them

  • Dirty reads: MVCC hides uncommitted row versions, while lock-based systems prevent incompatible reads until the writer commits or rolls back.

  • Non-repeatable reads: MVCC snapshots or row locks preserve the appropriate committed row version for the transaction’s duration.

  • Phantom reads: Predicate or range locks detect inserts and deletes matching a query, while SSI tracks conflicts between transactions that could produce an anomalous result.

For interviews, remember the progression: uncommitted data → changed existing row → changed result set.

57

What are the SQL isolation levels and the anomalies each prevents?

SQL isolation levels define the degree to which transactions must be isolated from each other to prevent anomalies such as dirty reads, non‑repeatable reads, and phantom reads. The SQL standard specifies four levels—READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, and SERIALIZABLE—each offering a different trade‑off between concurrency and consistency.

Read full answer

Applies toSQL standard (ISO/IEC 9075), PostgreSQL 16, MySQL 8.0 (InnoDB)

Isolation Levels and Anomalies

Isolation Level Dirty Read Non‑Repeatable Read Phantom Read
READ UNCOMMITTED Possible Possible Possible
READ COMMITTED Prevented Possible Possible
REPEATABLE READ Prevented Prevented Possible*
SERIALIZABLE Prevented Prevented Prevented

* In the SQL standard, REPEATABLE READ still allows phantom reads. However, PostgreSQL and MySQL/InnoDB actually prevent phantom reads at this level (see below).

How Each Level Works

  • READ UNCOMMITTED: Transactions can read uncommitted changes from other transactions. No locks are taken for reads, so all three anomalies can occur. It provides the highest concurrency but the weakest consistency.

  • READ COMMITTED: A transaction only sees committed data. Each read statement takes a fresh snapshot, so a repeated read within the same transaction may return different rows if another transaction commits in between. This prevents dirty reads but not non‑repeatable or phantom reads.

  • REPEATABLE READ: Guarantees that repeated reads within a transaction return the same data. In PostgreSQL this is achieved by using a single snapshot for the whole transaction, which also prevents phantom reads. In MySQL/InnoDB, next‑key locking (a combination of row and gap locks) is used to prevent both non‑repeatable and phantom reads, though the standard only requires prevention of non‑repeatable reads.

  • SERIALIZABLE: The strongest level; transactions are executed as if they were serialized. In PostgreSQL this uses predicate locking (SIREAD locks) to detect and abort transactions that would violate serial order. In MySQL/InnoDB it uses a similar locking strategy, often reducing concurrency significantly.

Implementation Differences

  • PostgreSQL: Default isolation is READ COMMITTED. REPEATABLE READ already eliminates phantom reads because PostgreSQL uses snapshot isolation. SERIALIZABLE uses serializable snapshot isolation (SSI) which is both efficient and correct.

  • MySQL/InnoDB: Default isolation is REPEATABLE READ. It uses next‑key locking to prevent phantom reads at this level, going beyond the standard. READ COMMITTED uses a statement‑level read view, while SERIALIZABLE uses strict two‑phase locking.

Choosing an Isolation Level

  • Use READ COMMITTED for most online applications; it avoids dirty reads while allowing good concurrency.

  • Use REPEATABLE READ when you need stable reads within a transaction (e.g., reporting) and can tolerate slightly lower concurrency.

  • Use SERIALIZABLE only when you have complex read‑write transactions that must guarantee serializable behavior (e.g., financial transfers). Be prepared for more lock contention and rollbacks.

  • Avoid READ UNCOMMITTED in any application that requires consistency; it is rarely justified.

58

What are two-phase locking and strict two-phase locking in DBMS?

Two-phase locking (2PL) is a concurrency-control protocol in which a transaction acquires locks during a growing phase and releases them during a shrinking phase. Strict two-phase locking (strict 2PL) additionally holds every exclusive (X) lock until the transaction commits or aborts, preventing cascading rollbacks.

Read full answer

Applies torelational DBMS concurrency control (textbook 2PL; PostgreSQL 16 and MySQL 8.0 InnoDB as reference systems)

Core Locking Rules

A transaction using 2PL follows two phases:

  1. Growing phase: The transaction may acquire shared (S) or exclusive (X) locks but cannot release any lock.

  2. Shrinking phase: The transaction may release locks but cannot acquire another lock.

The transition happens at its first unlock operation. A transaction does not need to acquire all locks simultaneously; it can acquire them as operations require.

Lock conflict Compatible?
S and S Yes
S and X No
X and X No

Every schedule generated by 2PL is conflict serializable. For each pair of conflicting operations, the locks impose a consistent order, and the two-phase rule prevents a cycle in the schedule’s conflict graph.

2PL Versus Strict 2PL

Property Two-phase locking Strict two-phase locking
Lock acquisition Growing phase only Growing phase only
Lock release Shrinking phase Shrinking phase
Exclusive-lock lifetime May be released before commit Held until commit or abort
Conflict serializability Guaranteed Guaranteed
Cascading rollback prevention Not guaranteed Guaranteed
Recoverable schedules Not necessarily guaranteed Guaranteed

Strict 2PL does not require all shared locks to remain until commit. This distinguishes it from rigorous 2PL, which holds every lock, including shared locks, until the transaction ends.

Worked Example

Suppose two accounts initially contain:

Account Initial balance
A 100
B 100

Both transactions transfer 10 units:

  • T1: r(A), w(A), w(B)

  • T2: r(B), w(B), w(A)

If T1 executes first, it acquires S(A), upgrades it to X(A), and acquires X(B). When T2 requests S(B), it must wait because T1 holds X(B).

Under non-strict 2PL, T1 could release X(A) or X(B) during its shrinking phase before committing. Under strict 2PL, those exclusive locks remain held until T1 commits or aborts. Therefore, T2 cannot read a value written by T1 while that value is still uncommitted.

After the transactions execute in the serialized order T1 → T2, the balances are:

Account Final balance
A 100
B 100

Guarantees and Trade-offs

  • Conflict serializability: The two-phase rule makes the conflict graph acyclic, so the schedule is equivalent to a serial execution.

  • No cascading rollback: Strict 2PL prevents another transaction from reading or depending on an uncommitted value protected by an exclusive lock.

  • Recoverability: Strict 2PL schedules are recoverable.

  • Deadlocks remain possible: Lock upgrades and transactions acquiring locks in different orders can still deadlock. Systems may prevent deadlocks, detect them and abort a victim, or use a lock-wait timeout.

  • Lock contention: Long transactions retain locks longer, potentially reducing concurrency and throughput.

Real Database Systems

PostgreSQL 16 and MySQL 8.0 InnoDB do not implement a textbook global 2PL scheduler:

  • PostgreSQL 16 uses multiversion concurrency control (MVCC), so ordinary SELECT statements generally do not acquire shared row locks. SELECT ... FOR SHARE and SELECT ... FOR UPDATE provide explicit locking reads. Its SERIALIZABLE isolation level uses serializable snapshot isolation and detects dangerous structures rather than enforcing classical 2PL.

  • MySQL 8.0 InnoDB also uses MVCC for consistent reads. Updates and locking reads such as SELECT ... FOR UPDATE use row and index-record locks, including gap or next-key locks depending on the isolation level and query. These mechanisms resemble strict 2PL in selected workloads but are not a complete implementation of it.

Interview Best Practices

  • Distinguish 2PL from strict 2PL by emphasizing when exclusive locks are released.

  • State that 2PL guarantees conflict serializability, while strict 2PL additionally prevents cascading rollback.

  • Mention that production systems often use MVCC, explicit locking reads, or serializable snapshot isolation instead of classical 2PL.

  • For transfer or similar invariant-based workloads, consider SERIALIZABLE, explicit row locking, deadlock handling, and retry logic.

59

What are shared and exclusive locks in DBMS?

A shared lock allows multiple transactions to read the same database item concurrently, while an exclusive lock prevents other transactions from reading or modifying that item until the lock is released. These locks are managed by the DBMS to maintain isolation and consistency during concurrent transactions.

Read full answer

Applies toDBMS concepts, PostgreSQL 16, and MySQL 8.0 InnoDB

Shared and Exclusive Locks

Lock type Other transactions may read? Other transactions may write? Lock holder may
Shared lock (S) Yes No Read only
Exclusive lock (X) No No Read and write

In the textbook two-phase locking model, a transaction requests a shared lock when it needs only to read a protected item. If no conflicting exclusive lock exists, multiple transactions can hold shared locks simultaneously.

An exclusive lock is required when a transaction will modify an item. While it is held, no other transaction can obtain either a shared or exclusive lock on that item.

Lock Compatibility

The lock manager maintains the following compatibility rules:

Existing lock Requested shared lock Requested exclusive lock
Shared (S) Compatible Incompatible
Exclusive (X) Incompatible Incompatible

For example, two transactions can read the same row while holding only shared locks. However, one transaction cannot update that row while another holds a shared lock.

Locks are normally retained until the transaction commits or rolls back, although some row locks can be released earlier depending on the isolation level and the DBMS’s locking rules. Retaining locks until transaction completion prevents a transaction from modifying an object after another transaction has inspected it but before the first transaction completes.

How They Work

  1. A transaction requests a lock before accessing a protected database item.

  2. The lock manager checks the item’s current lock state.

  3. A compatible request succeeds immediately.

  4. An incompatible request waits in the lock queue.

  5. The waiting transaction continues when the conflicting lock is released.

  6. If waiting creates a circular dependency, the DBMS may detect and abort a transaction because of a deadlock.

Locking is commonly implemented at several granularities:

  • Database level: affects the entire database.

  • Table level: affects all rows in a table.

  • Page or block level: affects a stored page containing multiple rows.

  • Row level: affects an individual row and provides finer concurrency.

Finer-grained locks improve concurrency but require more lock-management overhead. Not every DBMS implements every granularity: PostgreSQL 16 and MySQL 8.0 InnoDB support row-level locking but do not expose ordinary user-level page locks.

Real-System Behavior

The textbook compatibility model still describes how explicit shared and exclusive locks interact, but real systems extend it with MVCC and additional lock modes.

  • PostgreSQL 16: Ordinary SELECT statements use the MVCC model and do not block normal writers by taking row-level shared locks. They still acquire an ACCESS SHARE table-level lock. Row-level locks are primarily exclusive; SELECT ... FOR UPDATE obtains an exclusive row lock, while SELECT ... FOR SHARE obtains a shared row-level lock.

  • MySQL 8.0 InnoDB: InnoDB uses MVCC for consistent nonlocking reads, but locking reads such as SELECT ... FOR SHARE and SELECT ... FOR UPDATE explicitly acquire shared or exclusive record locks. Under REPEATABLE READ, InnoDB can also use gap and next-key locks to protect index ranges.

Thus, a shared row lock should not be assumed for every ordinary read in PostgreSQL or MySQL.

Common Pitfalls and Trade-offs

  • Deadlocks: A transaction holding a shared lock may request an exclusive lock later. Two transactions performing conflicting lock upgrades can wait on each other and cause a deadlock.

  • Long transactions: Holding locks until commit can reduce concurrency and increase contention.

  • Unnecessary explicit locks: In PostgreSQL, an explicit shared table lock is rarely needed for ordinary reads because MVCC already provides snapshot-based isolation.

  • Granularity trade-off: Row-level locking improves concurrency, whereas table-level locking is simpler and may use less metadata but blocks more operations.

  • Isolation-level differences: The exact effects of a lock depend on the transaction isolation level. Under READ COMMITTED, PostgreSQL and InnoDB may release nonmatching row locks earlier than under REPEATABLE READ.

60

How do database deadlocks occur, and how are they resolved?

A database deadlock occurs when two or more transactions each hold a resource that another transaction needs, creating a circular wait. In a detection-based system, the DBMS aborts one transaction, rolls back its changes, releases its locks, and allows the remaining transactions to continue.

Read full answer

Applies toDBMS concurrency control; PostgreSQL 16 and MySQL 8.0 with InnoDB

How Deadlocks Occur

A deadlock requires a cycle of blocked transactions. For example:

  1. Transaction A updates row 1 and locks it.

  2. Transaction B updates row 2 and locks it.

  3. Transaction A tries to update row 2, so it waits for B.

  4. Transaction B tries to update row 1, so it waits for A.

Neither transaction can proceed, creating the cycle A → B → A.

In the textbook wait-for graph:

  • Nodes represent transactions.

  • Edges represent transactions waiting for locks held by other transactions.

  • A cycle indicates a deadlock.

Deadlocks can result from row updates, inconsistent insertion orders, foreign-key checks, unique-index operations, or DDL lock conflicts. Although two-phase locking controls when locks can be released, it does not by itself prevent circular waits.

Detection and Recovery

The DBMS selects a victim transaction when it detects a cycle:

  1. The victim receives a deadlock error.

  2. Its changes are rolled back.

  3. Its locks are released.

  4. Other transactions may continue.

  5. The application may retry the aborted transaction.

Which transaction becomes the victim is implementation-dependent and can vary between executions.

System Detection behavior Reported error
PostgreSQL 16 Checks for a wait-for cycle after deadlock_timeout; its default is 1 second SQLSTATE 40P01, deadlock detected
MySQL 8.0 InnoDB Detects cycles among InnoDB lock waits and rolls back a victim transaction Error 1213, Deadlock found when trying to get lock; try restarting transaction

A deadlock differs from an ordinary lock wait: an ordinary wait has no cycle and may eventually succeed, while a deadlock cannot progress without intervention.

Worked Example

Suppose two PostgreSQL sessions each transfer 100 units between accounts whose initial balances are 1,000. Session A first updates account 1, and Session B first updates account 2. Each session then tries to update the account already locked by the other session, creating a deadlock.

PostgreSQL aborts one session with SQLSTATE 40P01. If Session A is selected as the victim, its update is rolled back and Session B commits the transfer:

account_id balance
1 1100.00
2 900.00

If Session B is selected as the victim, the balances are reversed.

Prevention Strategies

The most reliable application-level prevention method is a consistent lock order:

  • Always update or lock accounts in ascending account_id order.

  • Use the same ordering in every transaction and execution path.

  • Avoid acquiring user-defined, index, and row locks in unrelated orders.

Other strategies include:

  • Short transactions: Commit promptly to reduce lock overlap.

  • Smaller lock scope: Avoid modifying more rows than necessary.

  • Queue-based processing: Serialize work when strict sequential processing is sufficient.

  • Optimistic concurrency: Use version checks and retry instead of holding locks throughout business logic.

  • Timeout controls: PostgreSQL’s lock_timeout and MySQL’s innodb_lock_wait_timeout bound long waits, although timeouts do not prevent deadlocks from forming.

PostgreSQL and InnoDB Differences

Both systems use MVCC, so ordinary consistent reads often do not block writes as traditional locking systems might. Updates and DDL operations can still conflict.

  • PostgreSQL detects cycles through its lock manager, including heavyweight and row-level lock waits. It performs deadlock checking when a wait reaches deadlock_timeout rather than permanently maintaining a complete wait-for graph.

  • InnoDB uses record locks on index rows, gap locks, and next-key locks. Under REPEATABLE READ, gap locks can create additional deadlocks involving ranges and indexes.

  • PostgreSQL’s FOR UPDATE NOWAIT and FOR UPDATE SKIP LOCKED, along with MySQL 8.0’s corresponding locking-read options, can avoid waiting. Skipped work must be tracked and handled explicitly by the application.

Best Practices and Trade-offs

  • Retry the entire transaction, not only the failed statement, because PostgreSQL and InnoDB abort the transaction after a deadlock.

  • Use bounded retries with exponential backoff and jitter to prevent synchronized retry storms.

  • Make retried operations idempotent, especially for payments or other external side effects.

  • Keep external side effects outside the retried database transaction when possible, or coordinate them through an idempotent outbox process.

  • Preserve a consistent resource ordering even when automatic deadlock detection is enabled.

  • Treat deadlock errors as recoverable concurrency-control outcomes rather than unrecoverable failures.

61

What is timestamp-based concurrency control in DBMS?

Timestamp-based concurrency control, also called timestamp ordering, detects conflicting transactions by comparing each transaction’s timestamp with timestamps maintained for the database items it accesses. It provides conflict-serializable execution by aborting transactions whose operations would violate timestamp order.

Read full answer

Applies totextbook DBMS concurrency control; PostgreSQL 16 and MySQL 8.0 (InnoDB) for implementation comparisons

Core Idea

Every transaction receives a logical timestamp TS(Ti) when it starts. A larger timestamp represents a logically newer transaction.

For each data item x, the DBMS maintains:

  • RTS(x): the largest timestamp of a transaction that has read x.

  • WTS(x): the timestamp of the transaction that most recently wrote x.

Before an operation is permitted, the DBMS checks whether it conflicts with a newer transaction. If it does, the current transaction is aborted and rolled back. The application may then retry it with a new timestamp.

Timestamp ordering is a concurrency-control technique in its own right. It differs from serialization testing, which determines whether a transaction’s read and write sets can be serialized with other committed transactions.

Timestamp Validation Rules

For transaction Ti and data item x:

Operation Condition Action
Read x TS(Ti) < WTS(x) Abort Ti because a newer transaction has written x
Read x TS(Ti) >= WTS(x) Allow the read and set RTS(x) = max(RTS(x), TS(Ti))
Write x TS(Ti) < RTS(x) or TS(Ti) < WTS(x) Abort Ti because a newer transaction has read or written x
Write x Otherwise Allow the write and set RTS(x) = WTS(x) = TS(Ti)

The write condition uses OR, not AND. A conflict with either a newer read or a newer write makes the write unsafe.

These are the basic timestamp-ordering rules. Stronger variants impose additional restrictions to obtain stronger serializability and recoverability properties.

Worked Example

Consider an accounts table:

account_id balance
1 100

Two transactions occur:

  1. T2, with timestamp 20, writes balance = 200. The item now has WTS(x) = 20 and RTS(x) = 20.

  2. T1, with timestamp 10, attempts to read the row. Since TS(T1) = 10 < WTS(x) = 20, the read is rejected.

  3. T1 is aborted and rolled back. If the application retries it, the new transaction receives a newer timestamp, such as 30.

  4. After T2 commits, the retried transaction reads the updated value.

The resulting row is:

account_id balance
1 200

This prevents an older transaction from reading a value written by a newer transaction in a way that violates timestamp order.

Advantages and Limitations

Advantages Limitations
Does not require lock managers or lock waits for basic conflict detection Conflicting transactions may require repeated aborts
Avoids deadlocks caused by cyclic lock waits Older transactions can be repeatedly aborted, causing starvation
Provides conflict-serializable execution in the textbook model Cascading rollback may undo substantial work
Makes transaction ordering explicit through timestamps Timestamp and per-item metadata add storage and processing overhead

A rejected transaction must have all its effects rolled back. To preserve transaction-level semantics, the application normally retries the transaction from its beginning rather than retrying only the failed statement.

Comparison with Locking and MVCC

  • Two-phase locking: Transactions acquire and then release locks. Ordinary two-phase locking guarantees conflict serializability; strict two-phase locking additionally provides strict serializability.

  • Timestamp ordering: Detects conflicts using timestamps and aborts an unsafe transaction rather than waiting for a lock.

  • MVCC: Preserves row-version information so readers generally do not block writers. PostgreSQL and InnoDB primarily use MVCC rather than textbook timestamp ordering.

PostgreSQL 16 implements serializable transactions using Serializable Snapshot Isolation, which performs serialization checks involving predicate-style read dependencies. MySQL 8.0 InnoDB uses MVCC for consistent nonlocking reads and locking operations for stricter isolation. Neither is a direct implementation of textbook basic timestamp ordering.

Practical Guidance

  • Prefer MVCC when nonblocking readers and concurrent writes are important.

  • Use serializable isolation when conflict-serializable behavior is required and the application can safely retry serialization failures.

  • Use a mechanism that explicitly guarantees strict serializability when real-time commit order must also be respected; serializable isolation alone does not necessarily provide that guarantee.

  • Implement retries with bounded backoff and jitter to reduce repeated contention.

  • Distinguish conflict serializability from strict serializability: basic timestamp ordering does not require transactions to commit in timestamp order.

62

How does PostgreSQL implement MVCC for concurrent transactions?

Multiversion concurrency control (MVCC) lets PostgreSQL maintain multiple physical versions of updated rows so transactions can read a consistent snapshot while other transactions are modifying the same data. PostgreSQL combines row versioning, transaction IDs, snapshots, and transaction metadata to provide nonblocking ordinary reads and configurable isolation levels.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.4 InnoDB

How MVCC Works

For an UPDATE, PostgreSQL normally leaves the old tuple in the table heap and creates a new tuple containing the modified values. For a DELETE, it marks the existing tuple as deleted through its transaction metadata rather than creating a replacement tuple.

  • Old version: Remains available while an existing snapshot may need it.

  • New version: Becomes visible after its inserting transaction commits and a later snapshot includes that transaction.

  • Readers: Evaluate tuple metadata against a snapshot and select the version visible to the transaction.

  • Concurrent writers: Updating the same row can still cause one writer to wait; under stronger isolation, PostgreSQL may instead raise a serialization failure.

Ordinary MVCC reads do not lock the rows they inspect, so a reader generally does not block a writer. MVCC does not eliminate write-write contention.

Tuple Visibility and Storage

Each heap tuple contains transaction metadata including:

  • xmin: The transaction ID that inserted the tuple version.

  • xmax: The transaction ID or multitransaction ID associated with deletion or supersession.

  • cmin and cmax: Command IDs used to order insert and delete operations performed by the same transaction.

A snapshot records which transactions were active, in-progress, or completed when it was acquired. Simplified visibility follows these rules:

  • A transaction sees its own inserted and deleted rows according to its command ID.

  • A tuple inserted by a transaction that was active at snapshot acquisition is initially invisible, even if that transaction commits later.

  • A tuple deleted by a transaction that committed before snapshot acquisition is invisible.

  • If a deleting or updating transaction aborted, its effect is ignored.

Old tuples remain in the heap until no snapshot can require them and cleanup removes them. HOT updates place the new tuple on the same page when space permits and no indexed column changed, avoiding new index entries.

Snapshots and Isolation Levels

PostgreSQL obtains snapshots according to the transaction’s isolation level:

Isolation level Snapshot behavior Important consequence
READ COMMITTED A new snapshot for each statement A later statement can see rows committed since an earlier statement
REPEATABLE READ One snapshot for the transaction Repeated reads use the same snapshot, although serialization anomalies remain possible
SERIALIZABLE One snapshot plus serialization checks Dangerous dependencies can cause a transaction to be aborted

READ COMMITTED is PostgreSQL’s default. SERIALIZABLE uses Serializable Snapshot Isolation, tracking predicate dependencies with SIREAD locks and raising serialization failures when required to preserve serializability.

PostgreSQL Compared with InnoDB

Aspect PostgreSQL MySQL InnoDB
Historical row versions Stored primarily in the table heap Reconstructed from undo logs
Read consistency Snapshot-based visibility Read views and undo-log versions
Cleanup VACUUM and AUTOVACUUM remove obsolete tuples Purge processes remove obsolete undo records
Write conflicts Row locks and, when enabled, serialization checks Row locks and deadlock detection
Space implications Long transactions retain old tuples Long transactions retain undo history

Both systems reduce reader-writer interference, but PostgreSQL stores row versions directly while InnoDB reconstructs them from undo records.

Concrete Example

Suppose an account has a balance of 1000. Session A updates it to 900 but has not committed. Session B reads 1000 because its statement snapshot cannot see A’s uncommitted tuple. After A commits, B’s next statement sees 900 because READ COMMITTED acquires a fresh snapshot for every statement.

Best Practices and Limitations

  • Keep transactions short so obsolete versions can be removed promptly.

  • Monitor dead tuples, table bloat, vacuum activity, and transaction-ID age.

  • Avoid unnecessary FOR UPDATE; ordinary MVCC reads already provide a consistent snapshot.

  • Retry serialization failures when using SERIALIZABLE.

  • Do not assume MVCC eliminates all locking: two transactions updating the same row can still wait for each other.

  • Keep AUTOVACUUM enabled and correctly configured so transaction-ID age does not approach wraparound limits.

  • Use manual VACUUM for specific operational needs. It normally makes dead-tuple space reusable within the relation; VACUUM FULL rewrites the table and returns space to the operating system, but requires stronger locking.

63

How does optimistic concurrency control handle concurrent transactions?

Optimistic concurrency control (OCC) is a concurrency-control strategy that allows transactions to proceed concurrently and checks for conflicting changes before committing. Instead of locking data in advance, it assumes conflicts are uncommon and aborts or retries a transaction when validation fails.

Read full answer

Applies toDBMS transaction processing; PostgreSQL 16 and MySQL 8.4 InnoDB comparisons

Core Idea

OCC follows three phases:

  1. Read phase: The transaction reads data and records the versions or timestamps of the items it accessed.

  2. Validation phase: Before commit, the DBMS checks whether another transaction has modified any relevant item since it was read.

  3. Write phase: If validation succeeds, the changes are committed. If it fails, the transaction is rolled back and may be retried.

A version number can represent the state of a row. For example, an accounts table might contain:

account_id balance version
1 100 1

Two transactions read the same row. T1 updates it to balance = 90 and increments version to 2. If T2 attempts an update conditional on version = 1, it affects zero rows because its expected version is stale. T2 must abort or reload the row and try again.

Conflict Detection

Validation can detect several conflicts:

  • Write-write conflict: Two transactions modify the same item.

  • Read-write conflict: One transaction reads an item that another transaction later changes.

  • New-version conflict: The version observed during the read phase differs from the current version.

  • Serialization conflict: The concurrent operations cannot be arranged into a valid serial order.

The exact validation rules depend on the OCC algorithm. Timestamp ordering, version ordering, and serialization-graph methods are common textbook approaches.

Comparison with Pessimistic Concurrency Control

Aspect Optimistic control Pessimistic control
Initial assumption Conflicts are rare Conflicts are likely
Read operation Usually does not lock rows May acquire shared or exclusive locks
Conflicting write Transaction is aborted or rejected Transaction waits for the lock
Contention handling Abort and retry Lock waiting or deadlock detection
Best suited for Mostly read-heavy, low-contention workloads Frequently updated, contended data
Main cost Wasted work when validation fails Lock overhead and reduced concurrency

Pessimistic control is common in banking and inventory systems where strict ordering is important. OCC is useful when most transactions do not touch the same records.

PostgreSQL and MySQL InnoDB

Real database systems often use multi-version concurrency control (MVCC) rather than textbook OCC:

  • PostgreSQL 16 uses MVCC snapshots. Under READ COMMITTED, each statement receives a new snapshot; under REPEATABLE READ and SERIALIZABLE, the transaction uses one transaction-level snapshot. In REPEATABLE READ, an update to a row that the transaction already read can raise a serialization failure with SQLSTATE 40001; this isolation level uses snapshot isolation and does not guarantee a serializable schedule. SERIALIZABLE uses Serializable Snapshot Isolation to detect dangerous patterns of read/write dependencies and can also raise 40001. The application should roll back and retry the whole transaction.

  • MySQL 8.4 InnoDB uses MVCC for consistent reads and locking or current reads for operations such as SELECT ... FOR UPDATE and some updates. Applications commonly implement explicit OCC with a version column and a conditional UPDATE, checking whether the affected-row count is zero.

These systems therefore combine MVCC, row locks, snapshot validation, and conflict detection rather than implementing only the simplified textbook OCC algorithm.

Trade-offs and Best Practices

  • Keep transactions short because a transaction that reads old versions is more likely to fail validation.

  • Retry transactions that fail because of serialization failures, deadlocks, or explicit OCC validation conflicts; do not retry unrelated constraint, programming, or business-rule errors.

  • Make retries idempotent; repeated execution must not duplicate payments or other side effects.

  • Use explicit version columns when application-level OCC and clear stale-write detection are required.

  • Choose pessimistic locking when strict ordering, low latency, or predictable waiting behavior matters more than avoiding lock overhead.

  • Test under realistic contention: low-conflict workloads may never expose the differences between these strategies.

64

What is write-ahead logging in DBMS?

Write-ahead logging (WAL) is a recovery technique in which a database records transaction changes in a log before the affected data pages are written to persistent storage. This ordering ensures that committed transactions can be replayed after a crash, preserving atomicity and durability.

Read full answer

Applies toDBMS recovery concepts, including PostgreSQL 16 and MySQL 8 InnoDB

Core Idea

A database usually modifies data in memory, such as a buffer pool or buffer pool cache, and writes the resulting pages to disk later. With WAL, the database first writes enough information to a transaction log to reconstruct those modifications.

The required ordering is:

  1. Write the transaction’s log record to stable storage.

  2. Write the modified data page to disk.

If a crash occurs between these steps, recovery reads the log and reapplies the missing change. The write-ahead rule prevents a committed transaction from being lost merely because its modified page had not yet reached disk.

A Simple Example

Suppose an account table initially contains:

account_id balance
1 100

A transaction updates the balance to 90 with the statement UPDATE accounts SET balance = 90 WHERE account_id = 1;.

The database may initially leave the table page dirty in memory. Before acknowledging the commit, it makes the corresponding WAL information durable. If the system crashes before the table page is written, recovery uses the log to reproduce the update, leaving the committed state as:

account_id balance
1 90

If the transaction had not committed, recovery must discard its changes rather than apply them.

How Commit and Recovery Work

  • Commit: Before reporting success, the DBMS ensures that the transaction’s commit-related log records are on stable storage according to its durability policy.

  • Redo: During crash recovery, records representing committed changes are replayed when the corresponding data pages are missing or outdated.

  • Undo: Some systems also log information needed to reverse uncommitted changes. The mechanism differs by DBMS.

  • Checkpointing: The DBMS periodically records a known recovery position so recovery does not need to inspect the entire log.

The exact log format may be physical, logical, or physiological. Physical logging records page-level changes, logical logging records operations, and physiological logging combines aspects of both.

PostgreSQL and MySQL InnoDB

System WAL implementation Recovery characteristics
PostgreSQL 16 Uses a shared WAL with records identified by a log sequence number (LSN) Replays WAL from the last valid checkpoint; full-page images can restore pages after torn or incomplete writes
MySQL 8 InnoDB Uses a redo log for crash recovery and separate undo information for transaction rollback Redo replays committed changes, while undo information supports rollback and MVCC
MySQL binary log Records server-level changes for replication and recovery It is separate from InnoDB’s redo log and should not be confused with InnoDB WAL

In PostgreSQL, page changes include the page’s LSN, allowing recovery to determine whether a page is current. InnoDB similarly uses log sequence identifiers to track redo-log position.

Advantages and Limitations

  • Advantages:

  • Enables crash recovery without writing every data page during every commit.

  • Supports high throughput by allowing many modified pages to remain in memory.

  • Provides the foundation for durability and often supports replication or point-in-time recovery.

  • Reduces the amount of data that must be flushed synchronously during a transaction.

  • Limitations:

  • WAL creates additional I/O because changes are recorded before pages are written.

  • The log can grow rapidly under heavy write workloads.

  • Log storage, checkpointing, backups, and replication all require careful capacity planning.

  • Incorrect durability settings can make acknowledged commits disappear after an operating-system or power failure.

A common mistake is to assume that committing writes the changed row directly to its table file. Usually, it makes the relevant log information durable; the table page may be flushed later. Durability also depends on configuration—for example, PostgreSQL’s synchronous_commit and MySQL’s innodb_flush_log_at_trx_commit determine when and how transaction logs are synchronized with persistent storage.

65

How does a DBMS restore a consistent database after a crash?

A DBMS performs crash recovery using durable transaction and change logs to restore the database to a state consistent with its durable commit records. It ensures committed changes survive the failure and makes the effects of incomplete transactions invisible or rolls them back.

Read full answer

Applies toDBMS recovery concepts (ARIES model), PostgreSQL 16, and MySQL 8.0 InnoDB

Core Recovery Mechanism

Most modern DBMSs use write-ahead logging (WAL): before a modified database page is written to disk, the corresponding log record must first be made durable. This ordering lets recovery reconstruct page contents when only some changes reached the data files.

Recovery distinguishes transactions by their durable log status:

Transaction state before crash Recovery action Result
Commit record was durable Preserve the transaction’s effects, redoing missing page changes if necessary Committed changes survive
No commit record was durable Treat the transaction as a loser and undo or logically abort it Incomplete changes are not visible
Some pages were already written Compare each page’s LSN with the WAL or redo position Changes already present are not reapplied

A transaction with a durable commit record is commonly called a winner; one without one is a loser. Redo must be idempotent so that repeating a log record cannot corrupt the page.

Typical Recovery Procedure

  1. Detect the failure: The DBMS or operating system detects that the database process stopped unexpectedly.

  2. Open the durable log: The DBMS reads the surviving WAL or redo records.

  3. Find the recovery starting point: It locates a checkpoint identifying the redo position and recovery metadata.

  4. Redo missing changes: Log records are replayed when the target page does not already contain them. Depending on the system, physical replay may also include changes belonging to transactions that ultimately did not commit.

  5. Handle losers: ARIES-style recovery uses logical undo and compensation log records. InnoDB uses undo logs to roll back incomplete transactions. PostgreSQL leaves old row versions visible through MVCC; changes from transactions without commit records are not visible, and later VACUUM can reclaim their space.

  6. Complete recovery: The DBMS establishes a consistent state and opens the database for users.

A checkpoint is an anchor for recovery rather than a complete copy of the database. Depending on the system, its metadata can identify the redo position, dirty-page information, and active transaction state.

Example: Interrupted Bank Transfer

Suppose a transaction transfers ₹500 from account A to account B:

Account Before transaction After successful commit
A 1000 500
B 2000 2500

If the DBMS crashes after modifying A but before durably committing, the transaction is a loser. Recovery logically restores both balances to their original values. InnoDB performs this rollback using undo information; PostgreSQL preserves the old row version as the MVCC-visible value.

If the commit record is durable, the transfer remains committed. Even if neither modified page reached the data files, redo applies the logged changes and produces the final values in the table.

PostgreSQL 16 and MySQL InnoDB

System Recovery mechanism
PostgreSQL 16 Uses WAL and checkpoints. Startup recovery replays WAL from the checkpoint’s redo location to a consistent state. It uses MVCC rather than persistent undo logs; aborted or incomplete transactions remain logically invisible, and VACUUM later reclaims space.
MySQL 8.0 InnoDB Uses a physical redo log to restore page changes and undo logs to roll back transactions that lacked a durable commit. Recovery runs automatically during startup.

Although both systems provide transaction rollback behavior, they implement it differently: PostgreSQL primarily uses row versions and MVCC, whereas InnoDB records compensating changes in undo logs.

Failure Scope and Trade-offs

  • DBMS or operating-system process crash: Assuming durable storage remains intact, WAL or redo recovery restores a consistent state consistent with the durable commit records.

  • Media failure: The damaged storage must be replaced. Recovery generally requires a backup plus archived logs; PostgreSQL commonly uses point-in-time recovery (PITR) with a base backup and continuous WAL archiving, while MySQL can combine backups with binary logs.

  • Durability settings matter: Acknowledging commits before their log records are durable improves performance but can allow acknowledged transactions to be lost after a power failure.

  • More logging adds overhead: WAL provides crash recovery and supports PITR when logs are continuously archived, but it consumes storage and adds write I/O.

  • More frequent archiving improves recovery granularity: A smaller gap between archived log segments reduces the amount that must be replayed to reach a desired point in time.

  • Checkpoints balance work: Frequent checkpoints can shorten recovery time but increase checkpoint and page-flush I/O; infrequent checkpoints reduce that overhead but leave more work for recovery.

The textbook model assumes durable media and predictable failure boundaries. Real systems must also handle torn writes, corrupted pages, storage-controller caching, operating-system failures, and replication. Checksums where enabled, redundant storage, backups, replication, and backup verification complement—but do not replace—the recovery log.

66

How do checkpoints enable recovery in DBMSs?

A database checkpoint creates a durable recovery anchor by recording checkpoint metadata and coordinating write-ahead logging with dirty-page flushing. After a crash, the DBMS uses that anchor and the transaction log to redo page changes and undo transactions that did not commit.

Read full answer

Applies togeneral DBMS recovery concepts; PostgreSQL 16; MySQL 8.4 InnoDB

Checkpoint Operation

Most modern DBMSs use write-ahead logging (WAL): before a modified database page is written to disk, the log records describing changes through that page image must be made durable.

A checkpoint typically:

  1. Records recovery metadata in the log. Its exact contents depend on the DBMS; an ARIES checkpoint includes the active transaction table and the dirty-page table.

  2. Makes the checkpoint information durable according to the system’s checkpoint protocol.

  3. Flushes dirty pages or coordinates their flushing with background workers.

  4. Establishes a boundary that reduces the log that must be scanned during crash analysis.

A checkpoint does not normally wait for active transactions to finish. Transactions that remain incomplete at the time of a crash are handled through undo recovery.

Crash Recovery Procedure

In an ARIES-style recovery process, the checkpoint supports these steps:

  1. Analysis: Begin at the last complete checkpoint and reconstruct the transaction table and dirty-page table.

  2. Redo: Start at the smallest recLSN in the dirty-page table and repeat logged page updates that may not have reached disk. This position can precede the checkpoint, so recovery may replay some pre-checkpoint updates.

  3. Undo: Roll back transactions that were incomplete at the crash by reversing their effects.

For example, suppose a committed update modified page P before the checkpoint, but P was still dirty when the crash occurred. Its update may still require redo even though its log record predates the checkpoint. If another transaction had modified P without committing, that change may also be redone as part of reconstructing page history and then undone.

Thus, the checkpoint mainly reduces analysis work. Flushing dirty pages can reduce redo work, but it does not guarantee that every update preceding the checkpoint can be skipped.

Checkpoint Strategies

Strategy How It Works Trade-off
Sharp checkpoint All dirty pages are written before the checkpoint completes, pausing work as needed. Creates a simpler recovery boundary but may cause an I/O pause.
Fuzzy checkpoint Dirty pages may be flushed while transactions continue; the checkpoint protocol records the required recovery metadata. Reduces checkpoint pauses but requires more detailed logging and analysis.
Incremental checkpoint A subset of dirty pages is written during each checkpoint interval. Spreads I/O but may require more frequent checkpoints.

Checkpoint frequency involves a trade-off:

  • More frequent checkpoints generally shorten recovery analysis but increase checkpoint I/O.

  • Infrequent checkpoints reduce checkpoint overhead but increase the amount of log and dirty-page work that recovery must examine.

Checkpoint Versus Backup

Mechanism Primary Purpose Relevant Stored Data
Checkpoint Accelerate recovery from an abrupt failure A checkpoint record and database pages already flushed to primary storage
Transaction log Support redo, undo, and durability Log records describing changes to database pages
Backup Recover from media failure, corruption, or accidental deletion A separate copy of database or page data

A checkpoint is not a backup. It normally relies on the same storage as the database and therefore cannot protect against loss of that storage. Media-failure recovery generally requires a suitable backup together with any archived logs required to reach the desired recovery point.

PostgreSQL and MySQL InnoDB

  • PostgreSQL 16 uses WAL and a background checkpointer. A checkpoint records recovery information and causes dirty shared buffers to be flushed while normal activity can continue. During recovery, PostgreSQL uses checkpoint and control-file redo locations to replay WAL. The full_page_writes setting is enabled by default: the first write to a page after a checkpoint includes a full-page image, allowing a torn page to be restored; page checksums help detect corruption.

  • MySQL 8.4 InnoDB uses log sequence numbers in its redo logs. Checkpointing advances the redo position that must be retained while background page flushing writes dirty pages, potentially ahead of the checkpoint. After a crash, InnoDB replays redo from the checkpoint and rolls back transactions that were incomplete.

67

How does the ARIES recovery algorithm work?

ARIES—Algorithm for Recovery and Isolation Excluding Semantics—is a three-pass recovery algorithm that uses write-ahead logging to restore a database to a consistent state after a crash. It identifies unfinished transactions, repeats logged history, and then undoes the effects of transactions that had not committed.

Read full answer

Applies toARIES database recovery model; PostgreSQL 16 and MySQL 8.4 InnoDB as reference systems

Core Principles

ARIES combines write-ahead logging (WAL) with the steal/no-force buffer-management policy:

  • WAL rule: Before a modified database page is written to disk, the log records describing changes reflected in that page must be forced to stable storage.

  • Steal: A dirty page may be written to disk before its transaction commits.

  • No-force: At commit, modified pages do not have to be forced to disk. However, the commit log record must first be forced to stable storage; recovery can then reproduce any page changes that were not flushed.

These rules allow committed transactions to survive a crash while ensuring that uncommitted changes are eventually undone.

The Three Recovery Passes

Pass Purpose Main actions
Analysis Reconstruct recovery state Find committed and active transactions; rebuild the dirty-page table
Redo Restore the state represented by the log Repeat history, including updates and compensation records
Undo Remove effects of failed transactions Roll back transactions that were active at the crash
  1. Analysis pass

  2. Start at the most recent checkpoint (found through the master record) and scan forward to the end of the log.

  3. Use the checkpoint’s saved tables and the subsequent log records to reconstruct the transaction table, containing each transaction’s status and lastLSN.

  4. Reconstruct the dirty-page table, recording which pages might contain changes not yet flushed to disk.

  5. Determine which transactions committed and which are losers.

  6. Redo pass

  7. Redo starts at the smallest recLSN in the dirty-page table.

  8. Repeat history by reapplying logged updates and compensation records, including records belonging to uncommitted transactions.

  9. For each page, compare the log record’s LSN with the page’s pageLSN. If the page already contains that change, the action is skipped.

  10. Undo pass

  11. Process loser transactions backward through their log records.

  12. Reverse each logged update using the information in its update record.

  13. Write compensation log records (CLRs) describing undo actions.

  14. CLRs are redone during recovery but are never themselves undone.

Logging and Checkpoints

ARIES uses physiological logging: an update record identifies the physical page and location and describes the logical operation, including the information needed to undo it, rather than storing a complete disk-page image.

Checkpoints reduce recovery time by providing a recent starting point for analysis. A checkpoint records information such as active transactions and dirty pages. During normal operation, checkpoints and WAL records are written to stable storage as required by the WAL rule.

A transaction ID, page ID, and LSN allow recovery to correlate log records with transactions and pages. The transaction’s lastLSN points to its latest log record, while prevLSN links it to the preceding record for that transaction.

Worked Crash Example

Suppose:

Transaction Operation State at crash
T1 Changes account A from 100 to 70 Active, not committed
T2 Changes account B from 200 to 250 Committed

The corresponding pages were not yet flushed to disk.

  • Analysis identifies T1 as a loser and T2 as committed.

  • Redo repeats both logged updates, restoring A to 70 and B to 250.

  • Undo reverses T1, writing a CLR that restores A to 100.

The recovered result is:

Account Final balance
A 100
B 250

Redo precedes undo because an uncommitted page may already contain an update. Redo first restores the logged history, after which undo removes the effects of loser transactions in the correct order.

Trade-offs and Real-System Differences

  • Benefits: ARIES provides page-level redo and transaction-level undo, supports recovery interrupted by another crash through CLRs, and avoids forcing every dirty page to disk at commit.

  • Costs: Recovery scans log records, maintains transaction and dirty-page metadata, and writes CLRs when rolling back losers.

  • PostgreSQL 16: Uses WAL, full-page writes, MVCC, and optional data-page checksums, but does not implement textbook ARIES exactly. During crash recovery, WAL replay restores physical changes; MVCC determines transaction visibility rather than relying on the classic ARIES undo pass for aborted transactions.

  • MySQL 8.4 InnoDB: Uses redo logs for crash recovery and undo logs for rollback and MVCC. Its design has ARIES-like principles but differs in implementation details and recovery procedures.

68

What are the stages of query processing in a DBMS?

In a relational database management system, query processing is the sequence of steps that transforms a user‑issued SQL statement into an executable plan and then executes it to produce the result set. It typically involves parsing, validation, optimization, and execution, each of which may be further subdivided.

Read full answer

Applies torelational DBMS (PostgreSQL 16, MySQL 8 with InnoDB, and general DBMS concepts)

Parsing and Validation

  • Lexical analysis: The SQL string is broken into tokens (keywords, identifiers, punctuation).

  • Syntax analysis: Tokens are arranged into a parse tree (abstract syntax tree) that reflects the grammatical structure of the query.

  • Semantic validation: The system verifies that the referenced tables and columns exist, data types match, the user has the necessary privileges, and any constraints are not violated. The result is a validated parse tree.

Query Optimization

  • Logical optimization: The parse tree is rewritten into an equivalent but more efficient form. Common transformations include predicate pushdown (moving filters closer to the data source), subquery unnesting, and view merging.

  • Physical optimization: The optimizer decides how to access the data—full table scan, index scan, or index‑only scan—and, for joins, the order of tables and the join algorithm (nested loop, hash join, merge join).

  • Cost‑based planning: Using table statistics (row counts, index selectivity, column distributions), the optimizer estimates the cost of each candidate plan (usually I/O and CPU cost) and selects the cheapest one. The output is an executable plan.

Query Execution

  • The execution engine follows the plan: it fetches pages from the buffer pool or disk, performs the chosen scans, and carries out joins, sorts, and aggregations.

  • Intermediate results are either materialized (written to a temporary area) or pipelined directly to the next operator, depending on the plan.

  • The engine manages memory, locks, and write‑ahead logging to ensure ACID properties.

Result Retrieval

  • The final rows are formatted according to the client protocol (e.g., PostgreSQL wire protocol, MySQL protocol) and streamed back to the client.

  • For large result sets, rows are often fetched incrementally using a cursor, allowing the client to process data without holding the entire result in memory.

Example Walkthrough

Consider the simple query: SELECT name FROM employees WHERE salary > 50000; 1. Parsing and validation: The string is tokenized, parsed into a tree, and checked against the employees table schema. The system confirms that name and salary exist and that the comparison is valid. 2. Optimization: If an index exists on salary, the optimizer may choose an index scan; otherwise a full table scan. The predicate salary > 50000 is pushed down to the scan step. 3. Execution: The storage engine reads the relevant pages, filters rows, and projects the name column. 4. Result: The matching rows are returned to the client.

Practical tip: In PostgreSQL you can see the chosen plan with EXPLAIN; in MySQL use EXPLAIN or FORMAT=JSON to inspect the optimizer’s decisions. Understanding these steps helps you write more index‑friendly queries and interpret execution plans when tuning performance.

69

How does EXPLAIN reveal a query execution plan?

A query execution plan is the operator tree produced by the database optimizer, showing how rows are retrieved, combined, filtered, and aggregated. EXPLAIN displays the plan; in PostgreSQL, adding ANALYZE executes the query and supplements estimated costs with actual timings and row counts.

Read full answer

Applies todatabase management systems; PostgreSQL 16 and MySQL 8.0 (InnoDB)

How an Execution Plan Works

The optimizer chooses an execution strategy based on table statistics, indexes, estimated row counts, join order, and available memory. Its output is a tree in which each node receives rows from its child nodes and passes a transformed result to its parent.

Plan component Meaning Common examples
Scan Retrieves rows from a relation Seq Scan, Index Scan, Bitmap Heap Scan
Join Combines rows from two inputs Nested Loop, Hash Join, Merge Join
Transformation Filters, sorts, or groups rows Filter, Sort, Aggregate
Limiting Stops after enough rows are produced Limit

A Seq Scan is not automatically a problem. On a small table, reading the table sequentially may be cheaper than using an index. On a large table with poor selectivity, it may indicate a missing or unsuitable index.

Reading EXPLAIN Output

For PostgreSQL, start at the leaves and work upward:

  1. Identify the source scans: These read the base tables or indexes.

  2. Follow data flow upward: Joins and transformations consume their child results.

  3. Compare estimated and actual values: rows=... under the cost estimate is the planner’s prediction; actual rows=... shows what occurred.

  4. Check loops and multiplication: A node executed repeatedly may produce more total rows than its per-loop row count suggests.

  5. Find the expensive operation: Focus on high actual time, many rows removed, temporary I/O, or large differences between estimates and reality.

total cost is an abstract optimizer unit, not milliseconds. With ANALYZE, actual time is reported in milliseconds. The first time is startup time; the second is total time including rows returned to the parent node.

PostgreSQL and MySQL Differences

Feature PostgreSQL 16 MySQL 8.0
Estimated plan EXPLAIN SELECT ... EXPLAIN SELECT ...
Actual execution statistics EXPLAIN (ANALYZE) SELECT ... EXPLAIN ANALYZE SELECT ...
Structured output FORMAT JSON, FORMAT YAML, text FORMAT=JSON, FORMAT=TREE, traditional tabular output
Buffer statistics BUFFERS with ANALYZE Not exposed through the same option
Main execution model Executor consumes operator-tree nodes Server uses iterator-style access and join operators

MySQL’s EXPLAIN ANALYZE executes the statement, while ordinary EXPLAIN estimates its execution. Both systems may select different plans because their optimizers, cost models, statistics, and index implementations differ.

Code Example

The following PostgreSQL example creates a small employee hierarchy:

CREATE TABLE employee (
    employee_id integer PRIMARY KEY,
    name text NOT NULL,
    manager_id integer REFERENCES employee(employee_id),
    salary numeric(10, 2) NOT NULL
);

INSERT INTO employee VALUES
    (1, 'Ava',   NULL, 7000.00),
    (2, 'Ben',   1,    5000.00),
    (3, 'Chloe', 1,    6000.00),
    (4, 'Dan',   2,    4500.00);

EXPLAIN (ANALYZE, BUFFERS, SUMMARY OFF)
SELECT e.name AS employee, m.name AS manager
FROM employee AS e
LEFT JOIN employee AS m
  ON m.employee_id = e.manager_id
WHERE e.salary >= 5000
ORDER BY e.name;

A representative plan, with costs and timings abbreviated, is:

Sort
  ->  Hash Left Join
        Hash Cond: (m.employee_id = e.manager_id)
        ->  Seq Scan on employee e
              Filter: (salary >= 5000.00)
        ->  Hash
              ->  Seq Scan on employee m

The query returns:

employee manager
Ava NULL
Ben Ava
Chloe Ava

The join preserves Ava even though she has no manager because the query uses LEFT JOIN. PostgreSQL may choose a Nested Loop instead of a Hash Left Join depending on statistics and configuration.

Best Practices and Pitfalls

  • Run ANALYZE on PostgreSQL tables after substantial data changes so the optimizer has current statistics.

  • Investigate large estimate-to-actual row differences; they often reveal stale statistics, correlated predicates, or incorrect assumptions.

  • Treat Seq Scan as a cost decision, not an automatic defect.

  • Remember that EXPLAIN ANALYZE executes the statement. It can cause write side effects, so use it cautiously with INSERT, UPDATE, or DELETE.

  • Avoid running expensive EXPLAIN ANALYZE queries during production peaks.

  • Look beyond a single plan: a query can be fast in isolation but expensive under different data volume, concurrency, cache state, or parameter values.

70

How does a query optimizer choose an execution plan?

A query optimizer chooses an execution plan by estimating the cost of alternative plans and selecting the one with the lowest estimated cost. It considers logical transformations, data access methods, join algorithms, join order, sorting, aggregation, parallelism, and available memory.

Read full answer

Applies todatabase management systems (PostgreSQL 16 and MySQL 8.4 InnoDB)

Planning Pipeline

A typical optimizer performs these stages:

Stage Purpose Example
Parsing and analysis Validate SQL and build a parse tree Resolve tables, columns, types, and functions
Logical rewriting Simplify or normalize the query Transform a nested IN subquery into a semijoin where appropriate
Plan generation Generate alternative physical operations Sequential scan, index scan, hash join, merge join
Cost estimation Estimate rows, I/O, CPU, and memory usage Estimate that a filter will match 5% of rows
Plan selection Compare candidate plans Select the estimated cheapest plan

The logical plan describes what must be computed, such as joins and filters. The physical plan specifies how the executor will compute it, such as using a sequential scan followed by a hash join.

Cost Estimation

The optimizer relies mainly on statistics maintained by the DBMS:

  • Table and index size: Number of pages, tuples, and index entries.

  • Column distribution: Minimum, maximum, most-common values, histograms, and distinct-value counts.

  • Selectivity: Estimated proportion of rows satisfying a predicate.

  • Correlation: Whether the physical order of values matches their logical order.

  • System resources: Memory limits, CPU availability, and storage characteristics.

For example, if an indexed column matches 1% of a large table, an index lookup may be attractive. If it matches 90%, a sequential scan may be cheaper because random index access and table-row lookups become expensive.

The selected plan minimizes an estimated cost, not actual elapsed time. Estimation errors, cold caches, lock contention, or physical storage layout can make the fastest runtime plan different from the optimizer’s choice.

Worked PostgreSQL Example

Suppose departments has columns id, name, and region, with id as its primary key. Suppose employees has columns id, name, dept_id, and salary, with a primary key on id, a foreign key from dept_id to departments.id, and an index on dept_id.

After loading three departments and four employees, consider SELECT e.name, d.name FROM employees AS e JOIN departments AS d ON d.id = e.dept_id WHERE d.region = 'West' ORDER BY e.salary DESC LIMIT 3.

Its result is:

Employee Department
Ada Engineering
Cleo Engineering
Dan HR

Because these tables contain only a few rows, PostgreSQL will likely use a sequential scan for at least one table. It may use a nested loop with primary-key lookups or a hash join, depending on its cost estimates; the plan is not guaranteed. With a larger dataset and selective statistics, index scans or bitmap heap scans may become preferable. EXPLAIN (ANALYZE, BUFFERS) displays the chosen plan together with actual rows, timings, and buffer usage.

Plan Search and Join Selection

The optimizer may consider:

  • Scan methods: Sequential scan, index scan, bitmap scan, index-only scan.

  • Join algorithms: PostgreSQL 16 supports nested-loop, hash, and merge joins; MySQL 8.4 supports nested-loop and hash-join strategies but has no general merge join.

  • Join order: Starting with the most selective relation can reduce intermediate results.

  • Grouping methods: Hash aggregate, sorted aggregate, or index-based grouping.

  • Ordering methods: Index ordering, merge sort, or top-N heapsort.

PostgreSQL uses dynamic-programming-style search for many manageable join problems and heuristic or genetic optimization for larger search spaces. MySQL also uses cost-based optimization and heuristics for complex join enumeration.

Real-System Differences

The textbook model often simplifies I/O as sequential versus random page access. Actual execution is also affected by:

  • Buffers already cached in memory

  • SSD read latency and parallel I/O

  • Lock contention and concurrent workloads

  • Partitioning and distributed data placement

  • Parallel execution and work-memory limits

  • Network transfer costs in distributed databases

Optimizers use configured cost constants, memory settings, and parallel-worker limits, but they generally do not directly observe current cache residency or lock waits. These are therefore major sources of difference between estimated and actual execution time.

Best Practices and Common Pitfalls

  • In PostgreSQL, run ANALYZE when appropriate and ensure automatic statistics maintenance is functioning; in MySQL, use ANALYZE TABLE table_name.

  • Investigate suspiciously large row-estimate errors with each system’s EXPLAIN facilities.

  • Use PostgreSQL EXPLAIN (ANALYZE, BUFFERS) or MySQL EXPLAIN ANALYZE to compare estimated and actual rows and timings.

  • Remember that both EXPLAIN ANALYZE forms execute the statement; avoid running unsafe writes without transaction control.

  • Review indexes that are missing, redundant, or poorly matched to query predicates.

  • Do not assume a plan remains optimal after major data-distribution changes.

71

How do nested loop, hash join, and merge join compare?

A join algorithm combines rows from two relations according to a join condition. Nested-loop, hash, and merge joins differ mainly in how they locate matches, their expected cost, memory requirements, and the inputs and predicates they favor.

Read full answer

Applies toDBMS fundamentals; PostgreSQL 16 and MySQL 8.0.18 and later 8.0 releases (InnoDB)

Core Comparison

Algorithm Basic operation Expected processing cost Memory usage Best suited for
Nested loop For each outer row, scan or search the inner relation O(m × n) without indexes; less with effective indexes Usually low Small inputs or selective inner-side index lookups
Hash join Build a hash table and probe it with the other relation Expected O(m + n), excluding output generation Based on the build side; moderate to high Large equality joins on unsorted inputs
Merge join Merge sorted streams and emit matching rows O(m + n) after ordering; sorting adds approximately O(m log m + n log n) Often low while merging; sorting may require memory or disk Equality and supported range joins with ordered inputs

Here, m and n are the numbers of rows in the two inputs. These costs do not include producing the output: duplicate join keys can produce O(m × n) output rows.

How Each Algorithm Works

  • Nested loop join:

  • Select one relation as the outer input and the other as the inner input.

  • For every outer row, scan the inner relation or perform an index lookup and test the join condition.

  • Without indexes, it requires approximately m × n predicate tests.

  • With an index on the inner join key, each outer row may require only a small number of index operations.

  • The optimizer generally prefers the side expected to produce fewer rows as the outer input because the inner side is accessed repeatedly.

  • Hash join:

  • Insert the build-side join keys and corresponding rows into a hash table.

  • Scan the probe side and look up each join key in that table.

  • It is especially effective for equality predicates such as orders.customer_id = customers.customer_id.

  • Duplicate keys must retain all matching rows, so the output can be much larger than either input.

  • PostgreSQL 16 can spill hash-join batches to disk when the build-side hash table exceeds the memory permitted by work_mem; other engines may handle memory exhaustion differently.

  • Merge join:

  • Obtain both inputs in join-key order, using sorted input paths or explicit sorting when necessary.

  • Compare the leading rows and advance the side with the smaller key.

  • On matching rows, advance one or both sides depending on the predicate and whether duplicate keys remain.

  • It efficiently handles equality joins and supported inequality or range predicates, such as o.created_at <= c.created_at.

Worked Example

Suppose the inputs are:

order_id customer_id
1 101
2 102
3 101
customer_id name
101 Ada
102 Bob
103 Charlie

An inner join on orders.customer_id = customers.customer_id returns:

order_id customer_id name
1 101 Ada
2 102 Bob
3 101 Ada
  • A hash join could build the hash table from customers and probe it with the three orders rows.

  • A merge join could process both inputs in customer_id order and emit matches as they are encountered.

  • A nested loop join could scan or index-search customers once for each orders row. It is reasonable for these tiny inputs but scales poorly without an effective index.

Optimizer and System Differences

  • PostgreSQL 16 provides nested-loop, hash, and merge join plan nodes. Its planner considers estimated row counts, selectivity, sort costs, memory limits, and available index ordering. Hash joins support equality conditions, while merge joins can handle equality and supported non-equality conditions.

  • MySQL 8.0.18 and later 8.0 releases include hash-join support for equality joins, although indexed nested-loop access paths remain common. MySQL does not provide a general-purpose sort-merge join operator.

  • The textbook model presents three distinct algorithms, but real optimizers choose among available physical implementations and may switch approaches as estimates and runtime information change.

  • Join order can be as important as the algorithm. Placing the side expected to produce fewer rows outside a nested-loop operation can substantially reduce repeated inner work.

Best Practices and Pitfalls

  • Use a nested loop join when an effective inner-side index makes repeated lookups cheap.

  • Use a hash join for large equality joins when inputs are unsorted and sufficient memory is available.

  • Use a merge join when ordered inputs are available or when a supported range predicate makes hashing unsuitable.

  • Do not assume the physical algorithm follows the join order written in the SQL. Optimizers may reorder joins.

  • Inspect the execution plan and compare estimated with actual row counts; inaccurate statistics can cause poor join-algorithm and join-order choices.

72

How does database partitioning differ from sharding?

Database partitioning divides one logical table into smaller, manageable subsets, while sharding distributes those subsets across multiple database servers. Partitioning is primarily a data-management technique within a database; sharding is a distributed-database scaling architecture.

Read full answer

Applies todatabase management systems, including PostgreSQL 16 and MySQL 8.0 InnoDB

Core Difference

Aspect Partitioning Sharding
Scope Divides one logical table or dataset Distributes data across multiple database instances
Primary purpose Manageability, pruning, indexing, and archival Horizontal scalability and capacity distribution
Control layer Usually handled by the DBMS Usually designed and coordinated by the application or a distributed data layer
Typical topology Partitions may remain on one database server Each shard is normally an independent server or cluster
Routing The DBMS selects relevant partitions The application or middleware determines the target shard
Horizontal split Yes, commonly by time, key, or hash Yes, typically by tenant, customer, or entity identifier
Vertical split Yes Possible, but “sharding” usually refers to horizontal distribution

A database can use both: a table can be partitioned inside each shard, and each shard can itself contain many partitions.

How Partitioning Works

In horizontal partitioning, rows are assigned according to a partition key. For example, an orders table could be divided by order_date:

Partition Included rows
orders_2026_01 Orders placed in January 2026
orders_2026_02 Orders placed in February 2026
orders_2026_03 Orders placed in March 2026

When a query includes a date range, the DBMS can use partition pruning to avoid scanning irrelevant partitions. For example, a February report only needs to inspect orders_2026_02 rather than every historical partition.

  • Range partitioning: Uses ranges such as months, years, or ID intervals.

  • List partitioning: Assigns rows using explicit values.

  • Hash partitioning: Assigns rows using a hash function, distributing them more evenly.

  • Vertical partitioning: Separates columns into different tables, often to isolate large or frequently accessed fields.

PostgreSQL 16 supports declarative RANGE, LIST, and HASH partitioning. MySQL 8.0 InnoDB also supports several partitioning strategies, but native partitioning does not distribute partitions across independent servers.

How Sharding Works

In sharding, a routing key determines which server owns a row. Suppose an application uses customer_id to distribute customers across three shards:

Customer ID Assigned shard
1001 Shard A
1002 Shard B
1003 Shard C

A request for customer 1002 is routed directly to Shard B. The shard key should provide a stable mapping; changing it later may require expensive data movement.

Common sharding strategies include:

  • Range-based sharding: Assigns contiguous key ranges to servers. Simple, but can create uneven load.

  • Hash-based sharding: Maps keys to shards using a hash. Produces more even distribution, but makes range queries harder.

  • Directory-based sharding: Stores a mapping from tenant or key to shard. Flexible, but the directory becomes an additional coordination component.

  • Geographically distributed sharding: Places data near users or regions while addressing latency and regulatory requirements.

Trade-offs and Practical Considerations

Partitioning simplifies large-table administration, but it does not automatically increase total server capacity. It can improve performance through pruning, reduce the amount of data affected by index maintenance, and make time-based retention easier. However, too many small partitions can increase planning overhead and metadata management.

Sharding can distribute storage, read traffic, and write workloads across multiple machines. Its costs include cross-shard joins, global uniqueness constraints, distributed transactions, rebalancing, and more complex failure recovery. Queries that must inspect every shard may also become slower because the application must perform scatter-gather processing.

For most systems, prefer partitioning first when the bottleneck is table size, maintenance, or retention. Consider sharding when one database instance cannot meet capacity, availability, latency, or write-throughput requirements. The exact boundary is operational rather than absolute: textbook models describe partitioning as intra-database organization and sharding as inter-database distribution, while real systems often combine both.

73

What are the main types of database replication?

Database replication is the process of maintaining one or more copies of a database by continuously or periodically transferring committed changes from a source database to destination databases. The source is commonly called the primary, and the copies are called replicas; older texts may use the now-obsolete terms “master” and “slave.”

Read full answer

Applies torelational databases, including PostgreSQL 16 and MySQL 8.0 with InnoDB

Core Concepts

Replication provides redundancy, supports read scaling, and can enable failover when the primary becomes unavailable. It is not the same as backup:

  • Replication distributes operational changes and usually keeps replicas relatively current.

  • Backup creates recoverable copies at selected points in time.

  • A corrupted write can be replicated to every replica, so replication does not replace backups.

Replication also introduces a replication lag: a replica may temporarily lack transactions already committed on the primary.

Main Types

Replication types are classified along several independent dimensions.

Classification Types Meaning
By data representation Physical replication Copies database files, pages, or WAL records. It usually produces an exact clone and supports low-latency recovery. PostgreSQL uses physical WAL streaming replication.
By data representation Logical replication Transfers logical changes, such as inserted, updated, or deleted rows, and reconstructs them in the replica. It supports selective table replication.
By timing Synchronous replication The primary waits for acknowledgment from one or more replicas before completing a commit according to its configured commit rules. This reduces data loss but may increase latency.
By timing Asynchronous replication The primary commits independently of replica progress. This improves write performance, but a primary failure can lose unreplicated changes.
By topology Primary-replica replication One primary accepts writes and sends changes to one or more read replicas.
By topology Multi-primary replication Multiple nodes accept writes and exchange changes. Write conflicts must be detected and resolved. MySQL Group Replication supports this model.
By initialization Full replication Initializes a replica with a complete database snapshot.
By initialization Incremental replication Applies only changes occurring after the replica was initialized, normally through transaction logs.
By topology Cascading replication A replica receives changes from the primary and forwards them to other replicas. This reduces primary load but can increase end-to-end lag.

How Replication Works

A typical replication pipeline is:

  1. The primary commits a transaction.

  2. The database records the change in its transaction log, such as PostgreSQL WAL or the MySQL binary log.

  3. A replication process transmits the log or logical changes.

  4. The replica applies them and updates its data or WAL.

  5. Monitoring measures delay and replica health.

Physical replication is common for disaster recovery because the replica closely matches the primary. Logical replication is useful when applications need targeted data distribution, cross-engine migration, or replicas containing only selected tables. Unlike most physical replication systems, logical replication may require separate handling of schema changes and can create conflicts when writes affect the same rows.

Small Example

Suppose the primary contains:

order_id customer status
101 Aarav paid
102 Meera pending

Immediately after transaction 102 is committed, an asynchronous replica might contain only order 101. It later receives and applies the change for 102.

With synchronous replication, the primary waits for the required replica acknowledgment before returning the successful commit according to the configured durability policy. This strengthens consistency but does not mean every query on the replica sees the newest committed data unless the application also controls read routing.

Trade-offs and Best Practices

  • Consistency versus latency: Synchronous replication reduces potential data loss but can slow primary commits and reduce availability during replica failures.

  • Performance: Log transmission and replica apply work consume I/O and CPU. Asynchronous replication usually has better primary write latency.

  • Read scaling: Reads can be directed to replicas, but stale results are possible. Use primary reads when immediate consistency is required.

  • Failover: Automated failover requires health checks, reliable replica promotion, and application reconnection logic.

  • Conflict handling: Multi-primary systems need deterministic conflict detection and a documented resolution policy.

  • Security: Replicate over encrypted, authenticated connections and restrict replication privileges.

  • Monitoring: Track replication lag, slot or log-position retention, disk capacity, and replication errors.

  • Recovery testing: Regularly verify that a promoted replica contains the expected data and that application clients reconnect correctly.

In PostgreSQL 16, physical streaming replication is the usual choice for high-availability standbys, while logical replication is preferred for selective change distribution. MySQL InnoDB commonly uses asynchronous replication; MySQL semi-synchronous replication adds acknowledgment behavior, while MySQL Group Replication provides a multi-primary model with transaction certification and conflict management.

74

How does the CAP theorem constrain distributed database design?

The CAP theorem states that a distributed database cannot simultaneously guarantee consistency, availability, and partition tolerance when a network partition occurs. In practice, it forces a system to prioritize either strong consistency or continued availability during connectivity failures.

Read full answer

Applies todistributed database systems, including PostgreSQL 16 and MySQL 8.4 InnoDB

How CAP Works

CAP examines the behavior of a distributed system when some nodes cannot communicate:

  • Consistency: Every successful operation observes the same up-to-date data according to a specified consistency model. In CAP, this usually means linearizability, not the complete ACID consistency model.

  • Availability: Every request to a non-failing node receives a non-error response, although that response might contain stale data.

  • Partition tolerance: The system continues operating despite an arbitrary network partition separating its nodes.

A network partition forces a C or A decision:

  • Choose C: Preserve linearizability by rejecting, blocking, or timing out requests that cannot be completed consistently. Rejecting such requests sacrifices CAP availability.

  • Choose A: Continue serving requests on both partition sides, potentially allowing divergent values and later reconciliation.

CAP does not say that a healthy system cannot provide all three properties. The trade-off is unavoidable when a partition exists.

Applying CAP to a Replicated Database

Suppose two database replicas contain an account balance:

Replica Balance Partition state
R1 100 Connected to client
R2 100 Connected to client

A partition then separates them, and a client withdraws 20 from each replica:

Replica Balance Accepted operation
R1 80 Withdraw 20
R2 80 Withdraw 20

This illustrates the trade-off:

  • CP behavior: One partition side may accept the withdrawal while the other rejects or waits for connectivity. The withdrawal is therefore committed only once, but requests on the unavailable side are not guaranteed to succeed.

  • AP behavior: Both sides accept the withdrawal to remain available. Their states diverge temporarily, so reconciliation must later choose one result or apply an application-specific conflict-resolution policy.

CAP can apply differently to different operations. A system may provide strongly consistent writes while serving eventually consistent reads or analytics.

CP Versus AP Characteristics

Property CP-oriented behavior AP-oriented behavior
Partition handling Blocks, times out, or rejects unsafe operations Continues serving requests
Consistency Maintains a linearizable committed history May diverge during the partition
Typical mechanism Consensus, quorum coordination, fencing Replication, conflict detection, reconciliation
Main risk Reduced availability during failures Stale reads or conflicting writes
Example pattern Consensus-backed coordination Dynamo-style eventual consistency

Quorums are commonly used in replicated databases:

  • W + R > N ensures that read and write quorums overlap.

  • W is the number of replicas that must acknowledge a write.

  • R is the number of replicas that must be consulted for a read.

  • N is the total number of replicas.

For N = 3, W = 2, and R = 2, the quorums overlap. However, overlap alone does not guarantee linearizability: the protocol must also enforce appropriate version or ordering rules and, in classic quorum systems, conditions such as R > N/2 and W > N/2. During a partition, replicas on a minority side may also be unable to form a quorum.

Real Database Differences

  • PostgreSQL 16 uses WAL-based streaming replication rather than a general consensus protocol. Optional synchronous replication can use priority or quorum commit, and synchronous_commit controls how far a standby must progress before the primary acknowledges a commit. Required standbys being unreachable can reduce availability, while reads from a standby are not automatically linearizable.

  • MySQL 8.4 InnoDB commonly uses asynchronous replication, which allows the primary to acknowledge writes without waiting for replicas but permits replica lag and possible data loss during failover. Group Replication adds certification and conflict detection for consistent transaction ordering; InnoDB Cluster adds orchestration around it. Read and failover consistency still depend on the primary mode, consistency settings, and client routing.

  • Protocols such as Paxos and Raft provide fault-tolerant coordination. They do not eliminate CAP’s trade-off: preserving one consistent committed order requires withholding some operations when the required communicating nodes are unavailable.

Interview Guidance

When discussing CAP, make these distinctions explicit:

  1. Say “consistency in CAP means linearizability,” not that CAP provides every ACID guarantee.

  2. Explain that partition tolerance is generally assumed for a distributed database that must continue operating through network failures.

  3. Identify which property the design sacrifices during a partition.

  4. Do not label a database permanently as “CP” or “AP” without specifying its configuration and failure model.

  5. Mention PACELC: during a partition, choose consistency or availability; otherwise, choose consistency or latency.

75

How do SQL and NoSQL databases differ?

SQL databases organize data relationally and expose it through the declarative SQL language, while NoSQL databases use non-relational models such as documents, key-value pairs, wide-column tables, and graphs. Their consistency, transaction, and scaling capabilities differ, but neither category has one fixed behaviour across every product.

Read full answer

Applies toSQL and NoSQL database concepts; PostgreSQL 16, MySQL 8.4 (InnoDB), MongoDB 8.0, Apache Cassandra 5.0, Redis 8.0, and Neo4j 5

Data Models and Schemas

Aspect SQL databases NoSQL databases
Data model Tables containing rows and columns Key-value, document, wide-column, graph, and other models
Schema Uses a declared schema that can be changed through DDL; the degree of enforcement varies Often provides schema flexibility, although some products enforce schemas for particular collections or tables
Relationships Represented through foreign keys, joins, and often normalized tables Commonly represented by embedded data, references, application-level assembly, or graph edges
Optimization General-purpose optimizers support indexes, joins, grouping, and complex predicates Access paths are often specialized for particular query patterns and data layouts

Relational databases do not automatically normalize data; normalization remains a deliberate schema-design technique for reducing redundancy and update anomalies. Likewise, most NoSQL systems provide some schema flexibility, but that flexibility varies significantly by product.

Queries and Data Access

SQL is standardized, although PostgreSQL and MySQL implement different dialects and extensions. SQL is particularly effective for joins, aggregation, subqueries, window functions, and reporting over related data.

NoSQL query facilities depend on the model. MongoDB uses document filters and aggregation pipelines, Redis primarily exposes key-based commands, Neo4j uses the Cypher graph-query language, and Cassandra uses CQL, which looks like SQL but has no joins or subqueries: each query reads one table, so data is denormalized into one table per query pattern.

For example, suppose users contains (1, Alice) and orders contains (101, 1, Book). A relational join can return (Alice, Book) in one statement. In a document design, the order could instead be embedded in the user document, or stored separately and retrieved with a second lookup. Embedding reduces application joins but may duplicate data; references avoid duplication but require additional reads.

Transactions and Consistency

SQL systems such as PostgreSQL and MySQL InnoDB support ACID transactions, including atomicity, rollback, and configurable isolation levels. Their defaults differ: PostgreSQL 16 defaults to READ COMMITTED, while MySQL InnoDB defaults to REPEATABLE READ. Applications requiring stronger serialization behaviour must select and configure it appropriately.

NoSQL products offer a wider range of guarantees:

  • MongoDB supports multi-document ACID transactions, although they require an appropriate deployment topology and impose operational constraints.

  • Cassandra exposes per-operation consistency levels such as ONE, QUORUM, and ALL; replicas may temporarily disagree depending on the selected level and current membership.

  • Redis provides atomic operations and optimistic concurrency controls, but its transaction model is not equivalent to a general-purpose relational transaction.

  • Other systems may provide eventual consistency, strong consistency for particular operations, or custom reconciliation mechanisms.

Consequently, “eventual consistency” is common in distributed NoSQL designs, but it is not mandatory for every NoSQL database or operation.

Scalability and Performance

SQL databases traditionally scale through larger servers, read replicas, caching, and partitioning. They can also be horizontally scaled through sharding or distributed SQL systems, although coordinating joins, transactions, and schema changes across partitions increases complexity.

Many NoSQL systems distribute data by partition key across multiple nodes, making horizontal scaling a common design goal. This does not guarantee linear scaling: skewed keys, hot partitions, replication overhead, network costs, and cross-partition operations can limit throughput.

Performance depends on the workload rather than the category alone. SQL databases can support high write volumes when batching, indexing, partitioning, and replication are designed correctly. NoSQL databases can provide low latency for their targeted access patterns while performing poorly for unindexed cross-partition queries. Specialized NoSQL stores may also outperform general-purpose databases for caching, session storage, time-series ingestion, or graph traversal.

Choosing a Database and Avoiding Pitfalls

Requirement Usually suitable starting point
Complex relational queries and transactional integrity SQL database
Banking, orders, inventory, and enterprise reporting SQL database
Rapidly varying document-shaped data Document database
Key lookup, caching, queues, or session state Key-value database
Time-ordered distributed writes Time-series or wide-column database
Highly connected data with multi-hop traversal Graph database

Do not select NoSQL merely because the application stores JSON, or select SQL merely because the expected data volume is large. Start with the required queries, consistency guarantees, transaction boundaries, data lifetime, and failure model. Then model the data, choose indexes and partition keys deliberately, test realistic read and write mixes, and verify backup, restore, replication, and failover behavior under the product’s actual configuration.

76

What are the main NoSQL database types and examples?

NoSQL databases store and retrieve data through non-relational models rather than representing data primarily as rows in normalized relations. The four widely recognized categories are key-value, document, wide-column, and graph databases, each optimized for different access patterns.

Read full answer

Applies togeneral NoSQL database concepts (all versions); PostgreSQL 16 and MySQL 8.4 LTS (InnoDB) as relational reference systems

Main Types

Type Data model Typical examples Best suited for
Key-value Unique key mapped to an opaque value Redis, Amazon DynamoDB, Riak Caching, sessions, counters, simple lookups
Document Self-contained JSON- or BSON-like documents MongoDB, Couchbase Flexible records, content management, event payloads
Wide-column Partitioned rows and sparse column families Apache Cassandra, Apache HBase, Google Bigtable Very large distributed datasets and predictable scalability
Graph Nodes, edges, and their properties Neo4j, Amazon Neptune Relationships, recommendations, fraud analysis

Other products, including time-series, spatial, and vector databases, are often presented as specialized categories. Their storage and indexing designs may overlap with the four primary models, but their APIs and workload models can be distinct.

Key-Value Databases

A key-value database treats the value as opaque to the database. The application decides whether the value contains JSON, text, binary data, or another format.

A simple Redis example could contain:

Key Value
user:102 {"name":"Asha","plan":"pro"}
session:8f31 eyJ1c2VyIjoxMDIifQ
visits:2026-01-10 1842
  • Advantages: Very low latency, simple horizontal partitioning, and efficient caching.

  • Limitations: Querying by fields inside a value may require application-side processing unless the product adds secondary indexing.

  • Example systems: Redis provides rich data structures rather than only strings; DynamoDB also supports more advanced querying.

Document Databases

Document databases store related fields together in one document. Documents can have different structures, although production databases often enforce validation through schemas or collection validators.

A MongoDB users collection might contain:

_id name Additional fields
102 Asha skills: SQL, Python
103 Ravi address.city: Pune
  • Advantages: Natural representation of API payloads, nested objects, and irregular attributes.

  • Limitations: Relationships can require references or application-side joins; careless document design can create duplication and inconsistent updates.

  • SQL comparison: PostgreSQL JSONB and MySQL JSON support document-like data, but they remain relational systems with SQL tables as their primary model.

Wide-Column Databases

Wide-column databases organize data into partitions and column families. Rows sharing a partition key are stored together, and cells can be sparse. Cassandra and HBase normally use schema-defined column families, while engines such as Bigtable allow more flexible column-family evolution.

A simplified Cassandra-style representation could be:

Partition key Name Email Address
customer:102 Asha asha@example.com Pune
customer:205 Ravi ravi@example.com —
  • Advantages: Efficient partitioning, predictable write latency, and high horizontal scalability.

  • Limitations: Join support and multi-partition queries are intentionally limited. Data placement must reflect the application’s query patterns.

  • Design consideration: A poor partition-key choice can create “hot partitions,” concentrating traffic on a small number of nodes.

Graph Databases

Graph databases represent entities as nodes and relationships as edges. Both can carry properties.

For example, a recommendation system might record that Asha and Ravi each have a WORKS_AT relationship with Acme, while Asha has a SKILLS relationship with SQL.

  • Advantages: Efficient relationship traversal, path discovery, and pattern matching.

  • Limitations: Graph queries can be complex, and highly regular tabular workloads may remain better served by relational databases.

  • Example systems: Neo4j and Amazon Neptune are commonly used graph databases.

Transactions, Consistency, and System Choices

NoSQL does not mean that a database lacks transactions or strong consistency. Support depends on the product, deployment mode, and operation:

  • Redis supports atomic commands and transactions, while broader distributed durability depends on configuration.

  • MongoDB supports multi-document ACID transactions in suitable replica-set configurations.

  • Cassandra provides tunable consistency per operation; quorum-based reads and writes can provide strong consistency when their consistency levels guarantee sufficient replica overlap.

  • Neo4j provides ACID transactions for supported graph operations.

The CAP theorem applies to distributed systems during a network partition: a system cannot simultaneously guarantee uninterrupted availability and linearizable consistency. It must reject or delay some operations or relax consistency. CAP therefore does not mean that every NoSQL database is eventually consistent.

Choose based on the dominant workload: use key-value storage for direct lookups, documents for flexible records, wide columns for partitioned high-volume data, and graphs for relationship-heavy traversal. For workloads requiring extensive joins, strict schema enforcement, and general-purpose transactional SQL, PostgreSQL or MySQL with InnoDB may be more appropriate.

77

How do OLTP and OLAP systems differ?

OLTP (Online Transaction Processing) manages high-volume, concurrent, short transactions such as inserting an order or updating an account. OLAP (Online Analytical Processing) analyzes large datasets using aggregations, trends, and complex reports, making it read-heavy rather than write-heavy.

Read full answer

Applies toall database management system versions; PostgreSQL 16 and MySQL 8.4 InnoDB are reference implementations

Core Difference

The primary distinction is the workload:

  • OLTP supports operational applications that process individual business events. It emphasizes low latency, transactional integrity, immediate visibility, and concurrent writes.

  • OLAP supports decision-making by summarizing historical and current data. It emphasizes fast scans, aggregations, large joins, and analytical queries.

OLTP and OLAP are workload categories rather than specific storage technologies. Many implementations use relational tables and SQL, but either workload can also use non-relational systems.

Side-by-Side Comparison

Characteristic OLTP OLAP
Typical workload CRUD operations and point lookups Dashboards, trends, forecasts, and summaries
Queries Small, indexed, and frequently repeated Large scans involving many rows and columns
Data volume per query Usually a few rows Often millions or billions of rows
Write pattern Frequent concurrent inserts and updates Periodic batch loads, with relatively few analytical writes
Transaction length Usually short May run for minutes or hours
Consistency Usually favors strict isolation and immediate visibility Often uses snapshot reads or slightly delayed data
Schema design Usually normalized, commonly near 3NF Frequently uses dimensional star or snowflake schemas
Index usage Selective B-tree indexes locate individual records Column pruning, compression, partition pruning, and sometimes zone maps reduce data read
Join pattern Many small joins among lookup tables Large fact-to-dimension joins, sometimes against pre-aggregated data
Storage design Commonly row-oriented Commonly column-oriented, though row-oriented engines can also process analytical queries
Optimization goal Low response time under concurrent writes High throughput for analytical scans and aggregations

Architecture and Trade-offs

  • Row-oriented storage keeps related values from a row together. This is efficient for OLTP operations such as retrieving an order and its customer.

  • Column-oriented storage groups values by column. Analytical queries often read only selected columns, so columnar storage avoids reading irrelevant data and supports efficient aggregation.

  • Normalization reduces redundancy in OLTP and protects update consistency. OLAP models often organize data into fact tables and dimension tables to simplify reports and reduce repeated joins.

  • Concurrency differs: OLTP systems commonly use MVCC and row-level or fine-grained locking. OLAP systems may prioritize parallel scans, snapshot reads, and batch processing over strict transactional isolation.

  • Indexes serve different purposes. OLTP benefits from selective indexes, but every additional index increases write and storage costs. OLAP benefits more from column pruning, partitioning, compression, materialized aggregates, and careful scan planning.

  • Real deployments often combine the workloads through replication, ETL or ELT pipelines, caching, or HTAP databases. PostgreSQL and MySQL/InnoDB are general-purpose, row-oriented engines capable of analytical queries, but dedicated columnar warehouses and lakehouse platforms generally offer better performance for large OLAP workloads.

For example, recording a customer order is an OLTP operation because it changes operational state and must complete quickly and consistently. Calculating monthly revenue by product and region from historical orders is an OLAP operation because it scans and aggregates many records.

Best Practices and Interview Takeaways

  • Choose OLTP for order processing, payments, inventory updates, and other real-time transactional workloads.

  • Choose OLAP for sales analysis, customer segmentation, forecasting, and executive reporting.

  • Do not assume an operational database automatically provides columnar performance; large analytical scans can interfere with production transactions.

  • Avoid unnecessary indexes on frequently updated OLTP tables, and avoid excessive or accidental cross joins and poorly pruned scans in analytical workloads.

  • In interviews, explain that the difference is primarily workload and optimization, not simply “transactions versus reports”; modern systems frequently support both workloads.

78

How do star and snowflake schemas differ in data warehousing?

A star schema organizes a warehouse around a central fact table and mostly flat, denormalized dimension tables. A snowflake schema retains the dimensional structure but normalizes dimensions into related tables, reducing redundancy at the cost of additional joins.

Read full answer

Applies todata warehousing (vendor-neutral concepts; examples applicable to PostgreSQL 16 and MySQL 8.4 InnoDB)

Core Components

Both schemas are forms of dimensional modeling designed for analytical queries rather than transactional processing.

  • Fact table: Contains measurements describing a business event, such as a sale, order, or account transaction.

  • Grain: Defines what one fact row represents. For example, the grain might be “one sale line for one product at one store on one date.”

  • Dimension tables: Store descriptive attributes used to analyze those measurements, such as products, customers, stores, and dates.

  • Foreign keys: Connect fact rows to dimension rows, usually through surrogate keys.

  • Measures: Numeric values such as quantity, revenue, cost, or balance. Some measures, such as revenue, are additive; others, such as an account balance, are not.

Star and snowflake schemas are logical design patterns, not special PostgreSQL or MySQL features. Either can be implemented using ordinary relational tables.

Star Schema

In a star schema, each dimension is stored as a mostly flat, denormalized table. The central fact table resembles the center of a star, while the surrounding dimension tables resemble its points.

An example retail model contains:

Table Important columns
fact_sales sale_id, order_date_key, customer_key, product_key, store_key, quantity, gross_amount, discount_amount, net_amount
dim_product product_key (primary key), product_code, product_name, category_name, brand_name
Other dimensions Date, customer, and store attributes organized in similarly flat tables

A small fact table might contain:

sale_id order_date_key customer_key product_key store_key quantity net_amount
1 101 201 301 401 2 50.00
2 102 202 302 401 1 20.00

The corresponding dim_product rows could be:

product_key product_code product_name category_name
301 P100 Keyboard Electronics
302 P200 Mouse Electronics

Snowflake Schema

A snowflake schema normalizes dimension tables, commonly into third normal form. For example, category and brand information can be separated from product information:

Table Important columns
dim_product product_key (primary key), product_code, product_name, brand_key, category_key
dim_category category_key (primary key), category_name, department_key
dim_department department_key (primary key), department_name

dim_product.brand_key and dim_product.category_key reference their respective dimension tables, while dim_category.department_key references dim_department. The fact table still references dim_product.

Analyzing sales by category therefore requires additional joins along the path fact_sales → dim_product → dim_category → dim_department. This subdivision of the dimensional model resembles the branches of a snowflake.

Comparison

Aspect Star schema Snowflake schema
Dimension design Denormalized and mostly flat Normalized across related dimensions
Query joins Fewer joins and simpler SQL More joins and potentially more complex SQL
Storage Usually larger because attributes are repeated Usually smaller because redundancy is removed
Ease of maintenance Easier for common business users More involved because changes may affect multiple tables
Performance Often better for predictable analytical queries May require indexes, materialized views, or query optimization
Best fit Reporting and dashboards with stable dimensions Large or frequently shared reference dimensions

The trade-off is not absolute. Modern columnar analytical systems may handle snowflake joins efficiently, while a star schema with many duplicated attributes can consume substantial storage.

Best Practices and Pitfalls

  • Define the fact table’s grain before designing dimensions; every measure must make sense at that grain.

  • Use surrogate keys for dimensions while retaining natural identifiers such as product_code for traceability.

  • Avoid placing frequently changing descriptive fields directly in the fact table.

  • Use slowly changing dimensions to preserve history, commonly Type 2 for retaining previous dimension versions.

  • Partition very large fact tables by common filters such as date, but partitioning does not replace good dimensional design.

  • In PostgreSQL, index fact-table foreign-key columns when they are not already indexed. In MySQL InnoDB, foreign keys require supporting indexes, which InnoDB creates automatically when absent; check existing indexes before adding duplicates.

  • Do not confuse this concept with the Snowflake cloud data platform; “snowflake schema” is a traditional data-modeling term.

  • Prefer a star schema when simplicity and predictable join paths matter. Use a snowflake selectively when normalization meaningfully reduces redundancy without making analytical queries fragile.

79

How would you design an online shopping database schema?

A reliable online shopping schema uses a normalized relational model for customers, products, orders, inventory, and payments, while deliberately retaining immutable checkout snapshots such as the price, SKU, and product name purchased.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.4/InnoDB; the DDL below targets PostgreSQL 16

Core ER Design

Relationship Cardinality
Customer → Order One-to-many
Product → Product variant One-to-many
Order ↔ Product variant Many-to-many through order_items
Order → Payment One-to-many payment attempts
Product variant → Inventory One-to-one in this single-location model
  • Keys: Use surrogate primary keys and natural-key uniqueness constraints for email, sku, and provider references.

  • Snapshots: order_items copies the product name, SKU, and unit price so later catalog edits do not rewrite order history.

  • Totals: Derive item subtotals from immutable order lines. Add immutable tax, shipping, discount, and final-total columns when the business requires a stored checkout total.

  • Currency: An order uses one currency; checkout must reject variants or payments using a different currency.

  • Warehouses: For multiple fulfillment centers, replace the single inventory row per variant with an inventory_locations table keyed by variant and location.

Indexing, Concurrency, and Recovery

  • Index customer history with orders(customer_id, created_at DESC), processing queues with orders(status, created_at), product sales with order_items(variant_id), and payment lookup with payments(order_id).

  • PostgreSQL does not automatically index referencing foreign-key columns. InnoDB creates a supporting child-table index when necessary.

  • Checkout should run in one transaction: lock the relevant inventory rows with SELECT ... FOR UPDATE, verify on_hand_quantity - reserved_quantity, reserve stock, and write the order and lines atomically.

  • PostgreSQL defaults to READ COMMITTED; InnoDB defaults to REPEATABLE READ. Select isolation deliberately when stronger guarantees are required.

  • External payment calls cannot join the database transaction. Use idempotency keys, provider references, and a retry or saga workflow.

  • PostgreSQL uses WAL and base backups for recovery. InnoDB uses redo and undo logs, while MySQL point-in-time recovery also requires binary logs.

Code Example

The following PostgreSQL 16 DDL and indexes run in the displayed order:

CREATE TABLE customers (
    customer_id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    email VARCHAR(254) NOT NULL UNIQUE
        CHECK (email = lower(email)),
    full_name VARCHAR(120) NOT NULL
);

CREATE TABLE products (
    product_id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    name VARCHAR(200) NOT NULL
);

CREATE TABLE product_variants (
    variant_id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    product_id BIGINT NOT NULL REFERENCES products(product_id),
    sku VARCHAR(64) NOT NULL UNIQUE,
    price NUMERIC(12, 2) NOT NULL CHECK (price >= 0),
    currency VARCHAR(3) NOT NULL
        CHECK (currency ~ '^[A-Z]{3}$')
);

CREATE TABLE inventory (
    variant_id BIGINT PRIMARY KEY
        REFERENCES product_variants(variant_id),
    on_hand_quantity INTEGER NOT NULL DEFAULT 0
        CHECK (on_hand_quantity >= 0),
    reserved_quantity INTEGER NOT NULL DEFAULT 0
        CHECK (reserved_quantity >= 0),
    CHECK (reserved_quantity <= on_hand_quantity),
    updated_at TIMESTAMPTZ NOT NULL DEFAULT CURRENT_TIMESTAMP
);

CREATE TABLE orders (
    order_id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    customer_id BIGINT NOT NULL REFERENCES customers(customer_id),
    request_key VARCHAR(128) NOT NULL,
    status VARCHAR(20) NOT NULL
        CHECK (status IN
            ('pending', 'paid', 'fulfilled', 'cancelled', 'refunded')),
    currency VARCHAR(3) NOT NULL
        CHECK (currency ~ '^[A-Z]{3}$'),
    shipping_address TEXT NOT NULL,
    created_at TIMESTAMPTZ NOT NULL DEFAULT CURRENT_TIMESTAMP,
    UNIQUE (customer_id, request_key)
);

CREATE TABLE order_items (
    order_id BIGINT NOT NULL REFERENCES orders(order_id),
    variant_id BIGINT NOT NULL REFERENCES product_variants(variant_id),
    product_name VARCHAR(200) NOT NULL, -- Immutable checkout snapshot
    sku VARCHAR(64) NOT NULL,           -- Immutable checkout snapshot
    quantity INTEGER NOT NULL CHECK (quantity > 0),
    unit_price NUMERIC(12, 2) NOT NULL CHECK (unit_price >= 0),
    PRIMARY KEY (order_id, variant_id)
);

CREATE TABLE payments (
    payment_id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    order_id BIGINT NOT NULL REFERENCES orders(order_id),
    provider VARCHAR(30) NOT NULL,
    idempotency_key VARCHAR(128) NOT NULL,
    provider_reference VARCHAR(128), -- May be null before provider response
    amount NUMERIC(12, 2) NOT NULL CHECK (amount > 0),
    currency VARCHAR(3) NOT NULL
        CHECK (currency ~ '^[A-Z]{3}$'),
    status VARCHAR(20) NOT NULL
        CHECK (status IN
            ('initiated', 'succeeded', 'failed', 'refunded')),
    UNIQUE (provider, idempotency_key),
    UNIQUE (provider, provider_reference)
);

CREATE INDEX idx_orders_customer_created
    ON orders(customer_id, created_at DESC);

CREATE INDEX idx_orders_status_created
    ON orders(status, created_at);

CREATE INDEX idx_order_items_variant
    ON order_items(variant_id);

CREATE INDEX idx_payments_order
    ON payments(order_id);

CREATE UNIQUE INDEX idx_payments_one_success
    ON payments(order_id)
    WHERE status = 'succeeded';

Example query:

SELECT
    o.order_id,
    c.email,
    i.product_name AS product,
    i.sku,
    i.quantity,
    i.quantity * i.unit_price AS subtotal
FROM orders AS o
JOIN customers AS c ON c.customer_id = o.customer_id
JOIN order_items AS i ON i.order_id = o.order_id
WHERE o.order_id = 101
ORDER BY i.product_name, i.sku;

Illustrative result:

order_id email product sku quantity subtotal
101 alice@example.com Keyboard K-01 1 49.99
101 alice@example.com Mouse M-02 2 39.98

Production Practices

  • Use PostgreSQL full-text search or an index from the pg_trgm extension for catalog search. In MySQL, use InnoDB FULLTEXT indexes where appropriate.

  • Cache product pages and search results in Redis when read traffic warrants it.

  • PostgreSQL can range-partition orders by created_at; in MySQL, partitioning imposes unique-key restrictions that must be evaluated first.

  • Never store raw card details. Store provider tokens or opaque payment references.

  • In MySQL 8.4, replace identity syntax with AUTO_INCREMENT, use DATETIME(6) with CURRENT_TIMESTAMP(6) for UTC timestamps, and replace ~ with REGEXP. MySQL has no direct partial-index equivalent; enforce one successful payment by locking the order row in a transaction.

80

Diagnosing and fixing slow SQL queries in production

Slow query optimization in production is a systematic process of identifying expensive statements, separating execution time from wait time, examining execution plans, and applying measured fixes such as better indexes, query rewrites, fresher statistics, or resource configuration.

Read full answer

Applies toPostgreSQL 16 and MySQL 8.0 (InnoDB; MySQL 8.0.18+ for `EXPLAIN ANALYZE`).

1. Detecting the Problem

  • PostgreSQL: Install pg_stat_statements by adding it to shared_preload_libraries, restarting PostgreSQL, and running CREATE EXTENSION pg_stat_statements. Compare calls, mean_exec_time, and total_exec_time, grouping normalized statements by meaningful workload.

  • MySQL: Enable the slow query log and choose an appropriate long_query_time, or use Performance Schema tables such as events_statements_summary_by_digest and events_statements_history_long.

  • Application level: Measure SQL latency separately from database wait time. Use application instrumentation, tracing, or an APM, and inspect lock and wait events before concluding that CPU-intensive execution is the bottleneck.

A 500 ms query does not appear in a MySQL slow log configured with long_query_time = 2, although it may be visible in aggregate statistics or application traces.

2. Reading the Execution Plan

  • PostgreSQL: EXPLAIN (ANALYZE, BUFFERS) reports actual timings, row counts, and buffer activity. EXPLAIN without ANALYZE only estimates the plan.

  • MySQL: EXPLAIN FORMAT=JSON shows estimates and access paths; EXPLAIN ANALYZE reports actual execution information on supported 8.0 versions.

  • Full scans: PostgreSQL Seq Scan and MySQL type: ALL are not automatically defects. They can be appropriate for small tables or predicates matching a large fraction of rows.

  • Estimate errors: Compare estimated and actual row counts. Large differences often indicate stale statistics, correlated predicates, or insufficient statistics.

  • Expensive operations: Look for large sorts, hash joins, repeated nested loops, and PostgreSQL sorts reporting external merge Disk. MySQL’s Using filesort does not by itself prove that the sort used disk.

  • Cost interpretation: Planner costs are unitless estimates, not elapsed milliseconds, and should mainly be compared between plans for the same query.

EXPLAIN ANALYZE executes the statement, so use it cautiously in production, especially for modifying statements.

3. Common Causes and Fixes

Cause Symptom Correct response
Missing selective index Full scan and high estimated cost Add an index when the predicate is selective; confirm that the planner uses it
Excess columns More rows and bytes transferred Select only required columns
Non-sargable predicate Indexed column appears inside a function Use an expression index matching the predicate, or rewrite it without changing semantics
Poor join plan Large intermediate row counts Join on indexed keys and refresh statistics
Stale statistics Estimated and actual counts differ Run ANALYZE in PostgreSQL or ANALYZE TABLE in MySQL
Resource pressure Disk waits, low cache hit rates, high memory use Tune configuration cautiously and validate under load

For example, salary > 100000 is not equivalent to ABS(salary) > 100000 when negative salaries are possible. PostgreSQL also does not automatically index referencing columns for foreign keys; MySQL InnoDB normally creates a required index when one is missing.

Code Example

The following PostgreSQL 16 example creates a small table and shows the result rows:

CREATE TABLE employees (
    id integer PRIMARY KEY,
    name varchar(100) NOT NULL,
    salary numeric(12,2) NOT NULL
);

INSERT INTO employees (id, name, salary) VALUES
    (1, 'Alice', 80000.00),
    (2, 'Bob', 150000.00),
    (3, 'Priya', 950000.00);

ANALYZE employees;

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, name
FROM employees
WHERE salary > 900000;

The query returns:

id name
3 Priya

Test the proposed index and inspect the new plan:

CREATE INDEX idx_emp_salary ON employees (salary);

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, name
FROM employees
WHERE salary > 900000;

On such a small table, PostgreSQL may still choose a sequential scan because it is cheaper. Validate index decisions with representative data volume and statistics.

4. Validating the Fix

  • Compare the same parameters, data, and concurrency level before and after the change.

  • Measure latency percentiles such as p95 and p99, throughput, rows returned, CPU, I/O, and lock waits.

  • Test on a staging environment with representative data and cardinality.

  • Monitor the statement afterward through pg_stat_statements, the slow query log, Performance Schema, or application traces.

  • Verify correctness, rollback procedures, index storage, and write overhead before production rollout.

5. Best Practices

  • Avoid SELECT *, N+1 ORM access patterns, and unnecessary sorting or duplication.

  • Keep statistics current; both systems support automatic statistics maintenance, while bulk loads may justify targeted manual analysis.

  • Use covering indexes only for matching projections. PostgreSQL index-only scans also depend on visibility-map maintenance, while InnoDB secondary indexes include the primary key.

  • Prefer a staging-tested CREATE INDEX CONCURRENTLY or online index operation when appropriate, while accounting for their operational limitations.

  • Treat work_mem as a per-operation PostgreSQL limit, not a total process-memory guarantee.

  • Use MySQL optimizer hints sparingly. PostgreSQL 16 has no native optimizer-hint syntax; third-party extensions are required.

  • Treat every plan or configuration change as an experiment: retain the baseline, deploy gradually, and roll back when expected improvement is absent.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 80 DBMS answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All CS Fundamentals subjects