What a DBMS provides

A DBMS manages data together with rules and services so applications do not manipulate raw files directly. It exposes database operations or a query language and keeps metadata and schemas to know the structure of the data. Central management helps reduce uncontrolled redundancy and makes it easier to enforce rules consistently.

• Metadata and schemas: DBMS knows data structure through metadata and schemas rather than leaving structure to each program.
• Query/API access: Applications use query languages and database APIs instead of application-specific file handling.
• Integrity rules: Built-in constraints and rules enforce data integrity rather than relying solely on application checks.
• Concurrency control: DBMS provides built-in concurrency control so multiple users/applications can access data safely.
• Security: Access is managed via users, roles, privileges and policies, beyond simple file-level permissions.
• Recovery: DBMS uses logs, transactions and recovery mechanisms rather than manual backup/restore logic.

Three levels of a database system

Database systems are commonly understood at three levels; each level separates concerns so changes below need not affect the ones above.

• Physical level: Describes how data is actually stored (files, pages, indexes, storage structures).
• Logical level: Describes tables, attributes, relationships, and constraints.
• External (view) level: Contains the different views seen by users or applications.

Forms of data independence

There are two main forms of data independence, with examples of each.

• Physical data independence: Storage details can change without changing the logical schema. Example: the DBMS may add an index or reorganize files without requiring application changes.
• Logical data independence: The logical schema can change with minimal effect on user views or applications. Example: a table may be extended or reorganized while existing views continue to present the same required data.

Schema — the design

The schema is the database's design or structure. It defines what objects exist and how they relate to each other.

• Defines: table names, columns, data types, relationships, keys, and constraints

Instance — the current data

The instance is the actual data stored in the database at a particular moment in time. It consists of the rows and values that conform to the schema.

• Contents: actual rows and values
• Changes: modifies whenever rows are inserted, updated, or deleted

Concrete example

An example helps distinguish the two: the schema specifies the structure, while the instance holds specific records.

• Schema example: Student(id, name, email)
• Instance example: (101, Asha, a@x.com)

Example

Suppose a Student table has roll_no, email, and phone, and all three are individually unique. Then each of {roll_no}, {email}, and {phone} is a candidate key. The designer might choose roll_no as the primary key; the remaining candidate keys become alternate keys.

• Candidate keys: {roll_no}, {email}, {phone}
• Primary key: roll_no (chosen example)

Choosing a primary key

A good primary key is usually stable, unique, non-null, and preferably small. The primary key imposes a single primary key constraint on the table.

Remember: every primary key is a candidate key, but not every candidate key is selected as primary; the unselected candidate keys are often called alternate keys.

• Good primary key traits: stable, unique, non-null, preferably small

Common Referential Actions

The foreign key constraint can specify a referential action to determine how the DBMS handles updates or deletes of the referenced parent row.

• RESTRICT / NO ACTION: prevent the parent update/delete when matching child rows exist.
• CASCADE: automatically apply the related update/delete to child rows.
• SET NULL: keep the child row but clear the foreign key, if NULL is allowed.
• SET DEFAULT: replace the foreign key with its defined default value, if the DBMS/schema supports it.

Table examples

Provide simple table structures that capture primary attributes and the enrollment relationship.

• Student: student_id PK, name, email, ...
• Course: course_id PK, title, credits, ...
• Enrollment: student_id FK, course_id FK, semester, grade, enrollment_date, ...

Keys and uniqueness

Decide how to identify Enrollment rows based on requirements. Two common approaches are described below.

If you need to prevent duplicate enrollments, enforce uniqueness either via a composite primary key or a uniqueness constraint.

• Composite key option: (student_id, course_id, semester) could form a composite primary key.
• Surrogate key option: Enrollment could have its own enrollment_id primary key plus a uniqueness constraint to prevent duplicate enrollments.

How it works

The associative table contains the foreign keys of both participating entities; each row represents one specific relationship instance. For example, with students and courses, an associative entity named Enrollment holds the student and course foreign keys so Student -> Enrollment is one-to-many and Course -> Enrollment is one-to-many.

• Relationship mapping: Student -> Enrollment is one-to-many.
• Relationship mapping: Course -> Enrollment is one-to-many.

Benefits and enforcement

An associative entity centralizes the relationship and provides several practical advantages: it gives the relationship its own place to store attributes that belong to the relationship itself, foreign key constraints can enforce valid references to both entities, and indexes can be created on the relationship keys for efficient querying. Overall this produces cleaner rows, stronger integrity, and simpler queries than trying to represent the M:N relationship directly with repeated values.

