Comprehensive Study Guide: Data Analytics, Distributed Databases, Query Optimization, and Security

Advanced Data Analytics, Warehousing, and OLAP

  • Data analytics refers broadly to the processing of data to infer patterns, correlations, or models for prediction, which are then used to drive business decisions.

  • Decision-making tasks utilize historical data to predict future outcomes:

    • Low-value, high-volume decisions: Online advertisement systems analyze user profiles and past actions to decide which ad to present, maximizing aggregate return.

    • High-value, long-horizon decisions: Manufacturers and retailers predict future demand months in advance to optimize production and inventory, avoiding monetary losses from unsold inventory or missed sales due to stockouts.

  • Business Intelligence (BI) is used in a broadly similar sense to data analytics.

  • Decision support focuses primarily on reporting and aggregation using SQL queries over large datasets, contrasted with Online Transaction Processing (OLTP) where queries read and update small amounts of data.

Data Warehousing Infrastructure

  • A data warehouse is a repository (or archive) of information gathered from multiple heterogeneous sources, stored under a unified schema at a single physical site, and retained over long time horizons to permit historical analysis.

  • It provides a single uniform interface for decision-support queries while isolating OLTP databases from heavy analytical workloads.

Data-warehouse architecture
  • Issues and architectural decisions in building a data warehouse:

    • Data Gathering Architecture:

    • Source-driven architecture: Data sources transmit new information continually as transaction processing occurs, or periodically (e.g., nightly).

    • Destination-driven architecture: The data warehouse periodically requests new data from the source systems.

    • Freshness requirements: Synchronous replication is expensive, so warehouses often run queries on data replicated asynchronously up to the previous day or hour. Real-time requirements utilize stream processing infrastructures.

    • Schema Integration and Materialized Views: Data sources constructed independently have different schemas and data models. Data in the warehouse is converted into a single integrated schema and acts as a materialized view of the source data.

    • Data Transformation and Cleansing (ETL / ELT):

    • Data Cleansing: Correcting errors, misspelled names, addresses, or incorrect postal codes using reference databases via fuzzy lookup.

    • Deduplication (Merge-Purge): Eliminating duplicate address or customer records from multiple sources.

    • Householding: Grouping records for multiple individuals residing in the same dwelling to send a single mailing.

    • Transformation: Unit of measure conversion, schema mapping via joins, and conditional workflow routing.

    • ETL (Extract, Transform, Load) vs ELT (Extract, Load, Transform): ELT loads raw data directly into warehouses supporting user-defined functions or parallel frameworks (e.g., MapReduce) to perform transformations in parallel.

    • Update Propagation: Propagating updates from sources to the warehouse corresponds to the view-maintenance problem.

    • Data Summarization: Storing pre-aggregated summary data (e.g., total clothing sales by category) rather than complete raw transaction records to manage storage constraints.

Multidimensional Data Models and Warehouse Schemas

  • Multidimensional data is modeled using dimension attributes and measure attributes:

    • Measure attributes: Quantitative numerical values that can be aggregated upon (e.g., unit number, price, quantity).

    • Dimension attributes: Categorical attributes upon which measure attributes are grouped, filtered, and analyzed (e.g., item_id, store_id, customer_id, date).

Star schema for a data warehouse
  • Data Warehouse Schema Types:

    • Fact Table: A central, very large table containing individual event records. Contains measure attributes and dimension attributes (which act as short foreign key identifiers).

    • Dimension Tables: Outlying tables referenced by the fact table's foreign keys containing descriptive attributes (e.g., a store table containing city, state, country).

    • Star Schema: A schema architecture consisting of a single central fact table referencing multiple non-normalized dimension tables.

    • Snowflake Schema: A variant of the star schema where dimension tables are further normalized into multiple levels of sub-dimension tables (e.g., item_info referencing a manufacturer_id in a separate manufacturer table).

Database Engine Support for Warehouses

  • Differences between OLTP and Data Warehouse engines:

    • Data in warehouses is inserted and periodically deleted in bulk, but records are typically never updated post-insertion. Consequently, data warehouses eliminate concurrency control overheads (such as multi-version locking and transaction logging for small updates).

    • Row-Oriented Storage: Attributes of a tuple are stored sequentially in a file. Suitable for OLTP where individual records are read/written.

    • Column-Oriented Storage: Each attribute of a relation is stored in a separate file, with values from successive tuples placed at contiguous offsets. For a fixed-size attribute AA, the ii-th tuple value is located at offset (i−1)×size(A)(i - 1) \times \text{size}(A).

    • Benefits: Drastically reduces disk I/O by loading only columns referenced in the query; yields significantly higher data compression ratios because identical data types are stored contiguously.

    • Drawbacks: High I/O overhead for inserting or retrieving single complete tuples.

    • Systems utilizing columnar storage: Pure warehouse engines include Teradata, Sybase IQ, and Amazon Redshift. Traditional engines adding columnar options include Oracle, SAP HANA, Microsoft SQL Server, and IBM DB2.

    • Big Data Systems: Query engines over file stores such as Apache Hadoop (with Apache Hive for SQL execution, optimized by Cloudera and Hortonworks), Apache Spark, using compressed columnar file formats such as Orc and Parquet.

  • Data Lakes: Repositories that store raw data in multiple structured, semi-structured, or unstructured file formats without enforcing an up-front common schema (schema-on-read). Requires flexible querying engines such as Apache Hadoop and Apache Spark.

Online Analytical Processing (OLAP)

  • An Online Analytical Processing (OLAP) system allows analysts to interactively analyze multidimensional data across various aggregations and granularities in near real-time.

An example of sales relation
  • Cross-Tabulation (Cross-tab / Pivot Table):

    • Derived two-dimensional grid where distinct values of one attribute form column headers and distinct values of another form row headers.

    • Intersecting cells contain aggregated measure values (e.g., total sales quantity for a specific item_name and color).

Cross-tabulation of sales by item_name and color
  • Data Cube:

    • Generalization of a 2D cross-tab to nn dimensions.

    • Each cell is defined by a tuple of dimension values and contains the corresponding aggregated measure.

    • Dimensions can take the special value all, representing an aggregated summary across that entire dimension.

    • For nn dimensions, there are 2n2^n possible grouping combinations. For a data cube with 3 colors, 4 items, and 3 sizes, the base cube has 3×4×3=363 \times 4 \times 3 = 36 cells. Including summary values (all), the cube size expands to 4×5×4=804 \times 5 \times 4 = 80 cells.

Three-dimensional data cube
  • Core OLAP Operations:

    • Pivoting: Rotating the data axes to display a different pair of dimensions in a 2D cross-tab.

    • Slicing: Filtering the data cube by fixing a single dimension attribute to a specific value (e.g., clothes_size = 'large').

    • Dicing: Selecting a sub-cube by fixing specific values across multiple dimensions.

    • Rollup: Aggregating data from a finer level of granularity to a coarser level of detail.

    • Drill down: Moving from coarse, aggregated summaries to detailed, fine-grained data.

    • Dimension Hierarchies: Structuring attributes into multi-level paths (e.g., time hierarchy: datetime →\rightarrow date / hour_of_day →\rightarrow day_of_week / month →\rightarrow quarter →\rightarrow year; location hierarchy: city →\rightarrow state →\rightarrow country →\rightarrow region).

  • OLAP Implementations:

    • MOLAP (Multidimensional OLAP): Stores data cubes directly in array-based memory structures.

    • ROLAP (Relational OLAP): Uses relational databases to store base data and precomputed summary tables.

    • HOLAP (Hybrid OLAP): Stores high-level summaries in memory (MOLAP) and detailed base data in relational tables (ROLAP).

