PadhaikoAll subjects

Advanced Database Concepts

Database Management System (ENCT 301)

Open in the Padhaiko app

9.1 Concept of object-oriented databases

Traditional relational databases store flat tables of atomic values (INT, VARCHAR, DATE). When applications in CAD/CAM, geographic information systems (GIS), multimedia, or complex engineering simulations manipulate deeply nested objects, converting in-memory object graphs into normalized SQL rows and back introduces severe object-relational impedance mismatch.

Definition

Core Concepts of Object-Oriented Databases (OODBMS)

An Object-Oriented Database Management System (OODBMS) integrates object-oriented programming concepts directly with persistent database capabilities:

  1. Object Identity (OID): Every object receives a unique, immutable, system-generated identifier independent of its attribute values (unlike relational primary keys, which change if a user edits a key column).
  2. Complex & Nested Objects: Attributes can themselves be collections (sets, lists, arrays) or references to other objects without flattening into separate join tables.
  3. Encapsulation: Objects bundle data (attributes) and behavior (methods) together; external access occurs through public interfaces.
  4. Class Hierarchies & Inheritance: Subclasses inherit attributes and methods from superclasses and support polymorphism (overriding methods per subclass).
  5. Persistence: Objects survive after the creating application terminates without manual serialization code.
AspectRelational DBMS (RDBMS)Object-Oriented DBMS (OODBMS)
Basic UnitRelation (flat table of atomic tuples).Object (attributes + methods + unique OID).
IdentityValue-based (PRIMARY KEY attributes).System-generated immutable OID (pointer-like).
RelationshipsForeign keys joined dynamically at query time.Direct object references / pointer traversal (fast navigation).
Query LanguageStandardized declarative SQL.Language-integrated APIs / OQL (less standardized).

(Note: Object-Relational DBMS (ORDBMS) systems such as PostgreSQL and Oracle bridge both worlds by extending SQL tables with user-defined types, arrays, JSON, inheritance, and large-object types.)


9.2 Distributed database model

A Distributed Database (DDB) is a collection of multiple logically interrelated databases distributed across a computer network, managed by a Distributed DBMS (DDBMS) so that distribution is transparent to users.

Data Replication and Fragmentation

  1. Data Replication: Storing copies of a relation at multiple network sites.
    • Advantages: Higher availability (survives site failures) and faster local reads (parallelism).
    • Disadvantages: Increased storage and update propagation overhead (every write must update all replicas consistently).
  2. Data Fragmentation: Splitting a relation into smaller fragments distributed across sites where they are most used:
    • Horizontal Fragmentation (): Splits by rows using selection predicates (e.g., Branch = 'Kathmandu' vs. Branch = 'Pokhara'). Reconstructed via union ().
    • Vertical Fragmentation (): Splits by columns, including the primary key in every fragment so the original relation is losslessly reconstructed via natural join ().
    • Hybrid (Mixed) Fragmentation: Combines horizontal and vertical splits.
    • Correctness Rules: Fragmentation must satisfy Completeness (every tuple/attribute appears in at least one fragment), Reconstruction ( is exactly recoverable), and Disjointness (horizontal fragments do not overlap; vertical fragments overlap only on the primary key).

Distributed Commit: Two-Phase Commit (2PC)

To preserve atomicity when a transaction modifies data across multiple sites, a coordinator executes Two-Phase Commit (2PC) with all participants:

  1. Phase 1 (Prepare / Voting Phase): Coordinator writes <prepare T> to its log and sends prepare T to all sites. Each participant checks if it can commit locally: if yes, it forces its undo/redo logs to disk, writes <ready T>, and replies commit T (YES); otherwise it writes <no T> and replies abort T (NO).
  2. Phase 2 (Commit / Decision Phase):
    • If all participants replied YES, coordinator writes <commit T> to stable log and broadcasts commit T to all participants.
    • If any participant replied NO (or timed out), coordinator writes <abort T> and broadcasts abort T.
    • (Limitation: 2PC is a blocking protocol—if the coordinator crashes after participants reply YES, participants holding locks must block until the coordinator recovers.)

9.3 Concept of data warehousing and online analytical processing

Operational databases (OLTP) handle thousands of short, concurrent transactions (INSERT/UPDATE), whereas management decision-making requires analyzing years of historical data across subjects (OLAP).

Definition

Data Warehouse and Its Four Defining Characteristics

