Comprehensive Database Management Systems (DBMS) Study Guide

Database System Concepts & Architecture

  • Data:

    • Characteristics or attributes, often numerical, collected through observation.
    • Can be qualitative (descriptive) or quantitative (numerical).
    • Any facts and figures about an entity constitute data.
    • Plays a crucial role in facilitating analysis, supporting decision-making processes, and driving research activities.

  • Information:

    • Data that has been processed, analyzed, and placed in context, providing a basis for understanding, decision-making, and further analysis.
    • Formally defined as processed data.

  • Database:

    • A structured collection of data stored and accessed electronically from a computer system.
    • Facilitates efficient access, management, and updates.

  • Database Management System (DBMS):

    • Software designed to facilitate efficient data storage, retrieval, and management in databases.
    • Ensures data safety and integrity while offering accessibility and concurrency control.
    • Supports key operational functions like data querying, reporting, and analytics for informed decision-making.

  • Comparison: File System vs Database Management System:   File System vs DBMS Comparison

    • Data Access:
    • File System: Slower data retrieval due to unstructured querying capabilities.
    • DBMS: Structured querying capabilities allow for quicker data access.
    • Data Isolation:
    • File System: Challenges in correlating data across separate files lead to severe data isolation.
    • DBMS: Facilitates data integration, reducing data isolation issues.
    • Data Integrity:
    • File System: High risk of inadvertent data alterations or deletions creating integrity problems.
    • DBMS: Provides robust features and constraints to prevent unauthorized data alterations and maintain integrity.
    • Atomicity Problem:
    • File System: Potential for data inconsistency due to incomplete operations during system crashes.
    • DBMS: Supports transaction properties like atomicity, ensuring operations are either completed fully or not at all.
    • Concurrent Access Anomalies:
    • File System: Conflicts and inconsistencies arise from simultaneous data access/modifications by multiple users.
    • DBMS: Advanced concurrency controls manage simultaneous multi-user access while reducing anomalies.

  • View of Database (Data Abstraction):   View of Database

    • Physical Level (Internal Level):
    • The lowest level of data abstraction.
    • Specifies complex low-level data structures detailing how data is stored and accessed on storage hardware.
    • Predominantly managed by Database Administrators (DBAs).
    • Logical Level (Conceptual Level):
    • The intermediate abstraction level.
    • Describes what data is stored in the database and what relationships exist among those data items.
    • Expresses data in terms of entity sets, attributes, and relationships.
    • View Level (External Level):
    • The highest level of data abstraction.
    • Describes only a specific portion of the overall database that is relevant to a particular user or application.
    • Supports multiple distinct views of the same database for different user groups.

  • Data Independence:

    • The capacity to modify a schema definition at one level of a database system without requiring a alteration of the schema definition at the next higher level.
    • Physical Data Independence:
    • The ability to modify the internal/physical schema without changing the conceptual/logical schema.
    • Necessary to optimize performance (e.g., file reorganization, creating new access paths, modifying indexes).
    • Conceptual schema remains immune to physical storage adjustments.
    • Logical Data Independence:
    • The ability to modify the conceptual schema without altering external schemas or application programs.
    • Immunity of user views and applications to changes in the conceptual structure (e.g., adding or removing entity types or attributes).

  • Instance and Schema:

    • Database Instance:
    • The specific collection of information stored in the database at a particular point in time.
    • Acts as a snapshot of live data showing current state records and active transactions.
    • Database Schema:
    • The overall design and blueprint of the database system.
    • Defines the logical structure, tables, attributes, constraints, and relationships; rarely changes.

  • Comparison: OLAP vs OLTP:

    • Primary Function:
    • OLAP (Online Analytical Processing): Designed for complex data analysis, business intelligence, and reporting.
    • OLTP (Online Transaction Processing): Designed to handle daily operational, transactional data processing.
    • Database Design:
    • OLAP: Employs Star schema or Snowflake schema, optimized for fast read operations.
    • OLTP: Employs highly normalized schemas, optimized for high-volume write operations.
    • Query Complexity:
    • OLAP: Complex analytical queries involving aggregations and multi-dimensional computations.
    • OLTP: Simple and standardized queries focusing on CRUD operations (Create, Read, Update, Delete).
    • Data Volume:
    • OLAP: Deals with massive volumes of historical data.
    • OLTP: Processes a high volume of small, discrete transactions.
    • Response Time:
    • OLAP: Slower response times due to query processing across multi-gigabyte or terabyte datasets.
    • OLTP: Ultra-fast response times (milliseconds) to support high transaction throughput.

  • Specialized Types of Databases:

    • Commercial Database: Handles high volumes of business transactions and customer data (e.g., Salesforce CRM).
    • Multimedia Database: Manages and retrieves complex data types like images, audio, and video files (e.g., Adobe Experience Manager).
    • Deductive Database: Employs logic programming (such as Datalog) to deduce or infer new facts from stored rules and data.
    • Temporal Database: Stores historical data tied to specific time intervals, allowing time-based trend analysis (e.g., stock market historical records).
    • Geographic Information System (GIS): Organizes, analyzes, and visualizes spatial and geographic data (e.g., ArcGIS).

  • Database Administrator (DBA) Functions:

    • Schema Definition: Outlines the initial conceptual database schema using Data Definition Language (DDL).
    • Storage Structure and Access Method Definition: Configures physical layout and index access mechanisms using data storage and definition languages.
    • Schema and Physical Organization Modification: Modifies internal system tables and physical parameters to refine performance.
    • Granting Authorization: Controls security privileges, assigning specific user access rights across database objects.
    • Integrity Constraint Specification: Defines and enforces explicit data constraints to maintain overall data consistency.

  • DBMS Architecture Components:   DBMS Architecture

    • Query Processor:
    • DML Compiler: Translates DML queries into low-level instructions evaluated by the query engine.
    • DDL Interpreter: Processes DDL statements and updates metadata within the data dictionary.
    • Embedded DML Pre-compiler: Converts DML queries embedded in host programming languages into procedural function calls.
    • Query Optimizer: Evaluates multiple execution plans and selects the most efficient path for executing queries.
    • Storage Manager (Database Control System):
    • Authorization Manager: Enforces security policies and verifies access permissions.
    • Integrity Manager: Validates that state modifications fulfill active schema constraints.
    • Transaction Manager: Coordinates transaction execution, ensuring consistency and isolation during concurrent access.
    • File Manager: Allocates disk storage space and manages structural representations on physical media.
    • Buffer Manager: Controls main memory caching and data page transfers between disk and RAM.
    • Disk Storage:
    • Data Files: Physical storage containers holding table records.
    • Data Dictionary: System repository containing structural definitions and metadata regarding database objects.
    • Indices: Auxiliary access structures accelerating data lookup operations.