OLAP Extensions in SQL

  • SQL PIVOT Clause:

select *
from sales
pivot (
    sum(quantity)
    for color in ('dark', 'pastel', 'white')
)
order by item_name;
  • SQL Aggregation Syntax for Data Cubes:

    • GROUP BY CUBE(item_name, color, clothes_size): Generates all 23=82^3 = 8 grouping set combinations, inserting null for attributes omitted from a given grouping.

    • GROUP BY ROLLUP(item_name, color, clothes_size): Generates a hierarchical sequence of 4 groupings based on attribute ordering: {(item_name, color, clothes_size), (item_name, color), (item_name), ()}.

    • Composite Rollups: GROUP BY ROLLUP(item_name), ROLLUP(color, clothes_size) computes the Cartesian product of the grouping sets, yielding 2×3=62 \times 3 = 6 distinct groupings.

    • GROUP BY GROUPING SETS ((color, clothes_size), (clothes_size, item_name)): Explicitly lists the exact groupings to execute.

    • GROUPING() Function: Returns 1 if a null value in an attribute is generated by an OLAP CUBE/ROLLUP operation, and 0 for regular database nulls. Used in CASE statements to replace OLAP nulls with the string 'all'.

  • Specialized Query Languages: MDX (MultiDimensional eXpressions) and DAX (Data Analysis Expressions).

Reporting, Visualization, and Data Mining

  • Reporting & Dashboards: Tools like SAP Crystal Reports, Microsoft SSRS, Tableau, FusionCharts, Plotly, Datawrapper, and Google Charts generate human-readable reports and dynamic web dashboards.

  • Data Mining (Knowledge Discovery in Databases - KDD):

    • Process of semi-automatically extracting non-trivial, implicit, previously unknown, and potentially useful patterns, models, or rules from large disk-resident datasets.

  • Predictive Analytics Techniques:

    • Classification: Assigning items to discrete target classes based on a labeled set of training instances.

    • Decision-Tree Classifiers: Tree structures where internal nodes contain split predicates and leaf nodes contain class labels.

    • Bayesian Classifiers: Probabilistic classifiers applying Bayes' Theorem:       p(ci∣d)=p(d∣ci)p(ci)p(d)p(c_i|d) = \frac{p(d|c_i)p(c_i)}{p(d)}       Naive Bayesian Classifiers assume attribute independence conditional on the class:       p(d∣ci)=∏k=1np(dk∣ci)p(d|c_i) = \prod_{k=1}^n p(d_k|c_i)

    • Support Vector Machines (SVM): Geometric algorithms finding the maximum-margin hyperplane separating binary classes in multi-dimensional vector spaces. Uses kernel functions for non-linear decision boundaries.

    • Neural Networks and Deep Learning: Multi-layer network of artificial neurons using backpropagation to tune weights. Deep neural networks excel in vision, speech recognition, and natural language processing.

    • Regression: Predicting continuous numeric target variables YY from input variables X1,…,XnX_1, \dots, X_n via curve-fitting (e.g., Linear Regression: Y=a0+a1X1+a2X2+⋯+anXnY = a_0 + a_1 X_1 + a_2 X_2 + \dots + a_n X_n).

    • Association Rules: Uncovering co-occurrence patterns in transactional itemsets (e.g., bread→milk\text{bread} \rightarrow \text{milk}).

    • Support: Fraction of total transactions containing both antecedent and consequent.

    • Confidence: Conditional probability that a transaction contains the consequent given that it contains the antecedent.

    • Clustering: Unsupervised grouping of objects into clusters based on distance metrics to minimize intra-cluster distance relative to cluster centroids. Applications include biological taxonomy and collaborative filtering.

    • Text Mining: Analyzing textual documents via sentiment analysis (classifying text polarities), information extraction, named entity recognition, entity disambiguation, and constructing knowledge graphs.

Distributed Database Concepts and Architectures

  • A Distributed Database (DDB) is a collection of multiple logically interrelated databases distributed over a computer network.

  • A Distributed Database Management System (DDBMS) is the software system that manages the DDB while rendering the distribution transparent to users.

Core Characteristics and Transparencies

  • Conditions defining a DDB:

    • Database sites/nodes are interconnected via a local area network (LAN) or wide area network (WAN).

    • Stored data across nodes is logically interrelated.

    • System nodes can be heterogeneous in hardware, operating systems, and local DBMS software.

  • Transparency Dimensions:

    • Distribution / Network Transparency: Users are insulated from operational network details and physical storage placement.

    • Location Transparency: Commands are executed identically regardless of the physical location of the data or the node issuing the query.

    • Naming Transparency: Data objects are referenced by global names without requiring site qualifiers.

    • Replication Transparency: Users are unaware that multiple copies (replicas) of data exist across nodes.

    • Fragmentation Transparency: Users execute queries against global relations without knowledge of horizontal or vertical partitioning.

    • Design and Execution Transparency: Insulation from how the DDB is partitioned and where specific transaction sub-operations execute.

  • Reliability, Availability, Scalability, and Autonomy:

    • Reliability: Probability that a system is operational at a given time.

    • Availability: Probability that the system is continuously available during a time interval.

    • Scalability:

    • Horizontal Scalability: Adding more processing nodes to the network.

    • Vertical Scalability: Upgrading hardware capacity (CPU, memory, storage) of individual nodes.

    • Partition Tolerance: System capacity to remain operational despite network partitions that disrupt communication between node subsets.

    • Autonomy Levels:

    • Design Autonomy: Freedom of local nodes to choose data models, schemas, and transaction algorithms.

    • Communication Autonomy: Node independence in deciding what data and messages to share.

    • Execution Autonomy: Node independence in scheduling and executing local transactions.

Data Fragmentation, Replication, and Allocation

  • Data Fragmentation Methods:

    • Horizontal Fragmentation (Sharding): Dividing a relation RR into disjoint subsets of rows (tuples) using selection predicates σC(R)\sigma_C(R).

    • Complete Horizontal Fragmentation: Selection conditions C1,C2,…,CnC_1, C_2, \dots, C_n satisfy (C1∨C2∨⋯∨Cn)=TRUE(C_1 \vee C_2 \vee \dots \vee C_n) = \text{TRUE}. Reconstruction requires the UNION operation (⋃i=1nσCi(R)\bigcup_{i=1}^n \sigma_{C_i}(R)).

    • Disjointness: No tuple satisfies (Ci∧Cj)(C_i \wedge C_j) for any i≠ji \neq j

    • Derived Horizontal Fragmentation: Partitioning a secondary relation based on the horizontal predicate of a primary relation linked via foreign keys.

    • Vertical Fragmentation: Partitioning attributes of a relation RR into subsets using projection πL(R)\pi_L(R).

    • Complete Vertical Fragmentation: Attribute lists L1,L2,…,LnL_1, L_2, \dots, L_n must satisfy ⋃Li=ATTRS(R)\bigcup L_i = \text{ATTRS}(R) and ⋂Li=PK(R)\bigcap L_i = \text{PK}(R). Preserving the primary key PK(R)\text{PK}(R) in every fragment is mandatory for reconstruction via FULL OUTER JOIN or OUTER UNION.

    • Mixed (Hybrid) Fragmentation: Combining selection and projection πL(σC(R))\pi_L(\sigma_C(R)) to produce matrix sub-blocks.

  • Allocation Schemas and Replication:

    • Nonredundant Allocation: Each fragment is allocated to exactly one site.

    • Fully Replicated: The entire database is duplicated at every site, maximizing read performance and availability while increasing write synchronization overhead.

    • Partial Replication: Specific fragments are replicated across a subset of sites based on access frequency and transaction workloads.