A Data Warehouse is an analytical repository designed to support decision making, characterized by four properties (W. H. Inmon):

  1. Subject-Oriented: Organized around major business subjects (Sales, Customers, Products) rather than daily operational applications.
  2. Integrated: Combines data from heterogeneous sources via ETL (Extract, Transform, Load), resolving naming, unit, and encoding inconsistencies.
  3. Time-Variant: Stores historical snapshots spanning years (every record carries a time dimension).
  4. Non-Volatile: Data is loaded in batches and read-only for analysts—never updated or deleted in place during normal queries.
AspectOLTP (Operational Systems)OLAP (Analytical Systems)
PurposeRun day-to-day business transactions (banking, billing, orders).Strategic analysis, trend forecasting, reporting.
Data ProfileCurrent, detailed, normalized (3NF/BCNF).Historical, summarized/aggregated, multidimensional (Star/Snowflake).
WorkloadShort, frequent reads & writes affecting a few rows.Complex, long-running read-only scans aggregating millions of rows.
Performance MetricTransaction throughput (TPS) and low write latency.Query response time over huge datasets.

Multidimensional Modeling: Star vs. Snowflake Schemas and OLAP Operations

Data warehouses model data as data cubes using a central Fact Table (containing numeric measures like SalesAmount, UnitsSold plus foreign keys) surrounded by descriptive Dimension Tables (Time, Product, Store, Customer):

Five Core OLAP Operations:

  1. Roll-Up (Drill-Up): Aggregates measures upward along a dimension hierarchy (e.g., daily sales monthly yearly).
  2. Drill-Down: Navigates downward to finer-grained detail (e.g., yearly quarterly daily).
  3. Slice: Fixes a single value on one dimension (e.g., Year = 2026), reducing cube dimensionality by .
  4. Dice: Selects value ranges on two or more dimensions to extract a subcube.
  5. Pivot (Rotate): Reorients the cube axes (swapping rows and columns) for cross-tabulated viewing.

9.4 Basic concepts of NoSQL and big data

Web-scale applications generate massive unstructured and semi-structured Big Data characterized by the 5 Vs: Volume (terabytes to petabytes), Velocity (real-time streaming ingestion), Variety (text, JSON, images, logs, graphs), Veracity (data quality/noise), and Value (actionable insight).

CAP Theorem and BASE vs. ACID

Definition

CAP Theorem and BASE Philosophy

Eric Brewer's CAP Theorem proves that a distributed data store can simultaneously guarantee at most two of the following three properties:

Because network partitions (P) are unavoidable in distributed clusters, systems must choose CP (sacrifice availability during a split to preserve strict consistency) or AP (remain available using BASE: Basically Available, Soft state, Eventual consistency).

Four Major Categories of NoSQL Databases

NoSQL ("Not Only SQL") databases trade rigid relational schemas and cross-table joins for horizontal scalability across commodity clusters and flexible data models:

Classification of NoSQL Data Models
NoSQL TypeData ModelStrengths & Typical Use CasesRepresentative Systems
Key-Value StoreSimple (key -> opaque value) hash dictionary.Ultra-fast lookups; caching, session stores, shopping carts.Redis, Amazon DynamoDB
Document StoreSemi-structured self-describing documents (JSON / BSON).Schema flexibility, nested objects stored together; content management, user profiles.MongoDB, CouchDB
Column-Family (Wide-Column)Sparse multi-dimensional map indexed by (RowKey, ColumnFamily:Column, Timestamp).High write throughput & horizontal partitioning; time-series, IoT telemetry, logs.Apache Cassandra, HBase
Graph DatabaseNodes, directed labeled edges, and properties.Index-free adjacency for deep multi-hop traversals; social networks, fraud detection, recommendations.Neo4j, Amazon Neptune

Big Data Processing (MapReduce & Spark)

To process petabyte datasets stored across distributed filesystems (HDFS), frameworks parallelize computation across data nodes:


Worked Out Examples

Example 9.1

9.1

Consider the global relation Employee(EmpID, Name, Branch, Salary) containing tuples:

  1. Design a valid horizontal fragmentation by Branch (Kathmandu vs. Pokhara) and verify completeness, reconstruction, and disjointness.
  2. Design a valid vertical fragmentation splitting public directory data (EmpID, Name, Branch) from payroll data (Salary) and show how Employee is reconstructed.

Horizontal Fragmentation and Verification: Define two fragments using selection predicates:

  • tuples (101, 103, 105).
  • tuples (102, 104).

Check the three correctness rules:

  • Completeness: Every tuple in Employee () belongs to or .
  • Reconstruction: .
  • Disjointness: (no employee belongs to both branches).

Vertical Fragmentation and Lossless Reconstruction:

  • (stored at HR portal).
  • (stored at Payroll server).