Entity-Relationship (ER) Modeling

  • Introduction to ER Modeling:

    • Proposed by Dr. Peter Chen in 1976.
    • A conceptual database design tool grounded in real-world entities and relationships, presenting intuitive structural diagrams easily understandable by non-technical stakeholders.

  • Entities and Entity Sets:

    • Entity: An identifiable, real-world object or concept distinguishable from other objects by its attributes.
    • Tangible Entity: Physically exists in the physical world (e.g., Car, Pen, Person).
    • Intangible Entity: Exists conceptually or logically (e.g., Bank Account, Course, Flight Reservation).
    • Representation:
    • In ER diagrams, individual entity instances cannot be represented directly; ER diagrams reflect schemas.
    • In the relational model, an entity instance corresponds to a single row, tuple, or record in a table.
    • Entity Set:
    • A collection of similar entity instances sharing identical attributes and properties.
    • Represented in ER diagrams as a rectangle.
    • Represented in the relational model as a distinct table.

  • Bank and University ER Diagrams:   ER Diagram of a BankER Diagram for University System

  • Attributes and Attribute Categories:

    • Properties or characteristics describing an entity set; each attribute takes values from a permitted domain set.
    • In ER diagrams, attributes are represented by ellipses connected to their entity set rectangle.
    • In relational schemas, attributes become columns.
    • Single-Valued Attribute: Contains a single scalar value per entity instance (e.g., Aadhar Number, Date of Birth).
    • Multivalued Attribute:
    • Can hold multiple distinct values simultaneously for a single entity instance (e.g., Phone Number, Email Address).
    • Represented in ER diagrams by a double ellipse.
    • Transformed into relational schemas by creating a separate table containing the primary key of the primary entity (as a foreign key) combined with the multivalued attribute value.
    • Simple Attribute: Atomic attribute that cannot be broken down further (e.g., Age).
    • Composite Attribute:
    • Subdivided into smaller sub-components representing distinct simple attributes (e.g., Name divided into First_Name and Surname).
    • Represented in ER diagrams as hierarchy branches of ellipses connected to an attribute ellipse.
    • Stored Attribute: Formally stored directly in the database (e.g., Date_of_Birth).
    • Derived Attribute:
    • Value computed on-the-fly from stored attributes (e.g., Age calculated from Date_of_Birth and current date).
    • Represented in ER diagrams by a dashed ellipse.
    • Descriptive Attribute: An attribute attached directly to a relationship diamond rather than an entity set.
    • Null Value: Assigned when an attribute value is unknown, missing, or inapplicable for an entity.

  • Relationships and Relationship Degrees:

    • An association between two or more entity instances.
    • Represented in ER diagrams using a diamond symbol.
    • Degree of Relationship: Specifies the number of participating entity sets.
    • Unary (Self-Referential): A single entity set participates in the relationship with itself (e.g., an Employee supervises another Employee within a Team).
    • Binary: Two entity sets participate; most common relationship type in software design.
    • Ternary: Three entity sets participate simultaneously (e.g., Teacher, Subject, and Course).
    • Quaternary: Four entity sets participate simultaneously (e.g., Buyer, Solicitor, Financial Institution, Bid).
    • N-ary: Arbitrary NN entity sets participating in a single relationship construct.

  • Structural Constraints & Mapping Cardinalities:

    • Defines constraints dictating allowable association counts between entity instances.
    • One-to-One (1:11:1): Each entity instance in set AA associates with at most one entity instance in set BB, and vice versa.
    • One-to-Many (1:M1:M): Each entity instance in set AA associates with zero or more entities in set BB; each entity in set BB connects with at most one entity in set A$.\n - **Many-to-One (M:1)∗∗:Eachentityinset)**: Each entity in setAassociateswithatmostoneentityinsetassociates with at most one entity in setB;eachentityinset; each entity in setBconnectswithzeroormoreentitiesinsetconnects with zero or more entities in setA$.
    • Many-to-Many (M:NM:N): Entities in sets AA and BB connect with arbitrary numbers of entities in the opposite set.
    • Participation Constraints:
    • Total Participation: Every entity instance in the set must participate in at least one relationship instance (drawn as a double line in ER diagrams).
    • Partial Participation: Some entity instances can exist without participating in the relationship set (drawn as a single line).

  • Strong vs Weak Entity Sets:

    • Strong Entity Set: Possesses attributes sufficient to uniquely identify every tuple via its own primary key.
    • Weak Entity Set:
    • Lacks a primary key; relies on an associated identifying (owner) strong entity set for complete identification.
    • Contains a discriminator / partial key (underlined with a dashed line), distinguishing tuples within a specific parent entity.
    • Represented in ER diagrams by a double rectangle.
    • Connects to its owner entity via an identifying relationship, drawn as a double diamond.
    • Participation of a weak entity set in its identifying relationship is always total.
    • The primary key of a weak entity table is formed by combining the owner's primary key with the weak entity's discriminator attribute:
      Primary KeyWeak=Primary KeyOwner∪DiscriminatorWeak\text{Primary Key}_{\text{Weak}} = \text{Primary Key}_{\text{Owner}} \cup \text{Discriminator}_{\text{Weak}}
    • Reasons for Weak Entities: Mirrors dependent structural logic, provides cascading automatic deletion, and prevents redundancy and operational anomalies.

  • Conversion of ER Diagrams to Relational Tables:

    • Entity Sets: Convert each strong or weak entity set into an independent relational table.
    • Relationships:
    • Unary: Add a foreign key column to the entity table referencing its own primary key.
    • 1:11:1: Take the primary key from one entity set and insert it as a foreign key into the opposite entity table (prioritize placing it on the total participation side).
    • 1:M1:M or M:1M:1: Take the primary key from the 11-side table and insert it as a foreign key into the MM-side table.
    • M:NM:N: Create an independent relationship table combining primary keys of both participating entities as a composite primary key.
    • NN-ary (N≥3N \ge 3): Create a separate table whose primary key is composed of the union of primary keys of all participating entity sets.
    • Multivalued Attributes: Create an independent table with the entity's primary key (as a foreign key) combined with the attribute value forming the composite primary key.
    • Composite Attributes: Omit the parent composite attribute; include each individual simple sub-component as an independent column.

  • Enhanced ER (EER) Concepts:

    • Generalization:
    • A bottom-up approach combining multiple lower-level entity sets with shared characteristics into a single higher-level parent entity set.
    • Hides specific differences while abstracting common properties.
    • Specialization:
    • A top-down approach breaking down a higher-level entity set into specialized lower-level entity sets based on distinguishing traits.
    • Reverse of generalization.
    • Aggregation:
    • An abstraction treating a relationship between entity sets as a higher-level pseudo-entity, enabling it to participate in further relationships.

  • Advantages & Disadvantages of ER Modeling:

    • Advantages: Easily transformed into relational tables; intuitive visual structure accessible with minimal training.
    • Disadvantages: Potential loss of detailed information content; limited representation of operational business logic/constraints; becomes overly unwieldy for massive database systems.