Data distribution and replication among distributed databases

Distributed Concurrency Control and Recovery

  • Concurrency Control with Replicated Data:

    • Primary Site Technique: A single centralized primary site manages all lock requests. Simple, but creates a single point of failure and bottleneck.

    • Primary Site with Backup Site: A backup site mirrors lock tables; takes over if the primary fails.

    • Primary Copy Method: Coordinator sites for locking are distributed across different nodes depending on the data item.

    • Election Algorithms: Nodes vote to select a new coordinator if the primary coordinator fails.

    • Voting Method: True distributed locking where a lock request is sent to all sites holding a replica; a lock is granted if a majority of sites vote to grant it.

  • Commit Protocols:

    • Two-Phase Commit (2PC): Phase 1 (Prepare phase: coordinator asks participants to vote to prepare), Phase 2 (Commit/Abort phase). Problem: 2PC is a blocking protocol if the coordinator crashes after participants vote 'yes'.

    • Three-Phase Commit (3PC): Non-blocking protocol that inserts a prepare-to-commit state between the prepare and commit phases, establishing maximum wait timeouts.

Distributed Query Processing and Semijoins

  • Query Processing Stages:

    1. Query Mapping: Translating a global query into relational algebra over global relations.

    2. Localization: Mapping global algebraic expressions to localized queries over specific fragments using catalog guard conditions.

    3. Global Query Optimization: Choosing execution plans minimizing combined CPU, I/O, and data communication costs across the network.

    4. Local Query Optimization: Optimizing single-site execution plans at local nodes.

  • Data Transfer Cost Optimization:

    • Example Workload Metrics: Relation EMPLOYEE at Site 1 (10,000 records, 100 bytes/rec, total size 10610^6 bytes). Relation DEPARTMENT at Site 2 (100 records, 35 bytes/rec, total size 3,500 bytes). Result required at Site 3.

    • Strategy 1: Move EMPLOYEE (10610^6 bytes) and DEPARTMENT (3,500 bytes) to Site 3. Total transfer = 1,003,500 bytes.

    • Strategy 2: Move EMPLOYEE to Site 2, perform join (10,000 result records at 40 bytes/rec = 400,000 bytes), move result to Site 3. Total transfer = 1,400,000 bytes.

    • Strategy 3: Move DEPARTMENT to Site 1, perform join, send 400,000 bytes to Site 3. Total transfer = 403,500 bytes.

    • Semijoin Operation (R⋉A=BSR \ltimes_{A=B} S):

    • Defined as R⋉A=BS=πR(R⋈A=BS)=R⋈A=B(πB(S))R \ltimes_{A=B} S = \pi_R(R \bowtie_{A=B} S) = R \bowtie_{A=B} (\pi_B(S)).

    • Algorithm: Project join attribute BB from SS at Site 2 (πB(S)\pi_B(S)), transfer the small projection to Site 1, join with RR at Site 1, project required attributes, and ship filtered tuples back to Site 2 or 3.

    • Reduces network volume when only a small fraction of tuples in RR match join conditions in SS. Note: Semijoin is non-commutative (R⋉S≠S⋉RR \ltimes S \neq S \ltimes R).

System Architectures and Classification

Some different database system architectures
  • Multiprocessor Systems vs DDBMS:

    • Shared-Memory (Tightly Coupled): Processors share primary memory and disks.

    • Shared-Disk (Loosely Coupled): Processors have local primary memory but share common disks.

    • Shared-Nothing: Processors possess independent primary memory and disks, communicating over a high-speed bus/switch. Used in parallel databases.

  • Federated Database Systems (FDBS):

    • Heterogeneous, autonomous component databases operating independently.

    • Semantic Heterogeneity: Discrepancies in data models, constraints, query languages, and domain interpretations.

The five-level schema architecture in a federated database system
  • Five-Level Schema Architecture in FDBS:

    1. Local Schema: Conceptual schema of local component DBMS.

    2. Component Schema: Local schema translated into a canonical Common Data Model (CDM).

    3. Export Schema: Shareable subset of component schema made accessible to the federation.

    4. Federated Schema: Integrated global schema combining all export schemas.

    5. External Schema: Application-specific views defined over the federated schema.

The three-tier client/server architecture
  • Three-Tier Client/Server Architecture:

    • Presentation Tier (Client): Web browsers processing HTML, JavaScript, CSS.

    • Application Tier (Business Logic): Application servers running Java, C++, C# formulating queries and verifying business logic.

    • Database Server Tier: RDBMS processing SQL queries and managing data persistence.

  • Distributed Catalog Management:

    • Centralized Catalog: Stored at a single site; easy to implement but creates a bottleneck and failure point.

    • Fully Replicated Catalog: Identical copies at all sites; maximizes read performance but requires 2PC for all catalog updates.

    • Partitioned / Partially Replicated Catalog: Each site maintains catalog entries for locally stored data and caches remote metadata.

Query Optimization

  • Query optimization is the process of choosing an efficient query-evaluation plan from multiple logically equivalent execution strategies to minimize evaluation cost (evaluation time, disk I/O, CPU time).

Relational Expression Transformations and Equivalence Rules

  • Two relational algebra expressions are equivalent if, on every legal database instance, they evaluate to the same set (or multiset) of tuples.

