Relational Algebra, Normalization, and Transaction Management – Comprehensive Notes

Relational Algebra, Databases, and Transaction Management – Comprehensive Notes

• Context and scope

  • Database: a collection of persistent data
  • DBMS: software system to create, populate, and query a database
  • Relational Database / RDBMS: stores data in relations (tables) with a predefined schema
  • Primary keys identify a tuple within a table; foreign keys connect tuples across tables
  • Example schemas
  • Students(sid, name, login, age, gpa); sid is a primary key
  • Courses(cid, instructor, quarter, dept)

• Relational Algebra: overview

  • A formal, procedural query language for specifying queries on relations
  • Expressions built from relational-algebra operators applied to relations
  • Each operator takes one or two relations as input and yields a relation as output
  • Basic idea: describe the step-by-step computation to obtain the answer

• Key formal notions (basis for understanding later sections)

  • A relation r is a subset of D1 × D2 × … × Dn (arity n) where each Di is a domain (data type)
  • Tuples: members a1 ∈ D1, a2 ∈ D2, …, an ∈ Dn
  • Relation instance: current value of a relation, shown as a table
  • Arity: number of domains/attributes in a relation
  • Cardinality: number of tuples in a relation
  • Relational schema: R(A1, A2, …, An); arity n = number of attributes
  • Relations are unordered: the order of tuples does not matter

• Basic relational-algebra operators (six foundational, plus derived)

  • Selection: σ_{p}(R) selects rows that satisfy predicate p
  • Notation example: σ_{gpa > 3.3}(S1)
  • Projection: π_{A1, A2, …, Ak}(R) keeps only specified attributes
  • Eliminates duplicate tuples (relations are sets by definition)
  • Union: R ∪ S combines tuples from R and S (must be union-compatible)
  • Cartesian product (cross product): R × S pairs every tuple in R with every tuple in S
  • Difference: R − S returns tuples in R not in S
  • Rename: ρ_{name}(R) gives a relation the same tuples with a new name (and can rename attributes)
  • Derived and related operators (not basic but important)
  • Intersection: R ∩ S (requires same arity and compatible domains)
  • Join: natural join (R ⨝ S) combines on common attributes
  • Division: R ÷ S used for “for all” type queries
  • Aggregates: avg, min, max, sum, count with possible grouping
  • Generalized projection: allows arithmetic expressions in projection list
  • Outer join: left, right, and full outer joins (preserve one side’s tuples with nulls for non-matching tuples)
  • Assignment (non-standard, used to express complex queries): temp ← expression

• Notation details (typical forms used in slides)

  • Selection predicate: p(t) where t ∈ R
  • Selection example: σ_{A = B ∧ D > 5}(R)
  • Projection: ÕA1, A2, …, Ak (R) (often written as π rather than Õ in some slides)
  • Union: R È S
  • Intersection: R Ç S
  • Cartesian product: R x S
  • Join: R ⨝ S or R ⋈ S
  • Division: R ÷ S
  • Renaming: ρ_{newname}(E)

• Example domain: banking schema (illustrative schemas)

  • branch(branch-name, branch-city, assets)
  • customer(customer-name, customer-street, customer-city)
  • account(account-number, branch-name, balance)
  • loan(loan-number, branch-name, amount)
  • depositor(customer-name, account-number)
  • borrower(customer-name, loan-number)
  • Useful queries: e.g., get all loans over a threshold, or customers with loans and/or accounts

• Example relational-algebra queries (illustrative results)

  • Find all loans of over $1200: $ext{FavLoan} = \bigl( ext{σ}_{ ext{amount} > 1200}( ext{loan}) \bigr)$
  • Then project the loan numbers: $ext{π}_{ ext{loan-number}}( ext{FavLoan})$
  • Find names of all customers who have a loan, an account, or both: $ext{π}<em>{ ext{customer-name}}( ext{borrower}) \, ext{∩} \, ext{π}</em>{ ext{customer-name}}( ext{depositor})$
  • Find names of customers who have a loan at Perryridge branch: involve σ on loan with sbranch_name = 'Perryridge' and join with borrower

