University Study Notes on the Relational Model and Relational Algebra

Fundamental Structure of Relational Databases

• Attributes and Columns

  • In the relational model, a database is a collection of relations (tables).

  • Attributes represent the columns of the table.

  • Example attributes for an instructor relation include:

    • ID

    • name

    • dept_name

    • salary

• Tuples and Rows

  • Tuples are the rows in a table.

  • A relation is defined as an unordered set of tuples that share the same type.

  • Example data from an instructor relation instance:

    • $(10101, \text{Srinivasan}, \text{Comp. Sci.}, 65000)$

    • $(12121, \text{Wu}, \text{Finance}, 90000)$

    • $(15151, \text{Mozart}, \text{Music}, 40000)$

    • $(22222, \text{Einstein}, \text{Physics}, 95000)$

    • $(32343, \text{El Said}, \text{History}, 60000)$

    • $(33456, \text{Gold}, \text{Physics}, 87000)$

    • $(45565, \text{Katz}, \text{Comp. Sci.}, 75000)$

    • $(58583, \text{Califieri}, \text{History}, 62000)$

    • $(76543, \text{Singh}, \text{Finance}, 80000)$

    • $(76766, \text{Crick}, \text{Biology}, 72000)$

    • $(83821, \text{Brandt}, \text{Comp. Sci.}, 92000)$

    • $(98345, \text{Kim}, \text{Elec. Eng.}, 80000)$

Relation Schema and Database Architecture

• Relation Schema

  • Let $A_1, A_2, \dots, A_n$ be attributes.

  • A relation schema $R$ is defined as $R = (A_1, A_2, \dots, A_n)$.

  • Example: $\text{instructor} = (\text{ID}, \text{name}, \text{dept\_name}, \text{salary})$.

• Relation Instance

  • A relation instance $r$ defined over schema $R$ is denoted by $r(R)$.

  • The current values of a relation are specified in a table format.

  • An element $t$ of relation $r$ is a tuple (row).

• Database Schema vs. Instance

  • Database Schema: The logical structure of the database.

  • Database Instance: A snapshot of the data in the database at a specific instant in time.

• Physical vs. Logical Schemas

  • Physical Schemas: Describe the database design at the physical level, representing how data are actually stored on media.

  • Logical Schemas: Describe the design at the logical level, specifying what data are stored and the relationships between them.

Attributes and Properties of Relations

• Attribute Domains

  • The domain is the set of allowed values for each attribute.

  • Attribute values are required to be atomic (indivisible).

  • The special value null is a member of every domain, indicating that a value is "unknown."

  • The use of null values complicates the definition of operations.

• Unordered Nature

  • Relations are inherently unordered; the storage order of tuples is irrelevant.

Keys in Relational Databases

• Superkeys

  • Let $K \subseteq R$.

  • $K$ is a superkey if the values for $K$ are sufficient to identify a unique tuple in every possible relation $r(R)$.

  • Example: For the instructor relation, both $\{\text{ID}\}$ and $\{\text{ID}, \text{name}\}$ are superkeys.

• Candidate Keys

  • A superkey $K$ is a candidate key if it is minimal (no subset of $K$ is also a superkey).

  • Example: $\{\text{ID}\}$ is a candidate key for instructor.

• Primary Keys

  • One candidate key is selected as the primary key to uniquely identify tuples.

• Foreign Keys

  • A foreign key is a primary key from another table.

  • The referencing relation contains the foreign key, which points to the referenced relation.

  • Example: dept_name in the instructor table is a foreign key referencing the department table (where dept_name is the primary key).

  • Foreign Key Constraint: A value in the referencing relation must appear in the referenced relation.

University Database Examples

• Classroom Relation

  • Attributes: building, room_number, capacity.

  • Data examples: $\text{(Packard, 101, 500)}$, $\text{(Painter, 514, 10)}$, $\text{(Taylor, 3128, 70)}$, $\text{(Watson, 100, 30)}$, $\text{(Watson, 120, 50)}$.

  • Note: Multiple buildings may have identical room numbers.

• Department Relation

  • Attributes: dept_name, building, budget.

  • Data examples: $\text{(Biology, Watson, 90000)}$, $\text{(Comp. Sci., Taylor, 100000)}$, $\text{(Elec. Eng., Packard, 80000)}$, $\text{(Finance, Painter, 120000)}$, $\text{(History, Painter, 50000)}$, $\text{(Music, Packard, 80000)}$, $\text{(Physics, Watson, 70000)}$.

• Section Relation

  • Attributes: course_id, sec_id, semester, year, building, room_number, time_slot_id.

• Takes Relation

  • Attributes: ID, course_id, sec_id, semester, year, grade.

  • Data examples: $\text{(12345, CS-101, 1, Fall, 2009, A)}$, $\text{(98988, BIO-101, 1, Summer, 2009, A)}$.

Relational Query Languages

• Classification

  • Procedural: User specifies how to compute the result (e.g., Java, C++).

  • Non-procedural / Declarative: User specifies what data is needed without describing how to get it (e.g., SQL).

  • Non-procedural languages simplify query specification and allow query optimizers to determine the most efficient evaluation path.

  • Procedural languages are more powerful for complex computations that are difficult or impossible to express non-procedurally.

• Pure Languages

  • Relational Algebra

  • Tuple Relational Calculus

  • Domain Relational Calculus

  • These three are equivalent in computing power but are not Turing-machine equivalent.

Relational Algebra: Basic Operations

Relational algebra consists of six fundamental operations used to manipulate relations.