Equivalent expressionsAn evaluation plan
  • Fundamental Equivalence Rules:

    1. Cascade of σ\sigma (Deconstructing Conjunctive Selections):      σθ1∧θ2(E)=σθ1(σθ2(E))\sigma_{\theta_1 \wedge \theta_2}(E) = \sigma_{\theta_1}(\sigma_{\theta_2}(E))

    2. Commutativity of σ\sigma:      σθ1(σθ2(E))=σθ2(σθ1(E))\sigma_{\theta_1}(\sigma_{\theta_2}(E)) = \sigma_{\theta_2}(\sigma_{\theta_1}(E))

    3. Cascade of Π\Pi (Combining Projections):      ΠL1(ΠL2(…(ΠLn(E))… ))=ΠL1(E)where L1⊆L2⋯⊆Ln\Pi_{L_1}(\Pi_{L_2}(\dots (\Pi_{L_n}(E))\dots)) = \Pi_{L_1}(E) \quad \text{where } L_1 \subseteq L_2 \dots \subseteq L_n

    4. Selections with Cartesian Products and Theta Joins:      σθ(E1×E2)=E1⋈θE2\sigma_\theta(E_1 \times E_2) = E_1 \bowtie_\theta E_2      σθ1(E1⋈θ2E2)=E1⋈θ1∧θ2E2\sigma_{\theta_1}(E_1 \bowtie_{\theta_2} E_2) = E_1 \bowtie_{\theta_1 \wedge \theta_2} E_2

    5. Commutativity of Theta Joins and Natural Joins:      E1⋈θE2=E2⋈θE1E_1 \bowtie_\theta E_2 = E_2 \bowtie_\theta E_1

    6. Associativity of Joins and Cartesian Products:      (E1⋈E2)⋈E3=E1⋈(E2⋈E3)(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)      (E1⋈θ1E2)⋈θ2∧θ3E3=E1⋈θ1∧θ3(E2⋈θ2E3)where θ2 involves attributes from E2 and E3(E_1 \bowtie_{\theta_1} E_2) \bowtie_{\theta_2 \wedge \theta_3} E_3 = E_1 \bowtie_{\theta_1 \wedge \theta_3} (E_2 \bowtie_{\theta_2} E_3) \quad \text{where } \theta_2 \text{ involves attributes from } E_2 \text{ and } E_3

    7. Distribution of Selection over Theta Join:

    • When θ1\theta_1 involves only attributes of E1E_1:        σθ1(E1⋈θE2)=(σθ1(E1))⋈θE2\sigma_{\theta_1}(E_1 \bowtie_\theta E_2) = (\sigma_{\theta_1}(E_1)) \bowtie_\theta E_2

    • When θ1\theta_1 involves only attributes of E1E_1 and θ2\theta_2 involves only attributes of E2E_2:        σθ1∧θ2(E1⋈θE2)=(σθ1(E1))⋈θ(σθ2(E2))\sigma_{\theta_1 \wedge \theta_2}(E_1 \bowtie_\theta E_2) = (\sigma_{\theta_1}(E_1)) \bowtie_\theta (\sigma_{\theta_2}(E_2))

    1. Distribution of Projection over Theta Join:

    • When join condition θ\theta involves attributes in L1∪L2L_1 \cup L_2:        ΠL1∪L2(E1⋈θE2)=(ΠL1(E1))⋈θ(ΠL2(E2))\Pi_{L_1 \cup L_2}(E_1 \bowtie_\theta E_2) = (\Pi_{L_1}(E_1)) \bowtie_\theta (\Pi_{L_2}(E_2))

    • With join attributes L3L_3 (from E1E_1) and L4L_4 (from E2E_2) not in L1,L2L_1, L_2:        ΠL1∪L2(E1⋈θE2)=ΠL1∪L2((ΠL1∪L3(E1))⋈θ(ΠL2∪L4(E2)))\Pi_{L_1 \cup L_2}(E_1 \bowtie_\theta E_2) = \Pi_{L_1 \cup L_2}((\Pi_{L_1 \cup L_3}(E_1)) \bowtie_\theta (\Pi_{L_2 \cup L_4}(E_2)))

    1. Commutativity of Set Union and Intersection: E1∪E2=E2∪E1E_1 \cup E_2 = E_2 \cup E_1 and E1∩E2=E2∩E1E_1 \cap E_2 = E_2 \cap E_1 (Set difference is NOT commutative).

    2. Associativity of Set Union and Intersection.

    3. Distribution of Selection over Union, Intersection, and Set Difference:       σθ(E1∪E2)=σθ(E1)∪σθ(E2)\sigma_\theta(E_1 \cup E_2) = \sigma_\theta(E_1) \cup \sigma_\theta(E_2)       σθ(E1∩E2)=σθ(E1)∩σθ(E2)\sigma_\theta(E_1 \cap E_2) = \sigma_\theta(E_1) \cap \sigma_\theta(E_2)       σθ(E1−E2)=σθ(E1)−σθ(E2)\sigma_\theta(E_1 - E_2) = \sigma_\theta(E_1) - \sigma_\theta(E_2)

    4. Distribution of Projection over Union: ΠL(E1∪E2)=(ΠL(E1))∪(ΠL(E2))\Pi_L(E_1 \cup E_2) = (\Pi_L(E_1)) \cup (\Pi_L(E_2)).

    5. Distribution of Selection over Aggregation: σθ(GγA(E))=GγA(σθ(E))\sigma_\theta({}_G\gamma_A(E)) = {}_G\gamma_A(\sigma_\theta(E)) if θ\theta involves only group-by attributes GG

    6. Commutativity of Full Outer Join (E_1 \fullouterjoin E_2 = E_2 \fullouterjoin E_1); exchange of left/right outer joins (E_1 \leftouterjoin E_2 = E_2 \rightouterjoin E_1).

    7. Selection Distribution over Outer Joins: \sigma_{\theta_1}(E_1 \leftouterjoin_\theta E_2) = (\sigma_{\theta_1}(E_1)) \leftouterjoin_\theta E_2 if θ1\theta_1 involves only E1E_1

    8. Outer Join Replacement by Inner Join: If θ1\theta_1 is null-rejecting on E2E_2 (evaluates to false or unknown on nulls), then \sigma_{\theta_1}(E_1 \leftouterjoin_\theta E_2) = \sigma_{\theta_1}(E_1 \bowtie_\theta E_2).

Important Non-Equivalences

  • Selection Pushing over Outer Joins is invalid in general: \sigma_{\text{year}=2017}(\text{instructor} \leftouterjoin \text{teaches}) \neq \text{instructor} \leftouterjoin \sigma_{\text{year}=2017}(\text{teaches}) because pushing the selection down retains instructors who taught zero courses in 2017 (producing nulls), whereas evaluating selection after outer join eliminates them.

  • Non-associativity of Outer Joins: Let r(A,B)={(1,1)}r(A,B) = \{(1,1)\}, s(B,C)={(1,1)}s(B,C) = \{(1,1)\}, and t(A,C)=∅t(A,C) = \emptyset. Then (r \leftouterjoin s) \leftouterjoin t produces \tuple{1,1,1}, whereas r \leftouterjoin (s \leftouterjoin t) produces \tuple{1,1,\text{null}}.

Cost-Based Optimization and Plan Enumeration

  • Enumeration Procedure (genAllEquivalent(E)): Repeatedly matches subexpressions against a minimal set of equivalence rules to generate new candidate relational expressions until no further expressions can be derived.

  • Space and Time Optimizations:

    • Subexpression Sharing: Representing plan alternatives as Directed Acyclic Graphs (DAGs) where equivalent sub-trees share memory locations.

    • Dynamic Programming: Costing sub-plans bottom-up and pruning sub-plans that are strictly more expensive than alternative plans producing identical output properties (e.g., interesting sort orders).

    • Join Ordering Heuristics: Restricting search spaces to left-deep join trees (((…(r1⋈r2)⋈r3)⋯⋈rn)((\dots (r_1 \bowtie r_2) \bowtie r_3) \dots \bowtie r_n)) to enable pipelining.

  • Inspection Commands for Query Plans: EXPLAIN <query> (PostgreSQL, MySQL), EXPLAIN PLAN FOR (Oracle, displaying via dbms_xplan.display), db2exfmt (DB2), SET SHOWPLAN_TEXT ON (SQL Server).