Check correctness:

  • Completeness: All attributes appear in .
  • Reconstruction: (lossless because is the primary key).
  • Disjointness: Non-key attributes (Name, Branch vs. Salary) are completely disjoint.
Answer:
  1. Horizontal fragments: ( tuples) and ( tuples); complete, disjoint, and reconstructed via .
  2. Vertical fragments: and ; reconstructed losslessly via .
Example 9.2

9.2

A retail chain builds a Star Schema data warehouse with:

  1. If every store sells every product every day, calculate the maximum number of rows and raw storage size (in MB, using bytes/MB) of SalesFact for year.
  2. Describe how Roll-Up, Slice, and Dice operate on this cube.

Calculating Fact Table Cardinality and Raw Size:

  • Maximum fact rows (dense cube over dimensions):
  • Raw storage size at :

OLAP Operations on SalesFact:

  • Roll-Up: Aggregate daily Revenue along Date (FullDate Month Year) and along Store (StoreKey Province).
  • Slice: Fix Year = 2026 on the Date dimension, producing a (Store, Product) summary slice.
  • Dice: Filter Province IN ('Bagmati', 'Gandaki') AND Category = 'Electronics' AND Quarter IN ('Q1', 'Q2'), yielding a smaller subcube across multiple dimensions.
Answer:
  1. Maximum fact rows = ; raw storage size = .
  2. Roll-Up climbs hierarchies (Day Year); Slice fixes one dimension (Year = 2026); Dice restricts ranges on multiple dimensions simultaneously.
Example 9.3

9.3

A distributed transaction updates accounts at Site and Site using Two-Phase Commit (2PC) coordinated by Site .

  1. Trace the exact 2PC messages and log records if Site replies YES (commit T) and Site replies NO (abort T).
  2. Explain how the CAP Theorem guides choosing between an RDBMS/CP store (banking ledger) and an AP NoSQL store (social-media feed/cart) during a network partition.

Tracing Two-Phase Commit When One Participant Votes NO:

  1. Phase 1 (Prepare): Coordinator logs <prepare T> and sends prepare T to and .
    • Site acquires locks, logs <ready T> + undo/redo records to disk, and replies YES.
    • Site encounters a constraint/lock failure, logs <no T>, and replies NO.
  2. Phase 2 (Decision): Because not all sites voted YES, Coordinator logs <abort T> and sends abort T to both and . Site rolls back its prepared updates using its undo log and releases locks; Site also cleans up and logs <abort T>.

Applying the CAP Theorem During a Network Partition (P):

  • Banking Ledger (CP): During a network partition between branch servers, returning stale balances or permitting conflicting double-spends is unacceptable. A CP system preserves Consistency by rejecting/blocking writes on the minority partition until connectivity heals.
  • Social-Media Feed / Shopping Cart (AP + BASE): Keeping the website responsive is paramount; during a partition, both sides keep accepting reads and writes (Availability) and reconcile replicas asynchronously afterward (Eventual Consistency).
Answer:
  1. In Phase 1, logs <ready T> and votes YES while logs <no T> and votes NO. In Phase 2, Coordinator logs <abort T> and instructs both and to abort and undo changes.
  2. During a partition (P), banking chooses CP (rejecting inconsistent operations), while social feeds/carts choose AP / BASE (staying available and converging eventually).

Exercises

Practice Exercises — Advanced Database Concepts

Question 1

What is object-relational impedance mismatch, and how does an Object-Oriented DBMS (OODBMS) address it? Contrast Object Identity (OID) with a relational primary key.

Impedance Mismatch and OODBMS Features:

  • Impedance mismatch arises because object-oriented programming languages work with complex objects, inheritance, collections, and pointer graphs in memory, whereas relational DBMSs only store flat normalized tables of atomic values—requiring extensive mapping code (ORMs).
  • An OODBMS stores complex nested objects, class hierarchies, inheritance, and encapsulated methods persistently in the database, enabling direct pointer-based object navigation without relational joins.

OID vs. Relational Primary Key:

  • A relational primary key is value-based and user-visible (e.g., RollNo, Email); changing a key value changes the tuple's identity unless cascaded everywhere.
  • An OID is a system-generated, immutable, location-independent identifier tied to the object itself for its entire lifetime, remaining unchanged even if every attribute of the object is modified.
Answer:

Impedance mismatch is the gap between in-memory OO object graphs and flat relational tables; an OODBMS bridges it by natively persisting objects, methods, collections, and inheritance. An OID is immutable and system-generated, whereas a primary key is mutable and value-based.

Question 2

Compare data replication and data fragmentation (horizontal and vertical) in distributed databases, and explain the Two-Phase Commit (2PC) protocol along with its blocking limitation.

