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.

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).

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
storetable containingcity,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_inforeferencing amanufacturer_idin a separatemanufacturertable).
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 , the -th tuple value is located at offset .
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.

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_nameandcolor).

Data Cube:
Generalization of a 2D cross-tab to 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 dimensions, there are possible grouping combinations. For a data cube with 3 colors, 4 items, and 3 sizes, the base cube has cells. Including summary values (
all), the cube size expands to cells.

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:
datetimedate/hour_of_dayday_of_week/monthquarteryear; location hierarchy:citystatecountryregion).
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
PIVOTClause:
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 grouping set combinations, insertingnullfor 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 distinct groupings.GROUP BY GROUPING SETS ((color, clothes_size), (clothes_size, item_name)): Explicitly lists the exact groupings to execute.GROUPING()Function: Returns1if anullvalue in an attribute is generated by an OLAPCUBE/ROLLUPoperation, and0for regular database nulls. Used inCASEstatements 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: Naive Bayesian Classifiers assume attribute independence conditional on the class:
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 from input variables via curve-fitting (e.g., Linear Regression: ).
Association Rules: Uncovering co-occurrence patterns in transactional itemsets (e.g., ).
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 into disjoint subsets of rows (tuples) using selection predicates .
Complete Horizontal Fragmentation: Selection conditions satisfy . Reconstruction requires the
UNIONoperation ().Disjointness: No tuple satisfies for any
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 into subsets using projection .
Complete Vertical Fragmentation: Attribute lists must satisfy and . Preserving the primary key in every fragment is mandatory for reconstruction via
FULL OUTER JOINorOUTER UNION.Mixed (Hybrid) Fragmentation: Combining selection and projection 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.

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-commitstate between the prepare and commit phases, establishing maximum wait timeouts.
Distributed Query Processing and Semijoins
Query Processing Stages:
Query Mapping: Translating a global query into relational algebra over global relations.
Localization: Mapping global algebraic expressions to localized queries over specific fragments using catalog guard conditions.
Global Query Optimization: Choosing execution plans minimizing combined CPU, I/O, and data communication costs across the network.
Local Query Optimization: Optimizing single-site execution plans at local nodes.
Data Transfer Cost Optimization:
Example Workload Metrics: Relation
EMPLOYEEat Site 1 (10,000 records, 100 bytes/rec, total size bytes). RelationDEPARTMENTat Site 2 (100 records, 35 bytes/rec, total size 3,500 bytes). Result required at Site 3.Strategy 1: Move
EMPLOYEE( bytes) andDEPARTMENT(3,500 bytes) to Site 3. Total transfer = 1,003,500 bytes.Strategy 2: Move
EMPLOYEEto 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
DEPARTMENTto Site 1, perform join, send 400,000 bytes to Site 3. Total transfer = 403,500 bytes.Semijoin Operation ():
Defined as .
Algorithm: Project join attribute from at Site 2 (), transfer the small projection to Site 1, join with 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 match join conditions in . Note: Semijoin is non-commutative ().
System Architectures and Classification

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.

Five-Level Schema Architecture in FDBS:
Local Schema: Conceptual schema of local component DBMS.
Component Schema: Local schema translated into a canonical Common Data Model (CDM).
Export Schema: Shareable subset of component schema made accessible to the federation.
Federated Schema: Integrated global schema combining all export schemas.
External Schema: Application-specific views defined over the federated schema.

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.