Database Security, Privacy, and Protection

  • Database security addresses legal, ethical, policy, and system-level enforcement mechanisms to guarantee three fundamental goals:

    • Integrity: Guarding against unauthorized or improper data creation, modification, or deletion.

    • Availability: Ensuring timely, uninterrupted access to database objects for authorized subjects.

    • Confidentiality: Protecting sensitive data from unauthorized disclosure.

  • System Security Environment: Database security is dependent on surrounding system layers (application logic, web servers, network firewalls, SSL terminators, OS security).

DBA Responsibilities and Database Auditing

  • Database Administrator (DBA): Central administrative authority possessing a privileged DBA account (system/superuser/root account).

  • Core DBA Privileged Actions:

    1. Account Creation: Provisioning account identifiers and passwords.

    2. Privilege Granting: Assigning discretionary or mandatory access permissions.

    3. Privilege Revocation: Removing access permissions.

    4. Security Level Assignment: Assigning clearance classifications to user accounts.

  • Database Audits & Audit Trails: Expanding the system recovery log to log user account IDs, client IP/device IDs, timestamps, and exact operations for every session statement. Reviewing audit logs (audit trails) allows DBAs to trace unauthorized tampering.

Sensitivity, Disclosures, and Precision

  • Data Sensitivity Factors:

    1. Inherently sensitive (e.g., salary, HIV status).

    2. Sensitive source (e.g., identity of an informer).

    3. Explicitly declared sensitive by the data owner.

    4. Sensitive attribute or record (e.g., Salary attribute in EMPLOYEE).

    5. Sensitive in relation to previously disclosed data (e.g., combining non-sensitive GPS coordinates with secret event records).

  • Evaluation Criteria for Data Access: Data availability (concurrency locking), Access acceptability (denying access if queries implicitly expose sensitive data), Authenticity assurance (verifying external factors like time of day).

  • Security vs. Precision Tradeoff:

    • Security: Ensuring data is safe from corruption and unauthorized disclosure by rejecting any query referencing sensitive data.

    • Precision: Disclosing as much non-sensitive data as possible while protecting all sensitive data.

    • Tradeoff: Absolute security requires sacrificing precision (withholding partial non-sensitive data to eliminate inference channels).

  • Security vs. Privacy: Security refers to technical access protection mechanisms. Privacy examines whether personal information processing conforms to user agreements, enabling individuals to control the terms of personal data collection and use.

Discretionary Access Control (DAC)

  • Enforces access rights based on user identity and explicit privilege grants.

  • Privileges in SQL:

    • Account Level: System-wide capabilities (CREATE SCHEMA, CREATE TABLE, CREATE VIEW, ALTER, DROP, MODIFY).

    • Relation (Table) Level: Permissions on specific base relations or views (SELECT, INSERT, UPDATE, DELETE, REFERENCES). INSERT and UPDATE can be restricted to specific column lists.

  • Access Matrix Model: A matrix MM where rows represent subjects (users, accounts, roles), columns represent objects (relations, views, columns), and cells M(i,j)M(i,j) store granted privilege types.

  • Schema Ownership and Propagation:

    • Owner Account: Account that creates a schema/table automatically holds all privileges WITH GRANT OPTION.

Schemas for the two relations EMPLOYEE and DEPARTMENT
  • SQL Grant and Revoke Examples:

    • Granting table creation: sql GRANT CREATETAB TO A1; CREATE SCHEMA EXAMPLE AUTHORIZATION A1; &nbsp;&nbsp;&nbsp;&nbsp;

    • Granting modification without propagation: sql GRANT INSERT, DELETE ON EMPLOYEE, DEPARTMENT TO A2; &nbsp;&nbsp;&nbsp;&nbsp;

    • Granting retrieval with propagation: sql GRANT SELECT ON EMPLOYEE, DEPARTMENT TO A3 WITH GRANT OPTION; GRANT SELECT ON EMPLOYEE TO A4; &nbsp;&nbsp;&nbsp;&nbsp;

    • Revoking privileges (cascading revocation): sql REVOKE SELECT ON EMPLOYEE FROM A3; &nbsp;&nbsp;&nbsp;&nbsp;     Revoking SELECT from A3 automatically revokes SELECT on EMPLOYEE from A4 because A4 received it from A3.

    • Column-level update privilege: sql GRANT UPDATE ON EMPLOYEE (Salary) TO A4; &nbsp;&nbsp;&nbsp;&nbsp;

  • Granular View-based Authorization: ```sql CREATE VIEW A3EMPLOYEE AS SELECT Name, Bdate, Address FROM EMPLOYEE WHERE Dno = 5;

    GRANT SELECT ON A3EMPLOYEE TO A3 WITH GRANT OPTION;   ```

  • Propagation Limits:

    • Horizontal Propagation Limit: Restricts a user to granting a privilege to at most ii other accounts.

    • Vertical Propagation Limit: Restricts the depth jj of downstream GRANT OPTION chains.

Mandatory Access Control (MAC) and Multilevel Security

  • Mandatory Access Control (MAC) classifies subjects (users) and objects (data items) into security classes (e.g., Top Secret (TS\text{TS}) > Secret (S\text{S}) > Confidential (C\text{C}) > Unclassified (U\text{U})).

  • Bell-LaPadula Model Rules:

    1. Simple Security Property: A subject SS is not allowed read access to an object OO unless class(S)≥class(O)\text{class}(S) \ge \text{class}(O) (No read-up).

    2. Star Property (*-Property): A subject SS is not allowed write access to an object OO unless class(S)≤class(O)\text{class}(S) \le \text{class}(O) (No write-down).

  • Multilevel Relations:

    • Schema: R(A1,C1,A2,C2,…,An,Cn,TC)R(A_1, C_1, A_2, C_2, \dots, A_n, C_n, TC) where CiC_i is the security classification of attribute AiA_i, and TCTC is the tuple classification (TC=max⁡(Ci)TC = \max(C_i)).

    • Apparent Key: Primary key attributes under standard single-level definitions.

    • Filtering: Automatically replacing attribute values with null when displayed to users whose clearance is lower than the attribute's security classification.

    • Polyinstantiation: The presence of multiple tuples with the same apparent key but different attribute values and classification levels, preventing lower-clearance users from inferring higher-classified data via update failures.

    • Multilevel Integrity Rules: Entity Integrity (apparent key attributes cannot be null and must share the same classification level within a tuple), Null Integrity, and Interinstance Integrity.

Role-Based Access Control (RBAC) and Row-Level Security

  • Role-Based Access Control (RBAC): Privileges are granted to organizational roles (CREATE ROLE, DESTROY ROLE). Users are assigned to roles, simplifying administration.

  • Separation of Duties (Mutual Exclusion of Roles):

    • Static (Authorization Time) Exclusion: A user cannot be assigned to two mutually exclusive roles.

    • Dynamic (Runtime) Exclusion: A user can hold both roles, but cannot activate both within the same active session.

  • Role Hierarchies: Partial order relationships (reflexive, transitive, antisymmetric) where senior roles inherit permissions of junior roles.

  • Row-Level Access Control and Label-Based Security: Assigns labels directly to individual data rows. Access is granted if a user's session label matches row label criteria.

  • Web and Mobile Access Control: Enforces content-based access control and user credentials (using Directory Services Markup Language - DSML, XML signatures with canonicalization, and XML encryption).

