Advanced Database Concepts
Open in the Padhaiko app9.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.
Core Concepts of Object-Oriented Databases (OODBMS)
An Object-Oriented Database Management System (OODBMS) integrates object-oriented programming concepts directly with persistent database capabilities:
- 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).
- Complex & Nested Objects: Attributes can themselves be collections (sets, lists, arrays) or references to other objects without flattening into separate join tables.
- Encapsulation: Objects bundle data (attributes) and behavior (methods) together; external access occurs through public interfaces.
- Class Hierarchies & Inheritance: Subclasses inherit attributes and methods from superclasses and support polymorphism (overriding methods per subclass).
- Persistence: Objects survive after the creating application terminates without manual serialization code.
| Aspect | Relational DBMS (RDBMS) | Object-Oriented DBMS (OODBMS) |
|---|---|---|
| Basic Unit | Relation (flat table of atomic tuples). | Object (attributes + methods + unique OID). |
| Identity | Value-based (PRIMARY KEY attributes). | System-generated immutable OID (pointer-like). |
| Relationships | Foreign keys joined dynamically at query time. | Direct object references / pointer traversal (fast navigation). |
| Query Language | Standardized 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.
- Homogeneous DDBMS: Every site runs identical DBMS software and shares a common schema (easier to manage).
- Heterogeneous DDBMS: Different sites may run different DBMS products (e.g., Oracle at HQ, PostgreSQL at a branch) and schemas, coordinated via middleware/wrappers.
Data Replication and Fragmentation
- 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).
- 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).
- Horizontal Fragmentation (): Splits by rows using selection predicates (e.g.,
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:
- Phase 1 (Prepare / Voting Phase): Coordinator writes
<prepare T>to its log and sendsprepare Tto all sites. Each participant checks if it can commit locally: if yes, it forces its undo/redo logs to disk, writes<ready T>, and repliescommit T(YES); otherwise it writes<no T>and repliesabort T(NO). - Phase 2 (Commit / Decision Phase):
- If all participants replied
YES, coordinator writes<commit T>to stable log and broadcastscommit Tto all participants. - If any participant replied
NO(or timed out), coordinator writes<abort T>and broadcastsabort T. - (Limitation: 2PC is a blocking protocol—if the coordinator crashes after participants reply
YES, participants holding locks must block until the coordinator recovers.)
- If all participants replied
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).
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):
- Subject-Oriented: Organized around major business subjects (Sales, Customers, Products) rather than daily operational applications.
- Integrated: Combines data from heterogeneous sources via ETL (Extract, Transform, Load), resolving naming, unit, and encoding inconsistencies.
- Time-Variant: Stores historical snapshots spanning years (every record carries a time dimension).
- Non-Volatile: Data is loaded in batches and read-only for analysts—never updated or deleted in place during normal queries.
| Aspect | OLTP (Operational Systems) | OLAP (Analytical Systems) |
|---|---|---|
| Purpose | Run day-to-day business transactions (banking, billing, orders). | Strategic analysis, trend forecasting, reporting. |
| Data Profile | Current, detailed, normalized (3NF/BCNF). | Historical, summarized/aggregated, multidimensional (Star/Snowflake). |
| Workload | Short, frequent reads & writes affecting a few rows. | Complex, long-running read-only scans aggregating millions of rows. |
| Performance Metric | Transaction 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):
- Star Schema: Dimension tables are denormalized (each dimension is a single flat table radiating from the central fact table)—fewer joins, faster OLAP queries.
- Snowflake Schema: Dimension tables are normalized into sub-dimensions (e.g.,
ProductCategoryDepartment)—saves dimension storage, requires extra joins.
Five Core OLAP Operations:
- Roll-Up (Drill-Up): Aggregates measures upward along a dimension hierarchy (e.g., daily sales monthly yearly).
- Drill-Down: Navigates downward to finer-grained detail (e.g., yearly quarterly daily).
- Slice: Fixes a single value on one dimension (e.g.,
Year = 2026), reducing cube dimensionality by . - Dice: Selects value ranges on two or more dimensions to extract a subcube.
- 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
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:
- C — Consistency (Linearizability): Every read receives the most recent write or an error.
- A — Availability: Every request to a non-failing node receives a non-error response (without guaranteeing it is the most recent write).
- P — Partition Tolerance: The system continues operating even when network messages between nodes are dropped or delayed.
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:
| NoSQL Type | Data Model | Strengths & Typical Use Cases | Representative Systems |
|---|---|---|---|
| Key-Value Store | Simple (key -> opaque value) hash dictionary. | Ultra-fast lookups; caching, session stores, shopping carts. | Redis, Amazon DynamoDB |
| Document Store | Semi-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 Database | Nodes, 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:
- MapReduce: Splits work into a
Mapstage (processes input chunks independently to emit intermediate(key, value)pairs), aShuffle & Sortstage (groups values by key across nodes), and aReducestage (aggregates values per key). - Apache Spark: Accelerates iterative analytics and machine learning by caching Resilient Distributed Datasets (RDDs) / DataFrames in cluster RAM instead of writing intermediate stages to disk between every MapReduce pass.
Worked Out Examples
9.1
Consider the global relation Employee(EmpID, Name, Branch, Salary) containing tuples:
(101, 'Aarav', 'Kathmandu', 75000)(102, 'Sita', 'Pokhara', 68000)(103, 'Bikash', 'Kathmandu', 82000)(104, 'Nisha', 'Pokhara', 71000)(105, 'Rohan', 'Kathmandu', 90000)
- Design a valid horizontal fragmentation by
Branch(Kathmanduvs.Pokhara) and verify completeness, reconstruction, and disjointness. - Design a valid vertical fragmentation splitting public directory data (
EmpID, Name, Branch) from payroll data (Salary) and show howEmployeeis 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, Branchvs.Salary) are completely disjoint.
- Horizontal fragments: ( tuples) and ( tuples); complete, disjoint, and reconstructed via .
- Vertical fragments: and ; reconstructed losslessly via .
9.2
A retail chain builds a Star Schema data warehouse with:
- Dimension
Store(StoreKey, City, Province)with stores - Dimension
Product(ProdKey, ProdName, Category, Brand)with products - Dimension
Date(DateKey, FullDate, Month, Quarter, Year)covering days ( year) - Central Fact Table
SalesFact(StoreKey, ProdKey, DateKey, UnitsSold, Revenue)where each fact row takes .
- If every store sells every product every day, calculate the maximum number of rows and raw storage size (in MB, using bytes/MB) of
SalesFactfor year. - 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
RevenuealongDate(FullDateMonthYear) and alongStore(StoreKeyProvince). - Slice: Fix
Year = 2026on theDatedimension, producing a(Store, Product)summary slice. - Dice: Filter
Province IN ('Bagmati', 'Gandaki')ANDCategory = 'Electronics'ANDQuarter IN ('Q1', 'Q2'), yielding a smaller subcube across multiple dimensions.
- Maximum fact rows = ; raw storage size = .
- Roll-Up climbs hierarchies (
DayYear); Slice fixes one dimension (Year = 2026); Dice restricts ranges on multiple dimensions simultaneously.
9.3
A distributed transaction updates accounts at Site and Site using Two-Phase Commit (2PC) coordinated by Site .
- Trace the exact 2PC messages and log records if Site replies
YES(commit T) and Site repliesNO(abort T). - 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:
- Phase 1 (Prepare): Coordinator logs
<prepare T>and sendsprepare Tto and .- Site acquires locks, logs
<ready T>+ undo/redo records to disk, and repliesYES. - Site encounters a constraint/lock failure, logs
<no T>, and repliesNO.
- Site acquires locks, logs
- Phase 2 (Decision): Because not all sites voted
YES, Coordinator logs<abort T>and sendsabort Tto 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. ACPsystem 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).
- In Phase 1, logs
<ready T>and votesYESwhile logs<no T>and votesNO. In Phase 2, Coordinator logs<abort T>and instructs both and to abort and undo changes. - During a partition (
P), banking choosesCP(rejecting inconsistent operations), while social feeds/carts chooseAP/ BASE (staying available and converging eventually).
Exercises
Practice Exercises — Advanced Database Concepts
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.
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.
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>) orNO. - Phase 2 (Commit/Abort): Coordinator logs and sends
commit Tonly if all votedYES; otherwise sendsabort T. - Blocking Limitation: Once a participant logs
<ready T>and votesYES, it enters an uncertain state holding locks; if the coordinator crashes before broadcasting Phase 2, participants must block until the coordinator recovers.
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.
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).
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.
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:
- Key-Value Stores (e.g., Redis, DynamoDB): Fast key lookup to opaque values.
- Document Stores (e.g., MongoDB): Flexible JSON/BSON documents with nested fields.
- Column-Family Stores (e.g., Apache Cassandra, HBase): Wide sparse column families optimized for high-velocity writes.
- 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.
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).
- 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 (). - 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).
- Mapper 1 emits:
- Shuffle & Sort Phase (group by key):
"acid";"dbms";"sql".
- Reduce Phase (sum counts):
("acid", 1),("dbms", 2),("sql", 2).
- rows, occupying .
- MapReduce output:
("acid", 1),("dbms", 2),("sql", 2).