• Projection and selection composition examples

  • Combine selection and projection: π{name, gpa}(σ{gpa > 3.3}(S1))
  • Example result: list of students with gpa > 3.3 with their names and gpas

• Example of a relation and the idea of a relation instance

  • An example relation (account-number, branch-name, balance) shown as a table
  • Cardinality and arity concepts illustrated via simple tables

• Relational data model fundamentals

  • Set-theoretic domain: domain per attribute; tuples are elements of the Cartesian product of domains
  • Attributes and schema are named as a set; arity corresponds to number of attributes
  • Relations are unordered collections of tuples

• How to compose relational-algebra expressions

  • Basic compositions: e.g., sA=C(r × s) where A, B, C, D are attributes; A × B yields cross product; then select/project as needed
  • Example composition: sA=C(r × s) then projection onto certain attributes

• Practical: relational-algebra queries (banking example set)

  • Queries from the banking example include details about those who have loans or accounts, or both, and various dynamic predicates like branch location, loan amounts, etc.
  • These illustrate the use of selection, projection, union, intersection, and join in practice

• Relational database design: overview of normalization

  • Features of good relational design include minimizing redundancy and avoiding anomalies
  • Problems arise when we combine relations into a single schema (in_dep example) and duplicate information
  • Lossless decomposition ensures information is preserved when splitting a relation into multiple relations
  • Dependency preservation ensures that enforcing functional dependencies can be checked within the individual decomposed relations

• Functional dependencies (FDs)

  • FD notation: X → Y means Y is determined by X
  • If two tuples agree on X, they must agree on Y
  • Key concepts: superkey, candidate key, and prime attributes (attributes that are part of some candidate key)
  • Closure of a set of FDs: F+ is all FDs logically implied by F using Armstrong’s axioms (reflexivity, augmentation, transitivity, and derived rules like union and decomposition)
  • Attribute-closure algorithm: compute a+ for a set of attributes a under F to see what it functionally determines
  • Canonical cover Fc: minimal, equivalent FD set that preserves F+ and is used to optimize FD checking
  • Extraneous attributes: features in left or right sides of FDs that can be removed without changing F+; removal decisions rely on Fc
  • Dependency preservation: a decomposition is dependency-preserving if (F1 ∪ F2 ∪ … ∪ Fn)+ = F+; verifying this can be expensive; often a practical compromise is sought

• Normal forms (NF) and decomposition principles

  • 1NF (First Normal Form): all domain values atomic; no repeating groups
  • 2NF (Second Normal Form): in 1NF and no partial dependency of non-prime attributes on a candidate key
  • 3NF (Third Normal Form): in 2NF and no transitive dependency; every non-key attribute is non-transitively dependent on a candidate key
  • BCNF (Boyce–Codd Normal Form): for every non-trivial FD X → Y, X is a superkey
  • 4NF (Fourth Normal Form): no non-trivial multivalued dependencies Y ⤳ Z unless Y or Z is a superkey
  • 5NF (Project-Join Normal Form / PJNF): join dependencies generalize MVDs; rarely used in practice
  • Relationships among NF: BCNF ⇒ 3NF; 3NF ⇒ 2NF ⇒ 1NF; but BCNF can be more restrictive than 3NF and may sacrifice dependency preservation

• Examples and algorithms in normalization

  • Lossless decomposition: decompose R into R1, R2 such that R1 ∩ R2 → R1 or R1 ∩ R2 → R2 holds in F+ (sufficient condition)
  • Example: R = (A, B, C) with F = {A → B, B → C} yields lossless decompositions such as R1 = (A, B) and R2 = (B, C)
  • 3NF decomposition algorithm: construct Fc (canonical cover) and generate Ri for each a → b in Fc; ensure coverage of candidate keys; optionally remove redundant Ri
  • 3NF is dependency-preserving and lossless; BCNF is lossless but may not preserve dependencies