• Relationship attributes: Enrollment can store grade, semester, enrollment_date, status, or other relationship data.
• Referential integrity: Foreign key constraints can enforce valid Student and Course references.
• Performance: Indexes can be created on the relationship keys for efficient querying.

Overview and motivating example

Insertion, update, and deletion anomalies are problems caused by storing multiple independent facts in one poorly designed table. They lead to unnecessary restrictions, repeated updates, or accidental loss of information.

A common motivating example is a StudentCourse table that contains Student, Course, and Teacher. If the same course is taken by many students, the course and teacher information is repeated across many rows, which creates the conditions for the three anomalies described below.

• Table example: StudentCourse table with Student, Course, and Teacher — course and teacher details repeated across rows.

Insertion anomaly

An insertion anomaly occurs when you cannot store one fact without also having unrelated data. The table design forces you to include data that may not yet exist or is irrelevant to the fact you want to record.

• Example: You may be unable to add a new course until at least one student enrolls in it.

Update anomaly

An update anomaly happens when the same fact appears in many rows. Changing that fact requires updating every repeated row; missing even one update creates inconsistent data across the table.

• Example: If a teacher's name changes, every row containing that teacher must be updated. Missing a row yields inconsistent data.

Deletion anomaly

A deletion anomaly arises when deleting a row to remove one fact inadvertently removes another independent fact because they were stored together in the same row.

• Example: Deleting the last student enrolled in a course may also remove the only stored information about that course and its teacher.

Decision criteria — what to check

I would check whether the table contains repeated customer information, repeating groups, mixed facts, functional dependencies, or insertion/update/deletion anomalies. If it does, normalization is usually needed.

• Repeated values: The same customer name or phone appears many times when a customer places several orders.
• Repeating groups: Order or item information is stored in repeated columns or rows instead of separate rows/entities.
• Mixed facts: Attributes with different dependencies (customer-level vs order-level vs order-item-level) are stored in one table.
• Functional dependencies: Attributes should be tested for what key they actually depend on (customer, order, or order-item).
• Anomalies: Insertion, update, or deletion anomalies indicate the need for normalization.

Analyze attribute dependencies

Ask what each attribute actually depends on. Use the dependencies to determine proper grouping of attributes.

• Customer-level: Customer details depend on the customer (e.g., name, phone).
• Order-level: Order details depend on the order (e.g., order_date, order_id linked to customer).
• Order-item-level: Item quantities depend on a particular order-item combination (order_id + item_id).

Example normalized design

A cleaner design would usually separate the stable entities so each table represents a single level of dependency.

• Customer: Customer(customer_id, name, phone, ...)
• Order: Order(order_id, customer_id, order_date, ...)
• OrderItem: OrderItem(order_id, item_id, quantity, ...)

Formal rule comparison

State the rules precisely to contrast them.

• 3NF rule: For a functional dependency X -> Y, either X is a super key OR Y is a prime attribute.
• BCNF rule: For a functional dependency X -> Y, X must be a super key (for every non‑trivial FD).

Practical implications and trade-offs

BCNF removes more redundancy because every determinant must uniquely identify a row (be a super key). However, achieving BCNF by decomposing a relation can sometimes make it harder to preserve all original functional dependencies in the decomposed tables. In contrast, 3NF is less strict and is often easier to use when dependency preservation is important.

• Redundancy: 3NF can allow some remaining redundancy; BCNF usually removes more redundancy.
• Dependency preservation: 3NF is often easier to preserve dependencies; BCNF may sacrifice dependency preservation.

Common use cases (examples)

Denormalization is commonly considered for workloads where reads greatly outnumber writes and query latency matters. Typical examples include:

• Reporting systems: Precompute or duplicate fields to avoid heavy joins when generating reports.
• Dashboards: Store aggregates or summary fields so dashboard queries return quickly.
• Materialized summaries: Maintain denormalized summary tables to serve aggregated queries.
• Analytics: Duplicate or pre-aggregate analytic dimensions to speed up queries.
• Read-heavy workloads: Any workload measured to be read-dominant where join cost is a bottleneck.

The four ACID properties

Each letter of ACID describes one guarantee a transaction system must provide.

• Atomicity: A transaction is all-or-nothing. Either every required operation succeeds, or the entire transaction is rolled back.
• Consistency: A successful transaction moves the database from one valid state to another while respecting defined rules and constraints.
• Isolation: Concurrent transactions should behave safely so that intermediate operations do not incorrectly interfere with each other.
• Durability: Once a transaction commits, its changes must survive failures such as a process or system crash.

Concrete example