SQL Injection Attacks and Preventive Measures

  • SQL Injection (SQLi): An attack vector where malicious SQL code is injected into input fields, altering query structures executed by the backend database.

  • Primary Attack Types:

    • SQL Manipulation: Modifying existing SQL predicates (e.g., altering a login query to SELECT * FROM users WHERE username = 'jake' and (PASSWORD = 'jakespasswd' or 'x' = 'x');).

    • Code Injection: Appending new independent SQL commands to the original query.

    • Function Call Injection: Inserting database or OS function calls (e.g., invoking UTL_HTTP.REQUEST('http://129.107.2.1/') inside a TRANSLATE call).

  • Injection Risks: Database fingerprinting, Denial of Service (DoS), Authentication bypass, Parameter identification, Remote code execution, Privilege escalation.

  • Preventive Measures:

    • Bind Variables / Parameterized Statements: Using prepared statements (e.g., JDBC PreparedStatement) to pass input as typed literals rather than concatenated executable strings.

    • Input Validation and Filtering: Sanitizing escape characters (e.g., doubling single quotes '').

    • Function Security: Restricting execution rights on built-in administrative packages and custom functions.

Statistical Database Security, Flow Control, and Encryption

  • Statistical Database Security & Inference Control:

    • Statistical queries compute aggregate values (COUNT, SUM, AVG, MIN, MAX) over populations without revealing individual records.

    • Inference Attack: Inferring sensitive personal attributes by executing sequences of overlapping aggregate queries on small populations.

    • Mitigation Strategies: Enforcing minimum population size thresholds for aggregate queries, tracking query history to block repeated sub-population probes, injecting random noise into query outputs, and record partitioning.

  • Flow Control & Covert Channels:

    • Flow Control: Ensuring information does not flow explicitly or implicitly from high security classes to lower security classes.

    • Covert Channels: Unintended communication paths that bypass security policies to leak information.

    • Storage Channels: Conveying data by altering system state or shared resources.

    • Timing Channels: Conveying data by altering processing execution time or event sequences.

  • Data Encryption and Public Key Infrastructure (PKI):

    • Plaintext and Ciphertext.

    • Standards:

    • DES (Data Encryption Standard): 64-bit blocks with 56-bit key length.

    • AES (Advanced Encryption Standard): 128-bit blocks with 128, 192, or 256-bit key lengths.

    • TripleDES: Fallback algorithm for legacy systems.

    • Legal Prescriptions: State encryption mandates (e.g., Georgia Law OCGA 10-1-911) requiring encryption for SSNs, driver's licenses, and financial account numbers.

    • Symmetric (Secret Key) Encryption: Uses a single key for both encryption and decryption.

    • Asymmetric (Public Key) Encryption: Uses a mathematically related key pair (Public Key for encryption, Private Key for decryption).

    • RSA Algorithm:

    • Select large prime numbers aa and bb, compute n=a×bn = a \times b

    • Compute encryption key ee relatively prime to (a−1)×(b−1)(a-1) \times (b-1).

    • Ciphertext C=Pe(modn)C = P^e \pmod n.

    • Decryption key dd satisfies d×e=1(mod(a−1)×(b−1))d \times e = 1 \pmod{(a-1) \times (b-1)}.

    • Recovered Plaintext P=Cd(modn)=(Pe)d(modn)P = C^d \pmod n = (P^e)^d \pmod n

    • Digital Signatures & Digital Certificates: Digital signatures sign message digests using a private key to provide non-repudiation. Digital Certificates issued by a Certification Authority (CA) bind a public key to an owner's Distinguished Name (DN).

Case Study: Oracle Label-Based Security and Virtual Private Database (VPD)

  • Virtual Private Database (VPD): Server-enforced row-level security feature in Oracle Enterprise Edition. Uses PL/SQL functions registered via DBMS_RLS to dynamically append WHERE clause predicates to user SQL statements.

Oracle label security architecture
  • Architectural Flow:

    1. Session issues SQL query.

    2. Engine checks Discretionary Access Control (DAC) table permissions.

    3. Engine checks VPD policies and executes associated PL/SQL policy functions.

    4. Policy functions return dynamic WHERE predicates.

    5. Row-level security labels evaluate individual rows against the user's session clearance label.

    6. Query executes over the filtered row set.

  • Label Components in Oracle Security:

    • Level: Hierarchical sensitivity classification (e.g., HIGHLY_SENSITIVE (HS\text{HS}), SENSITIVE (S\text{S}), CONFIDENTIAL (C\text{C}), UNCLASSIFIED (U\text{U})).

    • Compartments: Non-hierarchical categories grouping data projects (e.g., FIN, CHEM).

    • Groups: Hierarchical organizational affiliations (e.g., WR, WR_SAL).

    • Evaluation Rule: A user can access a row only if the user's maximum clearance level is greater than or equal to the row's required level, the user possesses authorization for ALL compartments in the row's label, and the user belongs to the row's assigned group or a parent group.


Advanced Data Analytics, Warehousing, and OLAP
  • Data Analytics: Processing data to infer patterns, correlations, or predictive models to drive strategic business decisions.

  • Decision-Making Tasks:

    • Low-Value, High-Volume Decisions: Automated, high-frequency decisions based on user profiles (e.g., ad systems).

    • High-Value, Long-Horizon Decisions: Long-term strategic predictions to optimize production and inventory.

  • Business Intelligence (BI): Broad organizational term synonymous with data analytics.

  • Decision Support: Analytical querying and aggregation over large datasets (contrasted with Online Transaction Processing or OLTP).

Data Warehousing Infrastructure
  • Data Warehouse: Centralized repository gathering historical data from multiple heterogeneous sources under a unified schema.

  • Data Gathering Architecture:

    • Source-Driven Architecture: Data sources transmit updates continually or periodically to the warehouse.

    • Destination-Driven Architecture: Data warehouse periodically requests updates from source systems.

  • Data Freshness: Latency of replicated data; real-time requirements utilize stream processing infrastructures.

  • Materialized View: Integrated warehouse schema acting as a pre-computed view of source data.

  • Data Transformation and Cleansing (ETL / ELT):

    • Data Cleansing: Correcting errors/misspellings using reference databases via fuzzy lookup.

    • Deduplication (Merge-Purge): Eliminating duplicate customer/address records.

    • Householding: Grouping individual records residing at the same physical dwelling.

    • ETL (Extract, Transform, Load): Traditional pipeline transforming data prior to loading.

    • ELT (Extract, Load, Transform): Pipeline loading raw data first, leveraging parallel engines (e.g., MapReduce) for transformation.

  • View Maintenance: Process of propagating updates from sources to the warehouse.

  • Data Summarization: Storing pre-aggregated data to manage storage constraints.

Multidimensional Data Models and Warehouse Schemas
  • Multidimensional Data Components:

    • Measure Attributes: Quantitative numerical values meant for aggregation (e.g., price, quantity).

    • Dimension Attributes: Categorical fields used to group, filter, or slice measure data (e.g., date, store_id).

  • Warehouse Schemas:

    • Fact Table: Large central table containing measure attributes and foreign key dimension IDs.

    • Dimension Tables: Outlying tables storing descriptive context attributes.

    • Star Schema: Schema consisting of a central fact table referencing non-normalized dimension tables.

    • Snowflake Schema: Schema variant where dimension tables are normalized into multi-level sub-dimension tables.