• Search/Find Operation (Selection)

  • Notation: $\sigma_p(r)$, where $p$ is the search predicate.

  • Purpose: Returns tuples that satisfy predicate $p$.

  • Supported Comparisons: $=$, $\neq$, $>$, $\geq$, $<$, $\leq$.

  • Logical Connectives: $\land$ (and), $\lor$ (or), $\neg$ (not).

  • Example 1: Find instructors in the Physics department: $\sigma_{\text{dept\_name}=\text{"Physics"}}(\text{instructor})$.

  • Example 2: Find instructors in Physics with salary > 90,000: $\sigma_{\text{dept\_name}=\text{"Physics"} \land \text{salary}>90000}(\text{instructor})$.

  • Example 3: Find departments where the name is the same as the building name: $\sigma_{\text{dept\_name}=\text{building}}(\text{department})$.

• Project Operation

  • Notation: $\Pi_{A_1, A_2, \dots, A_k}(r)$.

  • Purpose: A unary operation that returns the argument relation with specific attributes excluded.

  • Behavior: Columns not listed are erased. Duplicate rows are removed because relations are treated as sets.

  • Example: Eliminate dept_name from instructor: $\Pi_{\text{ID}, \text{name}, \text{salary}}(\text{instructor})$.

• Composition of Operations

  • The result of any relational-algebra operation is also a relation.

  • Operations can be nested. Example (Find names of instructors in Physics): $\Pi_{\text{name}}(\sigma_{\text{dept\_name}=\text{"Physics"}}(\text{instructor}))$

• Cartesian-Product Operation

  • Notation: $r \times s$.

  • Purpose: Combines information from two relations by constructing a tuple for every possible pair of tuples from the two relations.

  • Naming: If an attribute name exists in both relations (e.g., ID), they are prefixed with the original relation name: $\text{instructor.ID}$, $\text{teaches.ID}$.

• Join Operation

  • Notation: $r \bowtie_\theta s$.

  • Definition: Combines Cartesian product and Selection: $r \bowtie_\theta s = \sigma_\theta(r \times s)$.

  • Purpose: Filters the Cartesian product to show only relevant associated data (e.g., matching IDs).

  • Example: $\sigma_{\text{instructor.id}=\text{teaches.id}}(\text{instructor} \times \text{teaches})$ is equivalent to $\text{instructor} \bowtie_{\text{instructor.id}=\text{teaches.id}} \text{teaches}$.

• Union Operation

  • Notation: $r \cup s$.

  • Requirements for validity:

    1. Relations $r$ and $s$ must have the same arity (number of attributes).

    2. Attribute domains must be compatible (e.g., types match column-by-column).

  • Example: Find courses taught in Fall 2017 OR Spring 2018: $\Pi_{\text{course\_id}}(\sigma_{\text{semester}=\text{"Fall"} \land \text{year}=2017}(\text{section})) \cup \Pi_{\text{course\_id}}(\sigma_{\text{semester}=\text{"Spring"} \land \text{year}=2018}(\text{section}))$

• Set-Intersection Operation

  • Notation: $r \cap s$.

  • Purpose: Finds tuples present in both relations.

  • Requirements: Compatibility (same arity and compatible domains).

  • Example: Courses taught in both Fall 2017 AND Spring 2018: $\Pi_{\text{course\_id}}(\sigma_{\text{semester}=\text{"Fall"} \land \text{year}=2017}(\text{section})) \cap \Pi_{\text{course\_id}}(\sigma_{\text{semester}=\text{"Spring"} \land \text{year}=2018}(\text{section}))$

• Set-Difference Operation

  • Notation: $r - s$.

  • Purpose: Finds tuples in the first relation that are not in the second.

  • Requirements: Compatibility (same arity and compatible domains).

  • Example: Courses taught in Fall 2017 but NOT in Spring 2018: $\Pi_{\text{course\_id}}(\sigma_{\text{semester}=\text{"Fall"} \land \text{year}=2017}(\text{section})) - \Pi_{\text{course\_id}}(\sigma_{\text{semester}=\text{"Spring"} \land \text{year}=2018}(\text{section}))$

Assignment and Rename Operations

• Assignment Operation

  • Notation: $\leftarrow$.

  • Purpose: Stores parts of a relational-algebra expression in temporary variables, similar to programming.

  • Example:

    • $\text{Physics} \leftarrow \sigma_{\text{dept\_name}=\text{"Physics"}}(\text{instructor})$

    • $\text{Music} \leftarrow \sigma_{\text{dept\_name}=\text{"Music"}}(\text{instructor})$

    • $\text{Physics} \cup \text{Music}$

• Rename Operation

  • Notation: $\rho$.

  • Purpose: Assigns a name to the result of an expression or specific attributes.

  • Expression forms:

    • $\rho_x(E)$: Returns expression $E$ under the name $x$.

    • $\rho_{x(A_1, A_2, \dots, A_n)}(E)$: Renames the result to $x$ and the attributes to $A_1, \dots, A_n$.

Query Equivalency

A query can often be written in multiple ways in relational algebra. Equivalent queries produce identical results on any database instance.

• Example 1: Selection order

  • Query 1: $\sigma_{\text{dept\_name}=\text{"Physics"} \land \text{salary}>90000}(\text{instructor})$

  • Query 2: $\sigma_{\text{dept\_name}=\text{"Physics"}}(\sigma_{\text{salary}>90000}(\text{instructor}))$

• Example 2: Selection with Join

  • Query 1: $\sigma_{\text{dept\_name}=\text{"Physics"}}(\text{instructor} \bowtie_{\text{instructor.ID}=\text{teaches.ID}} \text{teaches})$

  • Query 2: $(\sigma_{\text{dept\_name}=\text{"Physics"}}(\text{instructor})) \bowtie_{\text{instructor.ID}=\text{teaches.ID}} \text{teaches}$