Fundamental Equivalence Rules:
Cascade of (Deconstructing Conjunctive Selections):
Commutativity of :
Cascade of (Combining Projections):
Selections with Cartesian Products and Theta Joins:
Commutativity of Theta Joins and Natural Joins:
Associativity of Joins and Cartesian Products:
Distribution of Selection over Theta Join:
When involves only attributes of :
When involves only attributes of and involves only attributes of :
Distribution of Projection over Theta Join:
When join condition involves attributes in :
With join attributes (from ) and (from ) not in :
Commutativity of Set Union and Intersection: and (Set difference is NOT commutative).
Associativity of Set Union and Intersection.
Distribution of Selection over Union, Intersection, and Set Difference:
Distribution of Projection over Union: .
Distribution of Selection over Aggregation: if involves only group-by attributes
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).
Selection Distribution over Outer Joins: \sigma_{\theta_1}(E_1 \leftouterjoin_\theta E_2) = (\sigma_{\theta_1}(E_1)) \leftouterjoin_\theta E_2 if involves only
Outer Join Replacement by Inner Join: If is null-rejecting on (evaluates to
falseorunknownon 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 , , and . 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 () to enable pipelining.
Inspection Commands for Query Plans:
EXPLAIN <query>(PostgreSQL, MySQL),EXPLAIN PLAN FOR(Oracle, displaying viadbms_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
DBAaccount (system/superuser/root account).Core DBA Privileged Actions:
Account Creation: Provisioning account identifiers and passwords.
Privilege Granting: Assigning discretionary or mandatory access permissions.
Privilege Revocation: Removing access permissions.
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:
Inherently sensitive (e.g., salary, HIV status).
Sensitive source (e.g., identity of an informer).
Explicitly declared sensitive by the data owner.
Sensitive attribute or record (e.g.,
Salaryattribute inEMPLOYEE).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).INSERTandUPDATEcan be restricted to specific column lists.
Access Matrix Model: A matrix where rows represent subjects (users, accounts, roles), columns represent objects (relations, views, columns), and cells store granted privilege types.
Schema Ownership and Propagation:
Owner Account: Account that creates a schema/table automatically holds all privileges
WITH GRANT OPTION.

SQL Grant and Revoke Examples:
Granting table creation:
sql GRANT CREATETAB TO A1; CREATE SCHEMA EXAMPLE AUTHORIZATION A1; Granting modification without propagation:
sql GRANT INSERT, DELETE ON EMPLOYEE, DEPARTMENT TO A2; Granting retrieval with propagation:
sql GRANT SELECT ON EMPLOYEE, DEPARTMENT TO A3 WITH GRANT OPTION; GRANT SELECT ON EMPLOYEE TO A4; Revoking privileges (cascading revocation):
sql REVOKE SELECT ON EMPLOYEE FROM A3; RevokingSELECTfromA3automatically revokesSELECTonEMPLOYEEfromA4becauseA4received it fromA3.Column-level update privilege:
sql GRANT UPDATE ON EMPLOYEE (Salary) TO A4;
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 other accounts.
Vertical Propagation Limit: Restricts the depth of downstream
GRANT OPTIONchains.
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 () > Secret () > Confidential () > Unclassified ()).
Bell-LaPadula Model Rules:
Simple Security Property: A subject is not allowed read access to an object unless (No read-up).
Star Property (*-Property): A subject is not allowed write access to an object unless (No write-down).
Multilevel Relations:
Schema: where is the security classification of attribute , and is the tuple classification ().
Apparent Key: Primary key attributes under standard single-level definitions.
Filtering: Automatically replacing attribute values with
nullwhen 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 aTRANSLATEcall).
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 and , compute
Compute encryption key relatively prime to .
Ciphertext .
Decryption key satisfies .
Recovered Plaintext
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/SQLfunctions registered viaDBMS_RLSto dynamically appendWHEREclause predicates to user SQL statements.

Architectural Flow:
Session issues SQL query.
Engine checks Discretionary Access Control (DAC) table permissions.
Engine checks VPD policies and executes associated
PL/SQLpolicy functions.Policy functions return dynamic
WHEREpredicates.Row-level security labels evaluate individual rows against the user's session clearance label.
Query executes over the filtered row set.
Label Components in Oracle Security:
Level: Hierarchical sensitivity classification (e.g.,
HIGHLY_SENSITIVE(),SENSITIVE(),CONFIDENTIAL(),UNCLASSIFIED()).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 , the -th tuple value offset is .
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: -dimensional generalization of a cross-tab containing measures for all dimension value combinations, including summary value
all.Cube Cells: For dimensions, there are 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.,
CityStateCountry).
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 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 for OLAP-generated nulls, 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: .
Naive Bayes Assumption: .
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: ).
Association Rules: Co-occurrence patterns ().
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 .
Complete Horizontal: Selection predicates cover all tuples (). Reconstructed via
UNION.Disjoint: Predicates are mutually exclusive ().
Derived Horizontal: Partitioning a secondary relation based on a primary relation's foreign key predicate.
Vertical Fragmentation: Dividing attributes into subsets via projection .
Complete Vertical: Every attribute covered and primary key preserved in every fragment (). Reconstructed via
FULL OUTER JOIN.
Mixed Fragmentation: Combination of horizontal selection and vertical projection .
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-commitstate with timeouts.
Distributed Query Processing and Semijoins
Query Processing Stages: Query Mapping Localization Global Query Optimization Local Query Optimization.
Semijoin ():
Formula: .
Purpose: Ships unique join keys to eliminate non-matching tuples before transferring full relations, reducing network communication volume. Non-commutative ().
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 Component Schema Export Schema Federated Schema 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:
Cascade of Selections:
Commutativity of Selection:
Cascade of Projections:
Selection with Join:
Commutativity of Join:
Associativity of Join:
Pushing Selections: Selections pushed down past joins if predicate attributes belong solely to that subexpression.
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 where rows = subjects, columns = objects, cells = granted privileges.
Propagation Limits:
Horizontal Limit: Restricts total number of downstream grantees ().
Vertical Limit: Restricts granting depth level ().
Mandatory Access Control (MAC) and Multilevel Security
MAC: Security level classification model (Top Secret > Secret > Confidential > Unclassified ).
Bell-LaPadula Rules:
Simple Security Property: No read-up ().
Star Property (*-Property): No write-down ().
Multilevel Terms:
Filtering: Replacing sensitive values with
nullfor 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 , Plaintext .
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/SQLWHEREclause predicates to user queries viaDBMS_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).