• MVDS and 4NF

  • Multivalued dependencies (Y ⤳⤳ Z) capture a requirement that Y and Z values are independent given Y
  • 4NF requires that for every non-trivial MV dependency, either Y or Z is a superkey
  • Decomposition algorithms exist to achieve 4NF while preserving losslessness

• Modeling temporal data and denormalization considerations

  • Temporal data introduces time-varying attributes and valid-time constraints; functional dependencies may not hold across all time snapshots
  • Temporal modeling often adds start/end times to attributes/relations; this complicates constraints and requires careful design
  • Denormalization for performance: in some cases, duplicating data or using materialized views can speed up queries at the expense of write complexity

• ER model and normalization relationship

  • A well-designed ER model often yields a set of tables that already satisfy normalization requirements; poor designs can introduce FDs across entities/relationships that require decomposition

• Transaction processing and isolation (high-level outline)

  • ACID properties: Atomicity, Consistency, Isolation, Durability
  • Transaction: a unit of work that accesses/updates data; must handle failures and concurrency
  • Serializability: a schedule is serializable if it is equivalent to some serial execution
  • Conflict serializability: based on conflicting operations; can be checked via a precedence graph (cycle detection)
  • View serializability: based on read and write dependencies; generally harder to test
  • Schedules: sequence of operations from one or more transactions; must respect per-transaction order
  • Precedence graphs: directed graphs of transactions; an acyclic graph implies conflict serializability

• Concurrency control and locking mechanisms

  • Locks: Shared (S) vs Exclusive (X) modes; lock-granularity can be at various levels (fine-grained vs coarse-grained)
  • Lock compatibility matrix governs when locks can be granted
  • Two-Phase Locking (2PL): growing phase (acquire locks) and shrinking phase (release locks); guarantees serializability
  • Strict 2PL and Rigorous 2PL: keep all exclusive locks until commit/abort to ensure recoverability and reduce cascading aborts
  • Deadlocks: cycles of waiting transactions; detection and prevention strategies exist (timeout, wait-die, wound-wait, deadlock prevention)
  • Multigranularity locking: lock at different granularities (database, area, file, record); intention locks (IS, IX, SIX) enable efficient locking hierarchies
  • Predicate locking and phantom prevention: protect against phantom reads by locking on predicates or index structures (e.g., next-key locking for indices)
  • Index locking to prevent phantoms: lock index leaves or next keys during lookups and updates to avoid phantom results

• Recovery and logging (overview of approaches)

  • Log-based recovery: logs record the start, each update, and commit/abort; used to undo/redo after crash
  • Immediate modification (write-ahead logging, WAL): logs must be written before the data pages are updated; ensures atomicity and recoverability
  • Deferred modification: apply updates at commit time; simpler recovery but requires more coordination
  • Checkpointing: periodically flushes in-memory state to stable storage to bound redo/undo work; reduces recovery time
  • ARIES (Algorithm for Recovery and Isolation Exploiting Semantics): a sophisticated, practical recovery method with several optimizations (LSN, dirty-page table, CLR, fuzzy checkpoints, etc.)

• ARIES: core ideas and data structures

  • Log Sequence Numbers (LSN): monotonically increasing IDs for log records; used to identify and order actions
  • PageLSN: last LSN reflected on a page; used to determine if a page needs redo
  • Dirty Page Table (DPT): tracks pages that have been updated but not yet written to disk
  • Checkpoints: record the set of dirty pages and active transactions at a fixed point in time
  • Recovery passes (three):
  • Analysis: determine which transactions to undo, which pages are dirty, and the RedoLSN from which to start redo
  • Redo: replay history to bring database pages up to date, skipping records that are already reflected on disk
  • Undo: rollback incomplete transactions by applying compensating log records
  • CLR (Compensation Log Records): log records that record the undo of an action
  • Repeating history: in recovery, redo and undo phases may reapply/undo actions to reach consistent state