A bank transfer illustrates how the properties interact: debiting Account A and crediting Account B are treated as one transaction.

• Atomicity in the example: If the credit to Account B fails, Atomicity prevents only the debit from remaining (the whole transaction is rolled back).
• Isolation in the example: Isolation protects the transfer from conflicting concurrent work so intermediate states are not observed by other transactions.
• Consistency and Durability in the example: Consistency keeps database rules valid during the transfer, and Durability ensures that a committed transfer is not lost after a crash.

Concrete example (account balance)

Suppose an account balance is 100. Transaction T1 reads 100 and plans to subtract 10, while T2 also reads 100 and plans to subtract 20. T1 writes 90. Then T2, still using the old value 100, writes 80. The final value becomes 80 even though both changes together should have produced 70. The update performed by T1 has effectively disappeared.

• Step 1: T1 reads balance = 100
• Step 2: T2 reads balance = 100
• Step 3: T1 writes 90
• Step 4: T2 writes 80
• Result: Expected combined result = 70; Actual final value = 80

How a DBMS can prevent or detect it

A DBMS can prevent or detect lost updates using suitable isolation, locking, MVCC conflict checks, or atomic update statements that modify the value without relying on a stale application-side copy.

• Isolation: Use appropriate transaction isolation to avoid concurrent reads/writes causing lost updates.
• Locking: Acquire locks so one transaction updates the value exclusively while others wait.
• MVCC conflict checks: Detect conflicting concurrent writes via multiversion concurrency control checks.
• Atomic updates: Use atomic update statements that modify the value on the server side rather than relying on a stale client-side copy.

Properties and trade-offs

A serial schedule is simple and safe because transactions never overlap. The disadvantage is poor concurrency: one transaction may keep others waiting even when some operations could safely run together. A serializable schedule allows concurrency while preserving the correctness expected from serial execution.

• Advantage: Serializable schedules provide higher concurrency while maintaining correctness equivalent to some serial order.
• Disadvantage: Serial schedules have low concurrency because transactions run one after another.

Concrete example (two transactions)

This sequence shows how a dirty read can occur:

• Step 1: T1: Update balance = 500 (original was 400) — not committed yet.
• Step 2: T2: Read balance = 500 (reads T1's uncommitted change).
• Step 3: T1: ROLLBACK — database value returns to 400; T2 used a value (500) that never became permanent.

Example

T1 reads an employee salary as 50,000. T2 updates that same salary to 60,000 and commits. When T1 reads the row again, it now sees 60,000. The same query against the same row has produced two different values during one transaction.

• Scenario: T1 reads 50,000 → T2 updates to 60,000 and commits → T1 reads 60,000

Deadlock detection — wait-for graph

The DBMS can detect deadlocks by constructing a wait-for graph and checking it for cycles. In this graph, each active transaction is represented as a node, and directed edges show waiting relationships.

• Edge meaning: An edge T1 -> T2 means T1 is waiting for a resource currently held by T2. A cycle in the graph indicates a deadlock.

Resolution steps

Once a cycle is detected, the DBMS resolves the deadlock by selecting one or more transactions as victims and rolling them back so other transactions can proceed.

• Detect cycle: Identify the cycle in the wait-for graph.
• Choose victim: Select one transaction in the cycle to abort (victim selection policy may vary).
• Abort/rollback: Abort or roll back the chosen victim transaction.
• Release locks: Release the victim's locks so other transactions can acquire the needed resources.
• Continue: Allow the remaining transaction(s) involved in the cycle to continue; the victim may be retried later.

Core mechanism

Two-Phase Locking controls when a transaction may acquire and release locks by dividing its execution into two phases. This enforced ordering prevents interleavings that would violate conflict-serializability.

• Growing phase: The transaction may acquire new locks, but it cannot release any lock.
• Shrinking phase: The transaction may release locks, but it cannot acquire any new lock.

Common variants

Several variants of 2PL adjust lock-holding behavior to trade off concurrency, deadlock risk, and recovery complexity.

• Basic 2PL: Growing phase followed by shrinking phase.
• Strict 2PL: Hold write/exclusive locks until commit or rollback.
• Conservative 2PL: Acquire required locks before execution begins.

How MVCC works

When a row is updated under MVCC, the system creates a new row version while preserving the older committed version. A transaction reading from a snapshot continues to see the appropriate older committed version even while another transaction creates a new version. Visibility rules and snapshots determine which version each transaction sees, allowing readers to proceed without acquiring locks that block writers.

• Readers: Read from a snapshot and often do not block or get blocked by writers.
• Updates: Create new row versions instead of modifying the existing version in place.
• Visibility rules: Snapshots and visibility rules decide which version a transaction can see.
• Cleanup: Old versions are eventually removed when no active transaction can still need them.

Benefits and costs

MVCC greatly reduces read-write blocking compared with strict lock-based execution and typically yields higher concurrency for read-heavy workloads. The trade-offs are additional storage for extra versions and the need for version cleanup; strict locking trades those costs for simpler state but can cause more waiting and lower concurrency under contention.

• Benefit: Readers continue without waiting for writers, reducing contention.
• Cost: Extra row versions and background cleanup (garbage collection) are required.

Which columns to index

Focus indexing effort on columns that the query actually uses. This includes columns in WHERE conditions, columns used to join tables, and sometimes columns used for ORDER BY or GROUP BY.

• WHERE conditions: Index columns used in selective WHERE predicates.
• JOIN columns: Index columns that are used in joins between tables.
• Sorting/Grouping: Consider indexes on columns used in ORDER BY or GROUP BY where appropriate.
• Composite indexes: Use composite (multi-column) indexes when multiple columns are frequently used together in queries.

How to verify and choose

Use the execution plan (for example EXPLAIN) to verify whether the DBMS is using the index and to identify where the real cost occurs. The correct index depends on the actual query pattern; an index that looks reasonable may not be used if it doesn't match how the query is written or if statistics are outdated.

• Execution plan: Run EXPLAIN to see if the index is used and to find hot spots.
• Selectivity: Be aware that an index on a column with very low selectivity may provide little benefit.

Supported operations

Because of the structure above, B+ trees support both fast point lookups and efficient sequential access patterns, making them practical for many database workloads.

• Equality search: Navigate quickly to a key.
• Range search: Find the starting key and scan linked leaves.
• ORDER BY / ordered scans: Keys are maintained in sorted order for efficient ordered retrieval.
• Large datasets: Balanced height keeps search cost predictable as the index grows.

Key properties (concise)

• Data organization: Clustered: Determines table's row/order organization. Non-clustered: Separate index structure.
• Number per table: Clustered: Usually one. Non-clustered: Can be many.
• Leaf level: Clustered: Contains/represents the actual data rows or clustered entries. Non-clustered: Contains row locator / key reference.
• Range scans: Clustered: Often very efficient when range follows clustered key. Non-clustered: Can be efficient but may require additional row lookups.
• Use case: Clustered: Range access and ordered retrieval. Non-clustered: Alternate lookup paths.

How indexes affect write performance

Every write operation can require index maintenance because the index entries must reflect the current table state. The more indexes a table has, the more work each write may require.

• INSERT: New entries may need to be created in every relevant index.
• UPDATE: Changed indexed values may require index entries to be removed and reinserted (or otherwise updated).
• DELETE: When a row is deleted, corresponding index entries must be removed from relevant indexes.

Resource and maintenance costs

Indexes consume storage and memory and increase maintenance effort. These costs matter because index pages compete for cache and disk, and more indexes increase the scope of rebuilds, statistics gathering, and fragmentation management.

• Storage: Each index occupies additional pages/disk space.
• Memory/cache: Frequently used index pages compete for memory.
• Maintenance: Rebuilds, statistics and fragmentation work increase as the number of indexes grows.

Role of the log

During normal transaction processing the DBMS records enough information in a log to describe important changes. Depending on the recovery design, log records may contain before values, after values, or other information needed to repeat or reverse an operation.

After a crash, the database examines these log records and the recorded transaction states to determine the appropriate recovery actions.

• Before values: May be recorded so operations can be reversed (UNDO).
• After values: May be recorded so operations can be repeated (REDO).
• Other information: Any additional metadata needed to repeat or reverse an operation.

Recovery actions: REDO and UNDO

The recovery process uses the log to perform REDO for committed work that might not have been written to durable storage, and UNDO for partial updates from transactions that did not commit before the crash.

• Committed transaction: Its updates may need REDO if the log shows they committed but some modified data pages had not yet been written to durable storage.
• Uncommitted transaction: Its partial updates must be UNDO so incomplete work does not remain in the database.
• Checkpoint information: Helps the DBMS reduce how much of the log must be examined during recovery.

How WAL works (steps)

WAL lets the DBMS defer flushing dirty pages to disk but enforces the ordering that the log record describing a change is made durable first.

• Step 1: Transaction changes a page in memory.
• Step 2: Corresponding log record is written and made durable first.
• Step 3: The data page may be flushed later.
• Step 4: After a crash, the durable log can be used for REDO and/or UNDO as required.