Database Engine Support for Warehouses
  • Storage Layouts:

    • Row-Oriented Storage: Tuple attributes stored sequentially; optimal for OLTP point lookups and updates.

    • Column-Oriented Storage: Relation attributes stored in separate contiguous files; optimal for analytical scans and aggregations.

    • Offset Formula: For fixed-size attribute AA, the ii-th tuple value offset is (i−1)×size(A)(i - 1) \times \text{size}(A).

  • Data Lakes: Schema-on-read repositories storing raw structured, semi-structured, or unstructured files without up-front schema design (e.g., Apache Hadoop, Apache Spark).

Online Analytical Processing (OLAP)
  • OLAP: Interactive analysis of multidimensional data across various aggregations in near real-time.

  • Cross-Tabulation (Pivot Table): Derived 2D grid mapping one dimension to rows, another to columns, displaying aggregated measures in intersecting cells.

  • Data Cube: nn-dimensional generalization of a cross-tab containing measures for all dimension value combinations, including summary value all.

    • Cube Cells: For nn dimensions, there are 2n2^n possible grouping combinations.

  • Core OLAP Operations:

    • Pivoting: Rotating data axes in a 2D cross-tab.

    • Slicing: Filtering a data cube by fixing a single dimension attribute to a constant value.

    • Dicing: Selecting a sub-cube by fixing values across multiple dimensions.

    • Rollup: Aggregating data from finer granularity to coarser detail.

    • Drill-down: Unpacking coarse summary data into fine-grained detail.

    • Dimension Hierarchies: Multi-level attribute paths (e.g., City →\rightarrow State →\rightarrow Country).

  • OLAP Architecture Types:

    • MOLAP: Memory array-based multidimensional storage.

    • ROLAP: Relational database storage with precomputed summary tables.

    • HOLAP: Hybrid model (MOLAP summaries + ROLAP base details).

OLAP Extensions in SQL
  • SQL PIVOT: Converts row values into dynamic column headings.

  • Grouping Constructs:

    • GROUP BY CUBE: Generates all 2n2^n grouping combinations.

    • GROUP BY ROLLUP: Generates hierarchical subset groupings based on attribute order.

    • GROUP BY GROUPING SETS: Generates explicitly listed grouping combinations.

    • GROUPING() Function: Returns 11 for OLAP-generated nulls, 00 for standard database nulls.

Reporting, Visualization, and Data Mining
  • Data Mining (KDD): Semi-automatic extraction of non-trivial, implicit, and actionable patterns from large datasets.

  • Predictive Analytics Techniques:

    • Classification: Supervised learning assigning items to discrete target classes.

    • Decision Trees: Tree-based classification using predicate internal nodes and class label leaf nodes.

    • Bayesian Classifiers: Probabilistic classification via Bayes' Theorem: p(ci∣d)=p(d∣ci)p(ci)p(d)p(c_i|d) = \frac{p(d|c_i)p(c_i)}{p(d)}.

    • Naive Bayes Assumption: p(d∣ci)=∏k=1np(dk∣ci)p(d|c_i) = \prod_{k=1}^n p(d_k|c_i).

    • Support Vector Machines (SVM): Maximum-margin hyperplanes separating classes using kernel functions for non-linear boundaries.

    • Neural Networks / Deep Learning: Multi-layer networks tuned via backpropagation.

    • Regression: Predicting continuous numeric values (e.g., Linear Regression: Y=a0+a1X1+⋯+anXnY = a_0 + a_1 X_1 + \dots + a_n X_n).

    • Association Rules: Co-occurrence patterns (A→BA \rightarrow B).

    • Support: Fraction of total transactions containing both antecedent and consequent.

    • Confidence: Conditional probability of consequent given antecedent.

    • Clustering: Unsupervised grouping minimizing intra-cluster distances to centroids (e.g., Collaborative Filtering).

    • Text Mining: Extracting insights from unstructured text (e.g., Sentiment Analysis, Named Entity Recognition, Knowledge Graphs).

Distributed Database Concepts and Architectures
  • Distributed Database (DDB): Collection of multiple logically interrelated databases distributed over a network.

  • DDBMS: Software managing a DDB transparently to end users.

Core Characteristics and Transparencies
  • Transparencies:

    • Location Transparency: Command execution independent of physical data placement or node location.

    • Naming Transparency: Global object referencing without requiring site qualifiers.

    • Replication Transparency: User unawareness of duplicate data copies.

    • Fragmentation Transparency: User unawareness of horizontal or vertical partitioning.

  • System Metrics:

    • Reliability: Probability that a system is operational at a given time point.

    • Availability: Probability system is continuously operational throughout a time interval.

    • Scalability: Horizontal (adding processing nodes) vs Vertical (upgrading node hardware).

    • Partition Tolerance: System capacity to remain operational during network isolation events.

  • Autonomy Types:

    • Design Autonomy: Local node freedom of data model and transaction choices.

    • Communication Autonomy: Local control over external message sharing.

    • Execution Autonomy: Independence in scheduling and executing local transactions.

Data Fragmentation, Replication, and Allocation
  • Horizontal Fragmentation (Sharding): Dividing a relation into tuple subsets via selection conditions σC(R)\sigma_C(R).

    • Complete Horizontal: Selection predicates cover all tuples (⋁Ci=TRUE\bigvee C_i = \text{TRUE}). Reconstructed via UNION.

    • Disjoint: Predicates are mutually exclusive (Ci∧Cj=FALSEC_i \wedge C_j = \text{FALSE}).

    • Derived Horizontal: Partitioning a secondary relation based on a primary relation's foreign key predicate.

  • Vertical Fragmentation: Dividing attributes into subsets via projection πL(R)\pi_L(R).

    • Complete Vertical: Every attribute covered and primary key preserved in every fragment (⋂Li=PK(R)\bigcap L_i = \text{PK}(R)). Reconstructed via FULL OUTER JOIN.

  • Mixed Fragmentation: Combination of horizontal selection and vertical projection πL(σC(R))\pi_L(\sigma_C(R)).

  • Allocation Schemas:

    • Nonredundant: Each fragment allocated to exactly one site.

    • Fully Replicated: Entire database duplicated across all nodes (max read performance, high write cost).

    • Partial Replication: Specific fragments replicated across a subset of sites.

Distributed Concurrency Control and Recovery
  • Concurrency Control Approaches:

    • Primary Site: Single centralized coordinator node managing all lock requests.

    • Primary Copy: Lock coordination distributed across nodes based on data item location.

    • Voting Method: Distributed locking requiring majority consensus votes from replica nodes.

  • Commit Protocols:

    • Two-Phase Commit (2PC): Blocking protocol consisting of Prepare and Commit phases.

    • Three-Phase Commit (3PC): Non-blocking protocol introducing prepare-to-commit state with timeouts.

Distributed Query Processing and Semijoins
  • Query Processing Stages: Query Mapping →\rightarrow Localization →\rightarrow Global Query Optimization →\rightarrow Local Query Optimization.

  • Semijoin (R⋉A=BSR \ltimes_{A=B} S):

    • Formula: R⋉A=BS=πR(R⋈A=BS)=R⋈A=B(πB(S))R \ltimes_{A=B} S = \pi_R(R \bowtie_{A=B} S) = R \bowtie_{A=B} (\pi_B(S)).

    • Purpose: Ships unique join keys to eliminate non-matching tuples before transferring full relations, reducing network communication volume. Non-commutative (R⋉S≠S⋉RR \ltimes S \neq S \ltimes R).