• Shadow paging (alternative to WAL in some contexts)

  • Maintains a shadow page table and a current page table; writes are done to a new page copy and then the table is updated to point to the new version after a commit
  • Pros: no logging overhead; consistent state can be achieved without log replay
  • Cons: expensive to copy page tables; fragmentation; not easily supporting concurrent transactions; generally superseded by WAL-based approaches in modern systems

• Summary: practical recovery and consistency strategies

  • WAL with ARIES-style recovery is the dominant approach in modern systems due to balance of performance and robustness
  • Some modern systems explore alternative techniques (shadow paging, snapshotting) for certain workloads

• Practice-oriented notes on model and usage

  • SQL-level implementations use FDs and constraints implicitly through keys and assertions; explicit FD enforcement is typically not exposed directly in SQL
  • Normalization aims to reduce redundancy and update anomalies; practical systems often use a mix of normalized schemas and denormalized copies to improve read performance
  • Temporal data modeling and evolving data schemas require careful handling of constraints across time

• Key formulas and symbols (summary of core math and notation used in the course materials)

  • Relational algebra expressions
  • Selection: $\sigma_{p}(R)$
  • Projection: $\pi_{A1,A2,…,Ak}(R)$
  • Union: R ot S (often written as $R \, ext{È} \, S$)
  • Intersection: $R \cap S$
  • Difference: $R - S$
  • Cartesian product: $R imes S$
  • Join (natural join): $R \bowtie S$ or $R \Join S$
  • Division: $R \div S$
  • FD and closure
  • FD: $X \rightarrow Y$
  • Attribute closure: $X^+$ (set of attributes functionally determined by X under a given FD set F)
  • FD closure: $F^+$ (all FDs implied by F using Armstrong’s axioms)
  • Normal forms and dependencies
  • 1NF, 2NF, 3NF, BCNF, 4NF, 5NF
  • Lossless join condition: if $R = R1 \cup R2$ and $R1 \cap R2 \rightarrow R1$ or $R1 \cap R2 \rightarrow R2$ holds, the decomposition is lossless
  • Dependency preservation: the decomposition into Ri is dependency-preserving if $(F1 \cup F2 \cup … \cup Fn)^+ = F^+$
  • MVDS: $Y \twoheadrightarrow Z$ (multivalued dependency)
  • 4NF condition: for all MVDs, either the determinant is a superkey or the dependency is trivial
  • ARIES components (conceptual): LSN, DPT, PageLSN, CLR, checkpoint records, Redo/Undo passes

• Quick study prompts (to test understanding)

  • What makes a decomposition lossless, and how do FDs guarantee losslessness?
  • Explain the difference between 3NF and BCNF with an example that is 3NF but not BCNF.
  • What is the purpose of a canonical cover Fc, and how does it aid in normalization?
  • Describe ARIES three-pass recovery and the role of the Dirty Page Table.
  • Distinguish conflict serializability from view serializability and how precedence graphs are used for testing.

• Practical references and connections

  • Understanding these notes supports formulating accurate relational-algebra queries, selecting appropriate normal forms for database design, and reasoning about correctness guarantees in transactions and recovery.
  • Real-world relevance: database design choices impact performance, consistency, and recovery behavior in business-critical systems.

• Quick glossary (key terms)

  • relation, arity, domain, tuple, schema, primary key, foreign key, functional dependency (FD), closure F+, canonical cover Fc, lossless join, dependency preservation, join, division, MV dependency, 4NF, BCNF, 3NF, 1NF, 2NF, DAG (precedence graph) for serializability, ARIES, WAL, DPT, LSN, CLR, checkpoint, phantom, read/write locks, 2PL, 3PL, 4NF, PJNF

• Closing notes

  • While a large portion of the slides cover theory and formalism, the practical takeaways are: design clean, normalized schemas; use robust recovery protocols (ARIES-like with WAL) to ensure durability; and manage concurrency with correct locking strategies to achieve serializability and recoverability while balancing performance.