Replication vs. Fragmentation:

  • Replication copies the same data across multiple sites to boost read locality and fault tolerance, at the cost of extra storage and write synchronization.
  • Fragmentation partitions a table into subsets placed at relevant sites: horizontal fragmentation splits rows by predicate (, merged by ) and vertical fragmentation splits columns while keeping the primary key in every fragment (, merged by ).

Two-Phase Commit (2PC) and Blocking:

  • Phase 1 (Prepare): Coordinator asks participants to prepare; each flushes logs and replies YES (<ready T>) or NO.
  • Phase 2 (Commit/Abort): Coordinator logs and sends commit T only if all voted YES; otherwise sends abort T.
  • Blocking Limitation: Once a participant logs <ready T> and votes YES, it enters an uncertain state holding locks; if the coordinator crashes before broadcasting Phase 2, participants must block until the coordinator recovers.
Answer:

Replication stores redundant copies for availability/read speed, whereas fragmentation splits tables horizontally (rows) or vertically (columns + PK). 2PC ensures distributed atomicity via Prepare and Decision phases, but blocks if the coordinator crashes after participants vote YES.

Question 3

Define a Data Warehouse using its four core characteristics, distinguish between OLTP and OLAP, and compare the Star Schema and Snowflake Schema for multidimensional data modeling.

Four Properties of a Data Warehouse and OLTP vs. OLAP:

  • A data warehouse is Subject-Oriented, Integrated (via ETL), Time-Variant (historical), and Non-Volatile (read-only after batch loads).
  • OLTP supports high-concurrency, short read/write operational transactions on current normalized data; OLAP runs complex read-only analytical aggregations over years of summarized historical data.

Star Schema vs. Snowflake Schema:

  • Star Schema: Central fact table linked directly to denormalized flat dimension tables (simpler SQL, fewer joins, faster OLAP query execution).
  • Snowflake Schema: Dimension tables are normalized into hierarchical sub-tables (eliminates dimension redundancy and saves space, at the expense of extra joins during queries).
Answer:

A Data Warehouse is subject-oriented, integrated, time-variant, and non-volatile. OLTP targets real-time operational writes on normalized tables, whereas OLAP targets historical read analytics. Star schemas use denormalized dimensions for speed, while Snowflake schemas normalize dimensions to reduce redundancy.

Question 4

List the four primary families of NoSQL databases with an example of each, and explain the CAP Theorem and the BASE model in contrast with relational ACID transactions.

Four NoSQL Database Families:

  1. Key-Value Stores (e.g., Redis, DynamoDB): Fast key lookup to opaque values.
  2. Document Stores (e.g., MongoDB): Flexible JSON/BSON documents with nested fields.
  3. Column-Family Stores (e.g., Apache Cassandra, HBase): Wide sparse column families optimized for high-velocity writes.
  4. Graph Databases (e.g., Neo4j): Nodes and directed edges for relationship-heavy queries.

CAP Theorem and BASE vs. ACID:

  • CAP Theorem: Under a network Partition (P), a distributed store must choose either Consistency (C) or Availability (A).
  • While relational systems emphasize ACID (strict immediate consistency), many distributed NoSQL systems adopt BASE (Basically Available, Soft state, Eventual consistency)—staying available (AP) during partitions and converging replicas asynchronously once the network heals.
Answer:

The four NoSQL families are Key-Value (Redis), Document (MongoDB), Column-Family (Cassandra), and Graph (Neo4j). By the CAP Theorem, during a network partition systems choose CP (consistency) or AP (availability via BASE: Basically Available, Soft state, Eventual consistency).

Question 5
  1. A university analytics warehouse has a GradingFact(TermKey, CourseKey, StudentKey, Marks) table spanning terms, active courses per term, and enrollments per course-term (each row is ). Calculate the total number of fact rows and raw size in MB ().
  2. Trace the MapReduce (key, value) pairs produced for word-count on two input lines: "dbms sql dbms" and "sql acid".

Calculating Fact Table Rows and Storage:

  • Total fact rows rows.
  • Total bytes .

Tracing MapReduce Word Count:

  • Map Phase:
    • Mapper 1 emits: ("dbms", 1), ("sql", 1), ("dbms", 1).
    • Mapper 2 emits: ("sql", 1), ("acid", 1).
  • Shuffle & Sort Phase (group by key):
    • "acid" ; "dbms" ; "sql" .
  • Reduce Phase (sum counts):
    • ("acid", 1), ("dbms", 2), ("sql", 2).
Answer:
  1. rows, occupying .
  2. MapReduce output: ("acid", 1), ("dbms", 2), ("sql", 2).
← Crash Recovery