System Architectures and Classification
  • Multiprocessor Architectures:

    • Shared-Memory: Processors share RAM and disk.

    • Shared-Disk: Processors have independent RAM, shared disk.

    • Shared-Nothing: Independent RAM and disk per processor; communicates via bus/network.

  • Federated Database System (FDBS): Multidatabase system of autonomous, heterogeneous component databases.

  • FDBS 5-Level Schema: Local Schema →\rightarrow Component Schema →\rightarrow Export Schema →\rightarrow Federated Schema →\rightarrow External Schema.

  • Three-Tier Architecture:

    • Presentation Tier: Client web interface (HTML, JS).

    • Application Tier: Business logic server (Java, C#, C++).

    • Database Server: RDBMS handling query and transaction execution.

Query Optimization
  • Query Optimization: Process of selecting the minimum-cost evaluation plan among logically equivalent execution strategies.

Relational Expression Transformations and Equivalence Rules
  • Equivalence Rules:

    1. Cascade of Selections: σθ1∧θ2(E)=σθ1(σθ2(E))\sigma_{\theta_1 \wedge \theta_2}(E) = \sigma_{\theta_1}(\sigma_{\theta_2}(E))

    2. Commutativity of Selection: σθ1(σθ2(E))=σθ2(σθ1(E))\sigma_{\theta_1}(\sigma_{\theta_2}(E)) = \sigma_{\theta_2}(\sigma_{\theta_1}(E))

    3. Cascade of Projections: ΠL1(ΠL2(E))=ΠL1(E)\Pi_{L_1}(\Pi_{L_2}(E)) = \Pi_{L_1}(E)

    4. Selection with Join: σθ(E1×E2)=E1⋈θE2\sigma_\theta(E_1 \times E_2) = E_1 \bowtie_\theta E_2

    5. Commutativity of Join: E1⋈E2=E2⋈E1E_1 \bowtie E_2 = E_2 \bowtie E_1

    6. Associativity of Join: (E1⋈E2)⋈E3=E1⋈(E2⋈E3)(E_1 \bowtie E_2) \bowtie E_3 = E_1 \bowtie (E_2 \bowtie E_3)

    7. Pushing Selections: Selections pushed down past joins if predicate attributes belong solely to that subexpression.

    8. Pushing Projections: Projections pushed down past joins to retain only required output/join attributes.

Important Non-Equivalences
  • Outer Join Selection Pushing: Pushing selection down past outer join is invalid in general (may prematurely eliminate null-extended tuples).

  • Outer Join Non-Associativity: Outer joins are NOT associative ((r \leftouterjoin s) \leftouterjoin t \neq r \leftouterjoin (s \leftouterjoin t)).

Cost-Based Optimization and Plan Enumeration
  • Search Space Reduction:

    • DAG Subexpression Sharing: Memory sharing for identical sub-trees.

    • Dynamic Programming: Bottom-up pruning of dominated sub-plans.

    • Left-Deep Trees: Restricting join order evaluation trees to enable execution pipelining.

  • EXPLAIN Command: Engine command displaying execution plan and cost metrics (EXPLAIN <query>).

Database Security, Privacy, and Protection
  • Database Security Triad (CIA):

    • Integrity: Protection against improper or unauthorized modifications.

    • Availability: Ensuring timely, uninterrupted access for authorized subjects.

    • Confidentiality: Protection against unauthorized data disclosure.

DBA Responsibilities and Database Auditing
  • DBA Privileged Operations: Account Creation, Privilege Granting, Privilege Revocation, Security Level Assignment.

  • Audit Trail: Enhanced system log recording user IDs, IP addresses, timestamps, and statements to trace tampering.

Sensitivity, Disclosures, and Precision
  • Tradeoff:

    • Security: Disclosing only non-sensitive data and rejecting queries touching sensitive fields.

    • Precision: Disclosing as much non-sensitive data as possible while protecting sensitive data.

Discretionary Access Control (DAC)
  • DAC: Identity-based access control granting explicit privileges on objects.

  • Access Matrix: Matrix MM where rows = subjects, columns = objects, cells M(i,j)M(i,j) = granted privileges.

  • Propagation Limits:

    • Horizontal Limit: Restricts total number of downstream grantees (ii).

    • Vertical Limit: Restricts granting depth level (jj).

Mandatory Access Control (MAC) and Multilevel Security
  • MAC: Security level classification model (Top Secret TS\text{TS} > Secret S\text{S} > Confidential C\text{C} > Unclassified U\text{U}).

  • Bell-LaPadula Rules:

    1. Simple Security Property: No read-up (class(S)≥class(O)\text{class}(S) \ge \text{class}(O)).

    2. Star Property (*-Property): No write-down (class(S)≤class(O)\text{class}(S) \le \text{class}(O)).

  • Multilevel Terms:

    • Filtering: Replacing sensitive values with null for lower-clearance users.

    • Polyinstantiation: Storing multiple tuples with identical apparent keys at different security levels to eliminate covert inference channels.

Role-Based Access Control (RBAC) and Row-Level Security
  • RBAC: Privileges assigned to organizational roles rather than individual users (CREATE ROLE, GRANT).

  • Separation of Duties: Mutual exclusion of roles (Static at authorization vs Dynamic at runtime) to prevent fraud/collusion.

  • Row-Level Access Control: Row-by-row label assignment evaluated against user session labels.

SQL Injection Attacks and Preventive Measures
  • SQL Injection (SQLi): Malicious SQL code injection via unsanitized user inputs.

  • Types: SQL Manipulation, Code Injection, Function Call Injection.

  • Prevention: Bind Variables / Parameterized Statements (e.g., PreparedStatement), Input Validation / Escaping, Function Security.

Statistical Database Security, Flow Control, and Encryption
  • Statistical Security: Protecting individual records while serving aggregate queries (COUNT, AVG).

    • Inference Attack: Deducing private attributes using overlapping aggregate queries.

    • Countermeasures: Minimum population threshold, query tracking, output noise injection, data partitioning.

  • Covert Channels: Information leakage paths bypassing policy (Storage Channels vs Timing Channels).

  • Encryption Algorithms:

    • Symmetric: Same secret key for encryption and decryption (AES, DES).

    • Asymmetric (Public Key): Public key encrypts, private key decrypts (RSA).

    • RSA Math: Ciphertext C=Pe(modn)C = P^e \pmod n, Plaintext P=Cd(modn)P = C^d \pmod n.

    • Digital Signatures: Non-repudiation using private key signing of message digests.

    • Digital Certificates: Issued by Certification Authority (CA) to authenticate public key ownership.

Case Study: Oracle Label-Based Security and Virtual Private Database (VPD)
  • Virtual Private Database (VPD): Server-enforced row-level security dynamically appending PL/SQL WHERE clause predicates to user queries via DBMS_RLS.

  • Oracle Security Label Components:

    • Level: Hierarchical classification (HS > S > C > U).

    • Compartments: Non-hierarchical project categories (e.g., FIN, CHEM).

    • Groups: Hierarchical organizational units (e.g., WR).