Relational Database Management System (RDBMS) & Functional Dependency

  • Relational Model Foundations:

    • Conceptualized by Edgar F. Codd in 1970.
    • Replaced legacy hierarchical and network database architectures with tabular mathematical structures.
    • Domain: A set of atomic, indivisible values of a specific data type from which attribute values are drawn.
    • Relation (Table): A mathematical set of tuples.
    • Tuple (Row / Record): An individual ordered sequence of attribute values within a relation.
    • Arity / Degree: The total count of attributes (columns) defining a relation schema.
    • Cardinality: The total count of tuples (rows) currently residing in a relation instance.

  • Properties of Relational Tables:

    • Every cell must contain strictly atomic (indivisible) values.
    • All values within a specific column must belong to the exact same domain data type.
    • Every tuple within a relation must be distinct; duplicate rows are strictly disallowed in pure set theory.
    • No two tables in a database schema may share identical names.
    • Column names within a table must be unique.
    • Ordering of rows is completely arbitrary and mathematically insignificant.
    • Ordering of columns is completely arbitrary and mathematically insignificant.

  • Relational Database Anomalies:

    • Insertion Anomaly: Inability to insert a piece of data without simultaneously inserting unrelated, mandatory attributes.
    • Modification (Update) Anomaly: Updating a single piece of information requires repetitive updates across multiple duplicated rows, risking system-wide inconsistencies if incomplete.
    • Deletion Anomaly: Unintentionally purging desirable information as a side-effect of deleting an unrelated attribute record.

  • Purpose of Normalization:

    • A systematic table refinement process eliminating Redundancy and Inconsistent Dependencies.
    • Guarantees data integrity, optimizes storage, and prevents operational anomalies during updates.

  • Functional Dependency (FD) Formalism:

    • Formal constraint tool used to evaluate relational schemas.
    • Given a relation schema RR, with attribute sets α⊆R\alpha \subseteq R and \β⊆R\beta \subseteq R, α\alpha functionally determines β\beta (written as α→β\alpha \rightarrow \beta) if and only if for all pairs of tuples t1t_1 and t2t_2 in any legal relation instance r(R)r(R):     If t1[α]=t2[α], then t1[β]=t2[β]\text{If } t_1[\alpha] = t_2[\alpha], \text{ then } t_1[\beta] = t_2[\beta]
    • Trivial Functional Dependency:
    • An FD α→β\alpha \rightarrow \beta is trivial if β⊆α\beta \subseteq \alpha.
    • Trivial dependencies always hold true in any relation instance regardless of data values.

  • Closure of Attribute Sets:

    • The attribute closure of a set of attributes α\alpha under an FD set FF (denoted as α+\alpha^+) is the complete set of attributes functionally determined by α\alpha using F$.\n - *Algorithm for Attribute Closure (\alpha^+)*:\n 1. Initialize \text{result} := \alpha$.
    1. Repeatedly scan every dependency γ→δ\gamma \rightarrow \delta in F$.\n 3. If \gamma \subseteq \text{result},update, update\text{result} := \text{result} \cup \delta$.
    2. Repeat until no additional attributes can be added to result\text{result}.

  • Armstrong's Axioms:

    • A sound and complete set of inference rules published by William W. Armstrong in 1974 for deriving all implied functional dependencies:
    • Reflexivity Rule: If β⊆α\beta \subseteq \alpha, then α→β\alpha \rightarrow \beta
    • Augmentation Rule: If α→β\alpha \rightarrow \beta, then αγ→βγ\alpha \gamma \rightarrow \beta \gamma
    • Transitivity Rule: If α→β\alpha \rightarrow \beta and β→γ\beta \rightarrow \gamma, then α→γ\alpha \rightarrow \gamma
    • Derived Inference Rules:
    • Union: If α→β\alpha \rightarrow \beta and α→γ\alpha \rightarrow \gamma, then α→βγ\alpha \rightarrow \beta \gamma
    • Decomposition: If α→βγ\alpha \rightarrow \beta \gamma, then α→β\alpha \rightarrow \beta and α→γ\alpha \rightarrow \gamma
    • Pseudo-transitivity: If α→β\alpha \rightarrow \beta and γβ→δ\gamma \beta \rightarrow \delta, then αγ→δ\alpha \gamma \rightarrow \delta
    • Composition: If α→β\alpha \rightarrow \beta and γ→δ\gamma \rightarrow \delta, then αγ→βδ\alpha \gamma \rightarrow \beta \delta
    • Soundness & Completeness:
    • Sound: Any dependency derived using these axioms strictly holds in every relation state satisfying F$.\n - *Complete*: Repeated application derives the full closure set F^+ containing all valid implied dependencies.\n\n- **Equivalence of Two FD Sets**:\n - Two FD sets F_1andandF_2areequivalent(are equivalent (F_1 \equiv F_2)ifandonlyiftheirclosuresareidentical() if and only if their closures are identical (F_1^+ = F_2^+).\n - Verified by checking whether F_1 \subseteq F_2^+andandF_2 \subseteq F_1^+ simultaneously.\n\n- **Canonical Cover / Minimal Cover**:\n - A minimal simplified set of functional dependencies F_cequivalenttoequivalent toF without extraneous attributes or redundant dependencies.\n - *Properties of Canonical Cover*:\n 1. The right-hand side of every functional dependency in F_c contains a single attribute.\n 2. No attribute on the left-hand side of any dependency in F_c is extraneous.\n 3. No dependency in F_cisredundant(i.e.,foreveryis redundant (i.e., for everyf \in F_c,,(F_c - {f})^+ eq F_c^+).\n\n- **Keys in the Relational Model**:\n - **Super Key**: Any set of attributes X \subseteq Rwhoseclosuredeterminesallattributesinwhose closure determines all attributes inR((X^+ = R).\n - **Candidate Key**: A minimal super key; a super key for which no proper subset is itself a super key.\n - **Prime Attribute**: An attribute that is a member of at least one candidate key.\n - **Non-Prime Attribute**: An attribute that is not part of any candidate key.\n - **Primary Key**: The specific candidate key chosen by the DBA as the primary identifier for tuples (cannot contain null values; exactly one per table).\n - **Alternate Key**: Any candidate key not selected as the primary key.\n - **Foreign Key**: An attribute or set of attributes in a relation referencing the primary key of another (or the same) relation to establish referential integrity.\n - **Composite Key**: A key consisting of two or more combined attributes.\n - **Secondary Key**: An non-unique attribute indexed to accelerate lookup query speeds.\n\n# Database Normalization\n\n- **Hierarchy of Normal Forms**:\n  ![Hierarchy of Normal Forms](https://assets.knowt.com/pdf-flow-prod/2a6248b4-2f1c-4888-8494-cabadbb7f50e-figures/41.png)\n\n- **First Normal Form (1NF)**:\n - Requires all cell values in a table to be atomic and indivisible.\n - Disallows multivalued attributes and composite attributes.\n - Requires unique column names and a defined primary key to eliminate duplicate rows.\n\n- **Dependency Concepts for Normalization**:\n - **Partial Dependency**: Occurs when a non-prime attribute depends on a proper subset of a candidate key (written as \text{Proper Subset of Key} \rightarrow \text{Non-Prime}).\n - **Full Dependency**: Occurs when a non-prime attribute depends on a complete candidate key and not on any of its proper subsets.\n - **Transitive Dependency**: Occurs when a non-prime attribute functionally determines another non-prime attribute (\text{Non-Prime} \rightarrow \text{Non-Prime}).\n\n- **Second Normal Form (2NF)**:\n - A relation R is in 2NF if:\n 1. It is in 1NF.\n 2. It contains **no partial dependencies** (every non-prime attribute must be fully functionally dependent on every candidate key).\n\n- **Third Normal Form (3NF)**:\n - A relation R is in 3NF if:\n 1. It is in 2NF.\n 2. It contains **no transitive dependencies**.\n - *Direct Definition*: For every non-trivial functional dependency \alpha \rightarrow \betaininR, at least one condition holds:\n - \alphaisasuperkeyofis a super key ofR.\n - \betaisaprimeattributeofis a prime attribute ofR$.

  • Boyce-Codd Normal Form (BCNF):

    • A stricter version of 3NF.
    • Definition: A relation RR is in BCNF if for every non-trivial functional dependency α→β\alpha \rightarrow \beta in RR:
    • α\alpha must be a super key of R$.\n - *Notes*:\n - Any binary relation with exactly two attributes is always in BCNF.\n - If all attributes in a relation are prime attributes, it is automatically in 3NF, but not necessarily in BCNF.\n\n- **Multivalued Dependency (MVD) & Fourth Normal Form (4NF)**:\n - **Multivalued Dependency (\alpha \rightarrow\rightarrow \beta)**:\n - Occurs when the presence of one attribute set \alphadictatesasetofindependentvaluesforanotherattributesetdictates a set of independent values for another attribute set\beta, independent of other attributes.\n - **Trivial MVD**: \alpha \rightarrow\rightarrow \betaistrivialifis trivial if\beta \subseteq \alphaoror\alpha \cup \beta = R$.
    • Fourth Normal Form (4NF):
    • A relation RR is in 4NF if:
      1. It is in BCNF.
      2. For every non-trivial multivalued dependency α→→β\alpha \rightarrow\rightarrow \beta, α\alpha is a super key of R$.\n\n- **Lossless-Join Decomposition**:\n - Decomposing relation Rintosub−relationsinto sub-relationsR_1andandR_2 is **lossless** if performing a natural join yields the exact original relation:\n    R_1 \bowtie R_2 = R\n - If R_1 \bowtie R_2 \supset R, spurious (extra) fake tuples are generated, making the decomposition **lossy**.\n - *Lossless Check Rules for Binary Decomposition (R_1, R_2)*:\n 1. \text{Att}(R_1) \cup \text{Att}(R_2) = \text{Att}(R)\n 2. \text{Att}(R_1) \cap \text{Att}(R_2) eq \emptyset\n 3. The common attribute set must be a candidate key for at least one sub-relation: \n       (\text{Att}(R_1) \cap \text{Att}(R_2) \rightarrow R_1) \quad \lor \quad (\text{Att}(R_1) \cap \text{Att}(R_2) \rightarrow R_2)\n\n- **Dependency Preserving Decomposition**:\n - Decomposition of RintointoR_1, R_2, \dots, R_nwithlocalFDsetswith local FD setsF_1, F_2, \dots, F_n preserves dependencies if:\n    (F_1 \cup F_2 \cup \dots \cup F_n)^+ = F^+\n - Ensures all original functional constraints can be validated locally without computing costly multi-table natural joins.\n\n- **Fifth Normal Form (5NF / Project-Join Normal Form)**:\n - A relation R is in 5NF if:\n 1. It is in 4NF.\n 2. Every join dependency in Risimpliedbythecandidatekeysofis implied by the candidate keys ofR (cannot be further decomposed losslessly without changing candidate keys).\n\n# Database Indexing & Data Structures\n\n- **File Organization Strategies**:\n - **Ordered (Sequential) File Organization**:\n - Records stored sorted by a search key field.\n - Binary search is possible, requiring \mathcal{O}(\log_2 n)diskblockaccesses(wheredisk block accesses (wheren is the total disk block count).\n - High maintenance cost; inserts and deletes require rewriting the entire file structure.\n - **Unordered (Heap) File Organization**:\n - Records added sequentially at the end of the file.\n - Requires linear search across all blocks, taking \mathcal{O}(n) block accesses.\n - Low maintenance overhead for insertions.\n\n- **Database Indexing Concepts**:\n - Auxiliary data structures providing secondary pathways to locate records without altering physical storage locations.\n - Index entries are much smaller than main table records; each index entry contains a key value and a block pointer.\n - Disk block access formula using an index file: \n    \text{Total Accesses} = \log_2(\text{Blocks}_{\text{Index}}) + 1\n\n- **Single-Level Indexing Categories**:\n - **Primary Indexing**:\n - Main file is sorted on the primary key.\n - Index contains primary key values and anchor pointers to block addresses.\n - Example of **Sparse Indexing** (one index entry per disk block of the main file).\n - **Clustered Indexing**:\n - Main file is sorted on a non-key attribute.\n - Index contains one entry per unique value of the ordering attribute.\n - **Secondary Indexing**:\n - Built on unordered fields or non-primary attributes.\n - Example of **Dense Indexing** (one index entry for every record in the main file).\n\n- **Dense vs Sparse Index Comparison**:\n - **Dense Index**: Contains an index entry for every record / search key value in the main data file. Faster search, higher storage overhead.\n - **Sparse Index**: Contains index entries for only some records (usually the first record of each data block, called an anchor record). Consumes less space, but requires scanning within the data block.\n\n- **B-Tree Indexing Structure**:\n - A self-balancing m-way search tree where all leaf nodes reside at the exact same depth level.\n - *Node Structural Capacities for Order m B-Tree*:\n - **Root Node**: Minimum child count = 0,Maximumchildcount=, Maximum child count =m.Minimumkeycount=. Minimum key count =1,Maximumkeycount=, Maximum key count =m - 1$.
    • Internal Nodes: Minimum child count = ⌈m/2⌉\lceil m/2 \rceil, Maximum child count = mm. Minimum key count = ⌈m/2⌉−1\lceil m/2 \rceil - 1, Maximum key count = m - 1$.\n - **Leaf Nodes**: Child count = 0.Minimumkeycount=. Minimum key count =\lceil m/2 \rceil - 1,Maximumkeycount=, Maximum key count =m - 1$.
    • Insertion Mechanics: Inserting into a full node (m−1m - 1 keys) causes a node split; the median key promotes up to the parent node, splitting remaining keys into two sibling nodes.

Relational Query Languages & Relational Algebra

  • Query Language Classifications:   Query Language Hierarchy

    • Procedural Languages:
    • The user specifies both what data is needed and the explicit step-by-step procedure/algorithm to retrieve it.
    • Example: Relational Algebra.
    • Non-Procedural (Declarative) Languages:
    • The user specifies what data is needed without describing the execution steps.
    • Examples: Relational Calculus (TRC, DRC).

  • Relational Algebra Foundations:

    • Mathematical query language where inputs and outputs are relations (tables).
    • Pure set theory basis; duplicate values are automatically eliminated by default.
    • Relational Algebra expression outputs are unnamed relation instances.

  • Fundamental (Basic) Relational Algebra Operators:

    • Project Operator (Vertical Selection - Π\Pi):
    • Selects specific columns from a relation, dropping omitted columns.
    • Unary operator: Πcolumn_list(r)\Pi_{\text{column\_list}}(r).
    • Select Operator (Horizontal Selection - σ\sigma):
    • Selects specific tuples fulfilling a selection predicate condition p$.\n - Unary operator: \sigma_{\text{condition}}(r).\n - Commutative property: \sigma_{p_1}(\sigma_{p_2}(r)) = \sigma_{p_2}(\sigma_{p_1}(r)).\n - **Union Operator (\cup)**:\n - Combines tuples from two relations randands.\n - Binary operator: r \cup s.\n - Requires **Type Compatibility**: randands must have equal arity, and corresponding attribute domains must match.\n - **Set Difference Operator (--)**:\n - Returns tuples present in relation rbutnotinrelationbut not in relations.\n - Binary operator: r - s (requires type compatibility).\n - **Cartesian Product Operator (\times)**:\n - Combines every tuple from relation rwitheverytuplefromrelationwith every tuple from relations$.
    • Binary operator: r \times s$.\n - Result schema arity = \text{Arity}(r) + \text{Arity}(s);tuplecardinality=; tuple cardinality =\text{Cardinality}(r) \times \text{Cardinality}(s).\n - **Rename Operator (\rho)**:\n - Renames an algebra result expression or internal schema: \rho_{X(A_1, A_2, \dots, A_n)}(E).\n\n- **Derived / Additional Operators**:\n - **Set Intersection (\cap)**:\n - Returns tuples present in both randands: \n      r \cap s = r - (r - s)\n - **Natural Join (\bowtie)**:\n - Combines Cartesian product and equality selection across common attributes, dropping duplicated join columns: \n      r \bowtie s = \Pi_{\text{schema}}( \sigma_{r.A = s.A}(r \times s) )\n - **Division Operator (\div)**:\n - Used for queries involving "all" conditions (e.g., students who completed all project tasks).\n\n# Structured Query Language (SQL)\n\n- **Overview & History**:\n - Developed originally by IBM under the name SEQUEL (Structured English Query Language) in the early 1970s.\n - Standardized by ANSI and ISO (SQL-86, SQL-89, SQL-92, SQL:1999, up to SQL:2023).\n - Declarative language incorporating both data definition and data manipulation features.\n\n- **SQL Command Classifications**:\n - **Data Definition Language (DDL)**: `CREATE`, `ALTER`, `DROP`, `TRUNCATE`, `COMMENT`, `RENAME`.\n - **Data Manipulation Language (DML)**: `INSERT`, `UPDATE`, `DELETE`.\n - **Data Control Language (DCL)**: `GRANT`, `REVOKE`.\n - **Data Query Language (DQL)**: `SELECT`.\n - **Transaction Control Language (TCL)**: `COMMIT`, `ROLLBACK`, `SAVEPOINT`.\n\n- **SQL Data Types**:\n - Numeric: `INT`, `SMALLINT`, `BIGINT`, `DECIMAL(p,s)`, `FLOAT`, `REAL`.\n - Character: `VARCHAR(n)` (variable length), `CHAR(n)` (fixed length), `TEXT`.\n - Date/Time: `DATE`, `TIME`, `TIMESTAMP`.\n\n- **DDL & DML Syntax Examples**:\n - *Creating Table*:\n ```sql\n CREATE TABLE Students (\n StudentID INT PRIMARY KEY,\n FirstName VARCHAR(50),\n LastName VARCHAR(50),\n Age INT\n );\n    ```\n - *Adding & Modifying Columns*:\n ```sql\n ALTER TABLE Students ADD PhoneNumber VARCHAR(15);\n ALTER TABLE Students MODIFY COLUMN PhoneNumber VARCHAR(20);\n ALTER TABLE Students DROP COLUMN PhoneNumber;\n    ```\n - *Data Insertion & Deletion*:\n ```sql\n INSERT INTO Students (StudentID, FirstName, LastName, Age) \n VALUES (1, 'Amit', 'Sharma', 20);\n\n DELETE FROM Students WHERE StudentID = 1;\n    ```\n\n- **Basic Query Structure & Clauses**:\n - Standard Query Template:\n ```sql\n SELECT A1, A2, ..., An\n FROM R1, R2, ..., Rm\n WHERE Condition;\n    ```\n - **`SELECT`**: Specifies attributes to project (use `DISTINCT` to eliminate duplicates).\n - **`FROM`**: Specifies relations; multiple tables produce a Cartesian product.\n - **`WHERE`**: Filters rows satisfying logical predicates (`AND`, `OR`, `NOT`, `BETWEEN ... AND ...`).\n\n- **Set Operations in SQL**:\n - `UNION` / `UNION ALL`: Combines query results (eliminates or retains duplicates).\n - `INTERSECT` / `INTERSECT ALL`: Set intersection.\n - `EXCEPT` / `EXCEPT ALL` (or `MINUS`): Set difference.\n\n- **SQL Joins & Outer Joins**:\n - **Inner Join / Natural Join**: Combines matching rows (`NATURAL JOIN`).\n - **Left Outer Join (`LEFT JOIN`)**: Preserves all unmatched tuples from the left relation, padding right attributes with `NULL`.\n - **Right Outer Join (`RIGHT JOIN`)**: Preserves all unmatched tuples from the right relation, padding left attributes with `NULL`.\n - **Full Outer Join (`FULL JOIN`)**: Preserves unmatched tuples from both relations.\n\n- **Aggregate Functions & Grouping**:\n - **Built-in Aggregates**: `COUNT()`, `SUM()`, `AVG()`, `MIN()`, `MAX()`.\n - `COUNT(*)` counts all tuples including nulls; other functions ignore `NULL` values.\n - **`GROUP BY`**: Groups tuples sharing identical values in specified columns to apply aggregate functions per group.\n - **`HAVING`**: Filters groups resulting from `GROUP BY` based on aggregate conditions.\n - **`ORDER BY`**: Sorts output tuples (`ASC` ascending by default, `DESC` descending).\n\n- **Pattern Matching & Advanced SQL**:\n - `LIKE` Operator: Pattern matching using `%` (matches any substring) and `_` (matches any single character).\n - **Triggers**: Stored database procedures automatically executed in response to `INSERT`, `UPDATE`, or `DELETE` events.\n - **Embedded SQL**: SQL statements hardcoded inside host languages (e.g., C, Java) compiled at compile-time.\n - **Dynamic SQL**: Constructing and executing SQL query strings dynamically at runtime.\n\n# Relational Calculus\n\n- **Overview of Relational Calculus**:\n - Non-procedural, declarative query formalism based on predicate logic.\n - Specifies *what* information to obtain rather than *how* to extract it.\n\n- **Tuple Relational Calculus (TRC)**:\n - Formal Syntax:\n    { t \mid P(t) }\n    where tisatuplevariableandis a tuple variable andP(t) is a logical predicate formula.\n - Uses quantifiers \exists(thereexists)and(there exists) and\forall (for all).\n - Example: Find all details of Computer Science students: \n    { t \mid \text{Student}(t) \land t.\text{branch} = \text{'CSE'} }\n\n- **Domain Relational Calculus (DRC)**:\n - Uses domain variables ranging over single field attribute domains rather than entire tuples.\n - Formal Syntax:\n    { \langle x_1, x_2, \dots, x_n \rangle \mid P(x_1, x_2, \dots, x_n) }\n - Example: Find Roll Number of CSE students: \n    { \langle r \rangle \mid \exists n, b \, (\text{Student}(r, n, b) \land b = \text{'CSE'}) }\n\n- **Safety of Expressions & Expressive Power**:\n - An unsafe calculus expression can generate infinite relations (e.g., { t \mid eg(t \in \text{Instructor}) }).\n - When restricted to safe expressions, Tuple Relational Calculus, Domain Relational Calculus, and Basic Relational Algebra are **strictly equivalent in expressive power**.\n\n# Transaction Processing & ACID Properties\n\n- **Transaction Concept**:\n - A transaction is a single logical unit of database processing executing multiple operations.\n - Basic database access primitives:\n - **`READ(X)`**: Loads database item Xfromdiskstorageintoatransactionmemoryvariablenamedfrom disk storage into a transaction memory variable namedX$.
    • WRITE(X): Writes transaction memory variable XX back to physical disk storage.

  • ACID Properties:   ACID Properties

    • Atomicity: All operations of a transaction complete fully or none take effect ("All or Nothing"). Managed by the Recovery Manager.
    • Consistency: Execution of a transaction in isolation preserves database invariants from one consistent state to another. Managed by Application Developers / DBA.
    • Isolation: Executing transactions concurrently yields results identical to executing them serially in isolation. Managed by the Concurrency Control Manager.
    • Durability: Once a transaction commits, its modifications persist permanently even in the event of system failures. Managed by the Recovery Manager.

  • Transaction States:

    • Active: Initial state; transaction is actively executing read/write operations.
    • Partially Committed: Entered after executing the final statement; changes reside temporarily in main memory buffers before writing to disk.
    • Failed: Entered upon discovering that normal execution can no longer proceed due to logical or hardware errors.
    • Aborted: Entered after rolling back changes and restoring the database to its state prior to transaction start.
    • Committed: Entered after successfully flushing all updates to persistent storage.

  • Concurrency & Schedules:

    • Concurrent Execution: Interleaving operations from multiple transactions to maximize throughput and minimize response times.
    • Schedule: An ordered sequence of interleaved operations from a set of concurrent transactions.
    • Serial Schedule: A schedule where operations of each transaction execute completely from start to finish without interleaving with other transactions. Always consistent.
    • Non-Serial Schedule: A schedule where operations of concurrent transactions are interleaved. May cause inconsistencies if not managed properly.

  • Serializability:   Serializability Classification

    • Conflicting Operations: Two operations in a schedule conflict if they belong to different transactions, access the exact same data item, and at least one operation is a WRITE.
    • Conflict Serializability:
    • A schedule SS is conflict serializable if it can be transformed into a serial schedule via a series of swaps of non-conflicting instructions.
    • Precedence Graph Method (Conflict Serializability Test):
    • Construct a directed graph G=(V,E)G = (V, E) where vertices VV are active transactions.
    • Draw an edge Ti→TjT_i \rightarrow T_j if TiT_i executes a conflicting operation before TjT_j on the same data item.
    • Rule: If the precedence graph contains no cycles, the schedule is conflict serializable. If a cycle exists, it is not conflict serializable.
    • View Serializability:
    • A weaker form of serializability checking if a schedule SS is view-equivalent to some serial schedule S′S' based on read-initial, read-from-write, and final-write conditions.

  • Recoverability Classification of Schedules:   Recoverable, Cascadeless, Strict Schedules

    • Non-Recoverable Schedule: Occurs if transaction TjT_j reads a data item written by TiT_i, and TjT_j commits before TiT_i commits or aborts.
    • Recoverable Schedule: Transaction TjT_j reading data written by TiT_i delays its commit until after TiT_i has committed.
    • Cascadeless Schedule: Transaction TjT_j is forbidden from reading uncommitted data written by TiT_i (TiT_i must commit or abort before TjT_j reads the item). Prevents cascading rollbacks.
    • Strict Schedule: Transaction TjT_j can neither read nor write data written by TiT_i until TiT_i officially commits or aborts.

Database Recovery, Distributed Databases, & Concurrency Control

  • Log-Based Recovery Techniques:

    • System logs record all write operations sequentially in stable memory before applying changes to the database.
    • Log Entry Types: ⟨Ti start⟩\langle T_i \text{ start} \rangle, ⟨Ti,Xj,Vold,Vnew⟩\langle T_i, X_j, V_{\text{old}}, V_{\text{new}} \rangle, ⟨Ti commit⟩\langle T_i \text{ commit} \rangle, ⟨Ti abort⟩\langle T_i \text{ abort} \rangle
    • Deferred Database Modification: Updates are batched in log files and deferred from physical database disks until transaction commit.
    • Immediate Database Modification: Updates are written immediately to physical disk storage as they occur; requires both UNDO and REDO log recovery routines.

  • Shadow Paging Recovery:

    • Maintains two distinct page tables during transaction execution: a Current Page Table and a Shadow Page Table.
    • Updates copy modified pages to new physical disk blocks, updating the current page table.
    • Aborting a transaction simply discards the current page table, instantly reverting to the shadow page table.

  • Data Fragmentation & Distributed Databases:

    • Horizontal Fragmentation: Splitting table tuples into subset rows based on filtering conditions.
    • Vertical Fragmentation: Splitting table columns into smaller subsets stored across distinct nodes.
    • Hybrid Fragmentation: Combining horizontal and vertical partitioning.
    • Distributed Database: Storage hardware dispersed across multiple networked physical locations.

  • Concurrency Control Protocols:

    • Timestamp Ordering Protocol:
    • Assigns a unique monotonic timestamp TS(Ti)TS(T_i) when transaction TiT_i enters the system.
    • Tracks W-timestamp(Q)W\text{-timestamp}(Q) and R-timestamp(Q)R\text{-timestamp}(Q) for every data item Q$.\n - Enforces read and write ordering rules based on timestamps; transactions attempting out-of-order access are aborted and restarted.\n - Guarantees Conflict Serializability, View Serializability, and freedom from deadlock, but does not guarantee recoverability or cascadelessness.\n - **Thomas' Write Rule**:\n - A modification of the timestamp ordering protocol.\n - If T_iattemptstowriteattempts to writeQandandTS(T_i) < W\text{-timestamp}(Q),thesystemsimply∗∗ignores/discardstheobsoletewrite∗∗ratherthanaborting, the system simply **ignores/discards the obsolete write** rather than abortingT_i$.
    • Allows greater concurrency and view serializable schedules that are not conflict serializable.

  • Lock-Based Protocols:

    • Enforces mutual exclusion on data items using locks.

    • Shared Lock (SS): Allows concurrent read access; multiple transactions can hold SS locks simultaneously.

    • Exclusive Lock (XX): Provides exclusive read/write access; no other transaction can hold any lock on the item.

    • Lock Compatibility Matrix:     Lock Compatibility Matrix

    • Shared (SS) is compatible only with Shared (SS).

    • Exclusive (XX) is incompatible with both Shared (SS) and Exclusive (XX).

  • Two-Phase Locking (2PL) Variants:

    • Basic 2PL:
    • Requires transactions to operate in two distinct phases:
      1. Growing Phase: Transaction acquires locks; cannot release any lock.
      2. Shrinking Phase: Transaction releases locks; cannot acquire new locks.
    • Guarantees Conflict Serializability and View Serializability, but does not prevent deadlocks or cascading rollbacks.
    • Conservative 2PL:
    • Transaction must acquire all required locks simultaneously before beginning execution.
    • Eliminates deadlocks completely.
    • Rigorous 2PL:
    • Requires all locks (both shared and exclusive) to be held until the transaction explicitly commits.
    • Prevents cascading rollbacks and guarantees cascadeless/strict schedules.
    • Strict 2PL:
    • Requires all exclusive (XX) locks to be held until transaction commit.
    • Guarantees strict, cascadeless, recoverable schedules.

  • Comprehensive Concurrency Protocol Comparison:

    • Timestamp Ordering: Conflict Serializable = YES, View Serializable = YES, Recoverable = NO, Cascadeless = NO, Deadlock Free = YES
    • Thomas Write Rule: Conflict Serializable = NO, View Serializable = YES, Recoverable = NO, Cascadeless = NO, Deadlock Free = YES
    • Basic 2PL: Conflict Serializable = YES, View Serializable = YES, Recoverable = NO, Cascadeless = NO, Deadlock Free = NO
    • Conservative 2PL: Conflict Serializable = YES, View Serializable = YES, Recoverable = NO, Cascadeless = NO, Deadlock Free = YES
    • Rigorous 2PL: Conflict Serializable = YES, View Serializable = YES, Recoverable = YES, Cascadeless = YES, Deadlock Free = NO
    • Strict 2PL: Conflict Serializable = YES, View Serializable = YES, Recoverable = YES, Cascadeless = YES, Deadlock Free = NO

  • Multiple Granularity Locking:   Multiple Granularity Tree

    • Tree-structured hierarchy of lockable units (Database X→X \rightarrow Area A→A \rightarrow File F→F \rightarrow Record RR).
    • Introduces Intent Locks:
    • Intent-Shared (ISIS): Indicates explicit locking at a lower tree level with shared locks.
    • Intent-Exclusive (IXIX): Indicates explicit locking at a lower tree level with exclusive locks.
    • Shared-Intent-Exclusive (SIXSIX): Explicit shared lock on the current node plus explicit exclusive locking at lower levels.

  • Validation-Based Protocols:

    • Optimistic concurrency control technique split into three distinct execution phases:
    1. Read Phase: Reads database values into local temporary transaction variables; performs write operations on local buffers.
    2. Validation Phase: Performs validation tests comparing timestamp histories to ensure serializability invariants are maintained.
    3. Write Phase: Copies temporary local buffer results permanently to physical storage if validation succeeds; aborts transaction if validation fails.