Chapter 8 — Relational Databases

Definition: In a relational database, a relation is a table that represents a set of tuples (rows) having the same attributes (columns). A relation is formally a subset of the Cartesian product of attribute domains.

Components and notation

• Relation schema: R(A1, A2, ..., An) — the name R and its attributes A1..An.
• Relation instance: r(R) ⊂ Dom(A1) × Dom(A2) × ... × Dom(An) — a specific set of tuples at a moment in time.
• Tuple: a single row in the relation, e.g., (v1, v2, ..., vn).
• Attribute: a column; each attribute Ai has a domain Dom(Ai) (set of allowed values).
• Degree: number of attributes (n) of the relation.
• Cardinality: number of tuples (|r|) in the relation instance.

Example relation (STUDENT)

Here degree = 4, cardinality = 3. RollNo is a primary key (unique, non-null).

Key concepts

• Domain constraint: every attribute value must be from its domain.
• Entity (primary key) constraint: primary key uniquely identifies tuples; no two tuples have same primary-key value and primary key cannot be NULL.
• Referential integrity (foreign key): a foreign key in one relation must either be NULL or match a primary key value in the referenced relation.
• Superkey / Candidate key / Primary key: A superkey is a set of attributes that uniquely identifies tuples. A candidate key is a minimal superkey. One candidate key is chosen as the primary key.
• Functional dependency: A -> B means if two tuples agree on attribute set A they must agree on attribute B (used in normalization).

Properties of relations

• Tuples (rows) are unordered; attributes (columns) are unordered.
• No duplicate tuples are allowed (set semantics).
• Attribute values are atomic (first normal form requirement).

Basic relational algebra operators (short)

• Selection: σ(condition)(R) — choose rows satisfying condition.
• Projection: π(A1, A2,...)(R) — choose columns.
• Cartesian product: R × S.
• Join: R ⋈ S (commonly equijoin or natural join).
• Union: R ∪ S, Difference: R − S, Intersection: R ∩ S.

Why relations are useful: They provide a simple, mathematical, and flexible way to represent structured data; relations + keys + constraints = reliable data storage and powerful query capability (SQL maps directly to relational concepts).

Definition: A relation in a relational database is a set of tuples (rows) having the same attributes (columns). Conceptually it is a table with a name, a heading (attributes and their domains) and a body (the set of tuples).

Main components:

• Relation name: Identifier for the relation (table) — e.g., Student, Employee.
• Heading (Schema): The list of attributes (A1, A2, ..., An) and each attribute's domain (possible values). Notation: R(A1:D1, A2:D2, ..., An:Dn).
• Attributes: Columns of the relation. Attributes are expected to be atomic values (1NF). Example attributes: StudentID, Name, DOB.
• Domains: A domain Di is the set of allowed values for attribute Ai (e.g., Integer, Date, Varchar(50)).
• Body (Instance): The current set of tuples (rows) in the relation. Each tuple assigns one value from the domain to each attribute.
• Tuple (Record): A single row of the relation: t = <v1, v2, ..., vn> where vi ∈ Di.
• Degree (Arity): Number of attributes in the relation (n).
• Cardinality: Number of tuples (rows) in the relation, usually denoted |R|.
• Primary key (Tuple identifier): One or more attributes whose values uniquely identify tuples in the relation. Enforces entity integrity (no duplicate primary-key values, no NULLs in PK).
• Foreign key: Attribute(s) that reference a primary key in another relation to enforce referential integrity.
• Null values: A special marker indicating unknown or inapplicable values; allowed but must be handled carefully for constraints and keys.

Properties of a relation (mathematical model):

• Tuples form a set — no duplicate tuples.
• Order of tuples is not significant (set semantics).
• Order of attributes is not significant for the relation as a set (though tables display an order).
• Every tuple value comes from the domain declared for that attribute.

Short example (HTML table view):

Here: relation name = Student, heading = {StudentID:Integer, Name:Varchar, DOB:Date, Major:Varchar}, degree = 4, cardinality = 2, primary key = StudentID, each row is a tuple.

Relation Schema: A relation schema is the logical description (structure) of a relation. It specifies the relation name and a list of attributes with their domains. It is a metadata-level concept and does not change frequently. Notation: R(A1, A2, ..., An) where R is the relation name and each Ai is an attribute having a domain Di.

Relation Instance: A relation instance (or relation variable instance) is a set of tuples that conform to the relation schema at a particular moment in time. An instance is the actual data — rows in a table. If R is a schema and Di are domains, an instance r of R is a subset r ⊆ D1 × D2 × ... × Dn.

Key concepts:

• Attributes: columns of the relation; each attribute has a domain (allowed values).
• Tuple: a single row in the instance; an ordered list of attribute values.
• Degree (arity): number of attributes (n) in the schema.
• Cardinality: number of tuples (|r|) in the instance.
• Primary key: a minimal set of attributes that uniquely identify a tuple in every valid instance of the relation.
• Constraints: domain constraints (values must come from attribute domains), key constraints (uniqueness), and entity-integrity (primary key values cannot be NULL).

Difference (short): Schema = structure (definition, fixed until changed by DBA). Instance = content (current set of tuples, changes frequently with insert/update/delete).

Formal view (set-theoretic): If R(A1,...,An) with domains D1,...,Dn, then any instance r of R is r ⊆ D1 × D2 × ... × Dn. Each tuple t in r is of the form (v1, v2, ..., vn) where vi ∈ Di.

Example explained: Schema Student(AdmNo, Name, Class, DOB) has degree 4. An instance might contain 200 tuples today (cardinality 200). AdmNo is the primary key — no two tuples can have the same AdmNo and it cannot be NULL. Tomorrow some students graduate, so the instance changes but the schema remains Student(AdmNo, Name, Class, DOB).

What is a Key?
A key is one or more attributes of a relation that uniquely identify a tuple (row). Keys enforce uniqueness and help establish relationships between tables in a relational database.

Core concepts and formalism

• Functional dependency: X → Y means attribute set X functionally determines attribute set Y (each value of X corresponds to exactly one value of Y).
• Superkey: Any attribute set X such that X → all attributes of the relation (i.e., X uniquely identifies tuples). A superkey may contain extra attributes.
• Candidate key: A minimal superkey (no proper subset of it is a superkey). A relation can have multiple candidate keys.
• Primary key: A candidate key chosen by database designer to be the main identifier. It must be unique and not NULL.
• Alternate key: Any candidate key that is not selected as the primary key.
• Composite (concatenated) key: A key made up of two or more attributes used together to uniquely identify tuples.
• Foreign key: An attribute (or attribute set) in one relation that references a candidate/primary key in another relation to establish referential integrity.
• Surrogate key: An artificial key (often system-generated, e.g., an auto-increment integer) used as the primary key when no natural key is convenient.

Properties

• Uniqueness: Key values must be unique across tuples.
• Minimality (for candidate keys): No subset of a candidate key should be able to uniquely identify tuples.
• Non-nullability (usually for primary keys): Primary key attributes should not be NULL.
• Referential integrity: A foreign key value must either match an existing primary key value in the referenced relation or be NULL (if allowed).

How to check a key (practical steps)

1. Identify functional dependencies between attributes.
2. Compute the attribute closure X+ for candidate sets X (attributes determined by X using dependencies).
3. If X+ includes all attributes of the relation, X is a superkey. If no proper subset of X is a superkey, X is a candidate key.

Short example (conceptual)
For relation Student(SID, RollNo, Name, DOB, Email):

• SID → all attributes (if SID is unique) so SID is a superkey; if no subset of SID (itself single attribute) is a superkey then SID is a candidate key and can be chosen as primary key.
• {RollNo, Branch, Year} might together be a composite key if RollNo alone is not unique across branches/years.
• In an Enrollment relation Enrollment(EnrollID, StudentSID, CourseID): StudentSID is a foreign key referring to Student(SID).

Why keys matter: Keys ensure data integrity, enable fast lookup/indexing, and define relationships between tables for joins and referential constraints.

Integrity Constraints are rules applied to a relational database to ensure accuracy, consistency and validity of the data. They prevent invalid or inconsistent data from being stored and enforce business rules at the database level.

Main types of integrity constraints:

• Domain Constraint: Each attribute (column) has a domain — a set of permissible values (data type, length, allowed range or format). Example: age INT CHECK (age BETWEEN 0 AND 120).
• Entity Integrity: No primary key (PK) value can be NULL. Every row must be uniquely identifiable. Example: in a Student table, roll_no PRIMARY KEY, roll_no cannot be NULL.
• Key Constraints:
  • Superkey: A set of attributes that uniquely identifies a tuple.
  • Candidate key: Minimal superkey (no proper subset is a superkey).
  • Primary key: A chosen candidate key; unique and NOT NULL.
  • Alternate key: Candidate keys not chosen as primary.
  • Composite key: A key made of two or more attributes.
• Referential Integrity: A foreign key (FK) in a child table must either be NULL (if allowed) or match a primary key value in the parent table. This keeps relationships consistent. Example: order.customer_id must exist in customer.customer_id.
• CHECK Constraints and Business Rules: Custom conditions that rows must satisfy, e.g., CHECK (salary >= 0) or CHECK (start_date <= end_date).

How constraints are enforced: At INSERT, UPDATE and DELETE operations. The DBMS checks constraint rules and rejects operations that would violate them. Referential actions may be specified (ON DELETE CASCADE, ON UPDATE SET NULL) to manage dependent rows when parent rows change.

Why they matter: Integrity constraints maintain data quality, reduce application-level checks, prevent anomalies, and preserve correct relationships between tables.

Short SQL examples:

CREATE TABLE Student (
  roll_no INT PRIMARY KEY,
  name VARCHAR(50) NOT NULL,
  age INT CHECK (age BETWEEN 3 AND 100)
);

CREATE TABLE Department (
  dept_id INT PRIMARY KEY,
  dept_name VARCHAR(40)
);

CREATE TABLE Employee (
  emp_id INT PRIMARY KEY,
  name VARCHAR(50),
  dept_id INT,
  FOREIGN KEY (dept_id) REFERENCES Department(dept_id) ON DELETE SET NULL
);

Relational algebra is a procedural query language that operates on relations (tables). It provides a set of basic operations that produce new relations from existing ones. These operations form the theoretical foundation for SQL and relational databases.

Basic operations (with purpose and syntax):

• Selection (σ) — selects rows that satisfy a condition. Syntax: σ_condition(R). Example: σ_city='Delhi'(Students) returns all student tuples with city = 'Delhi'. Selection is row-oriented and preserves all attributes.
• Projection (π) — selects specified columns (attributes) and removes duplicates. Syntax: π_attr1,attr2,...(R). Example: π_name,roll_no(Students) returns only the name and roll_no columns.
• Union (∪) — combines tuples from two relations with the same schema, removing duplicates. Syntax: R ∪ S. Both relations must have the same set of attributes (compatible).
• Set Difference (−) — tuples in R that are not in S. Syntax: R - S. Schema must match.
• Intersection (∩) — tuples common to both relations. Can be derived: R ∩ S = R - (R - S). Syntax: R ∩ S.
• Cartesian Product (×) — pairs every tuple of R with every tuple of S, producing combined attributes. Syntax: R × S. Use carefully — result size = |R| * |S|.
• Theta Join and Natural Join
  • Theta-join: R ⋈_θ S = σ_θ(R × S) — join with a general condition θ (e.g., R.id = S.rid).
  • Natural join (⋈): matches and merges tuples on all common attribute names, eliminating duplicate columns. Syntax: R ⋈ S.
• Rename (ρ) — renames a relation or its attributes. Syntax: ρ_newName(oldRelation) or ρ_newAttrList(R). Useful to avoid name clashes before joins.
• Division (÷) — used for queries like “find X that relate to all Y”. If R(A,B) and S(B), then R ÷ S returns all a in A such that for every b in S, (a,b) ∈ R. Syntax: R ÷ S.

Typical properties and useful identities (used to optimize or rewrite expressions):

• Selection is commutative: σ_p(σ_q(R)) = σ_q(σ_p(R)) = σ_{p ∧ q}(R).
• Projection is idempotent: π_L(π_L(R)) = π_L(R). Order of projections matters if attribute lists differ.
• Union and intersection are commutative and associative: R ∪ S = S ∪ R; (R ∪ S) ∪ T = R ∪ (S ∪ T), similarly for ∩.
• Cartesian product distributes over union: R × (S ∪ T) = (R × S) ∪ (R × T).
• Theta-join as selection on Cartesian product: R ⋈_θ S = σ_θ(R × S).

Why these operations matter: they allow expression of all common queries — filtering, column selection, combining tables, and expressing “for all” conditions (division). They are the algebraic building blocks behind SQL's SELECT-FROM-WHERE constructs.

Overview
Relational algebra provides a set of basic operations (selection, projection, union, difference, Cartesian product, rename) to query relations. 'Additional operations' are derived operators built from the basic ones to express common queries more conveniently: intersection, natural join, theta join, division, outer joins (left, right, full) and rename (as a formal operator). Each has a precise meaning and can be implemented using basic operators.

1. Intersection (R ∩ S)
Definition: Tuples that are present in both relations R and S. Both relations must be union-compatible (same attributes and domains).
Intuition: R ∩ S = R − (R − S).

2. Natural Join (R ⋈ S)
Definition: Combine tuples from R and S that have equal values on all common attributes; the common attributes appear once in the result. Natural join implicitly performs a Cartesian product followed by selection on equality of common attributes then projection to remove duplicate common columns.
Intuition: Join student and enrollment tables on StudentID to get student details with their courses.

3. Theta Join (R ⋈_{θ} S)
Definition: General join where tuples from R and S are combined when predicate θ (any comparison) holds between attributes of R and S (e.g., R.A > S.B). Natural join is a special case where θ is equality on all common attributes.

4. Division (R ÷ S)
Definition: Given R(X, Y) and S(Y) where Y attributes are a subset of R’s attributes, R ÷ S returns the set of X-values such that for every tuple y in S, the tuple (x,y) is in R. Used to answer 'for all' queries (e.g., students who have taken all required courses).
Intuition: Find suppliers who supply all parts listed in S.

5. Outer Joins (Left ⟕, Right ⟖, Full ⟗)
Definition: Like natural join but preserve unmatched tuples from one or both sides by padding NULLs for missing attributes. Left outer join keeps all tuples from R and matches from S (NULLs if no match). Right outer join keeps all from S. Full outer join keeps all tuples from both relations.

6. Rename (ρ)
Definition: Renames a relation or its attributes, used to avoid name conflicts or to make intermediate results referable. Syntax: ρ_NewName(Relation) or ρ_NewName(attr1,attr2,...)(Relation).

Why these matter (CBSE context)
These additional operations let you express common database questions succinctly: intersection for common membership, joins to combine related information, division for 'for all' queries, outer joins to retain unmatched rows (useful in reports), and rename to keep expressions clear. Each can be explained and implemented using the basic operations, which reinforces understanding of relational algebra's completeness.

Overview

In relational databases, joins and set operations are ways to combine rows from two (or more) relations (tables).

Joins combine tuples from different tables based on a related column (usually a key). They produce a result that typically contains columns from both input tables. Joins are implemented in SQL using the JOIN clause (or by listing tables in FROM with a WHERE condition).

• Inner Join (Equi-join): Returns rows that have matching values in both tables. SQL: SELECT ... FROM A INNER JOIN B ON A.key = B.key;
• Natural Join: A join on all columns with the same names in both tables. It implicitly matches those columns and removes duplicate columns in the result. Use with care because it depends on column names.
• Theta Join: A join with an arbitrary condition (e.g., A.x > B.y). General form is A ⋈_{condition} B.
• Cross Join (Cartesian Product): Every row of A paired with every row of B. SQL: SELECT ... FROM A CROSS JOIN B; or FROM A, B (without WHERE).
• Outer Joins: Preserve non-matching rows from one or both tables by padding missing columns with NULLs.
  • Left Outer Join: All rows from left table + matching rows from right table; non-matches have NULL for right-side columns. SQL: FROM A LEFT JOIN B ON ...
  • Right Outer Join: All rows from right table + matching rows from left table.
  • Full Outer Join: All rows from both tables; non-matches padded with NULLs.
• Self Join: A table joined with itself using aliases — useful for hierarchical or pairwise comparisons.

Set operations treat whole rows as set elements and combine the results of two queries (usually requiring the same number of columns and compatible types):

• UNION: All distinct rows that appear in either result. SQL: Q1 UNION Q2. Removes duplicates by default.
• UNION ALL: Like UNION but preserves duplicates (faster when duplicate removal not needed).
• INTERSECT: Rows common to both results. SQL: Q1 INTERSECT Q2.
• EXCEPT / MINUS: Rows in the first result but not in the second. SQL dialects differ: SQL Server and standard SQL use EXCEPT, Oracle uses MINUS. Example: Q1 EXCEPT Q2.

Important rules for set operations:

• Both queries must return the same number of columns.
• Corresponding columns must have compatible data types (can be implicitly converted or of same domain).
• Column names in the final result come from the first query (Q1) in many systems.
• UNION/INTERSECT/EXCEPT remove duplicates by default; use ALL suffix to keep duplicates (where supported).

Connection to relational algebra

• Join in relational algebra is often written as A ⋈_{condition} B. Natural join is A ⋈ B (matching attributes). Cartesian product: A × B.
• Set operations correspond to algebraic set ops: ∪ (union), ∩ (intersection), − (difference).

Practical notes

• Use INNER JOIN when you need only matching rows; use LEFT/RIGHT/FULL OUTER JOIN when you need to retain non-matching rows from one or both sides.
• Prefer explicit JOIN ... ON syntax over comma-separated tables with WHERE — it is clearer and less error-prone.
• Be careful with NATURAL JOIN and SELECT * with joins: column name collisions can produce unexpected results.

Overview: Relational database design organizes data into relations (tables) so the information is stored efficiently, without unnecessary redundancy, and supports correct querying and updates. Good design uses functional dependencies, keys and normalization to eliminate anomalies (insertion, update, deletion) while preserving data integrity.

Key concepts

• Relation: A table with rows (tuples) and columns (attributes).
• Functional dependency (FD): For attributes X and Y of a relation R, X → Y means that if two tuples agree on X they must agree on Y.
• Key: An attribute or minimal set of attributes that uniquely identifies a tuple (candidate key). A chosen candidate key is the primary key.
• Closure (X+): The set of all attributes functionally determined by X given a set of FDs; used to test keys.
• Decomposition: Splitting a relation into two or more relations to remove redundancy while aiming for lossless join and dependency preservation.

Anomalies

• Insertion anomaly: Cannot add valid data because other required data is missing. Example: cannot add a new course if a student record is required for the table design.
• Deletion anomaly: Deleting a row removes other valuable information. Example: deleting the last student enrolled in a course removes the course information entirely.
• Update anomaly: Multiple copies of the same information require multiple updates; inconsistency can result if all copies aren't changed.

Normalization (common normal forms)

• 1NF (First Normal Form): All attribute values are atomic (no repeating groups or arrays).
• 2NF (Second Normal Form): Relation is in 1NF and every non-prime attribute is fully functionally dependent on the whole of every candidate key (no partial dependency on a part of a composite key).
• 3NF (Third Normal Form): Relation is in 2NF and there is no transitive dependency of a non-prime attribute on a key. Formally, for each FD X → A, either X is a superkey or A is a prime attribute (part of some candidate key).
• BCNF (Boyce–Codd Normal Form): For every non-trivial FD X → Y, X must be a superkey (stronger than 3NF).

Decomposition properties

• Lossless-join decomposition: Decomposing R into R1 and R2 is lossless if R1 ∩ R2 → R1 or R1 ∩ R2 → R2 (the common attributes functionally determine one of the components).
• Dependency preservation: After decomposition, it should be possible to enforce all original FDs using constraints on the decomposed relations (not always possible with BCNF).

Design process (practical steps)

1. List attributes and identify candidate keys using attribute closures (X+).
2. List functional dependencies by analyzing semantics of data.
3. Apply normalization rules: remove partial dependencies (to reach 2NF), remove transitive dependencies (to reach 3NF), and consider BCNF when necessary.
4. Check each decomposition for lossless join and try to preserve dependencies.

Why this matters (summary): Proper relational design reduces redundancy, avoids anomalies, improves integrity and makes queries and updates reliable and efficient. In practice you balance normalization with performance (sometimes denormalize for speed).

Definition: A functional dependency (FD) X -> Y between two sets of attributes X and Y of a relation R means: for any two tuples t1 and t2 in R, if t1[X] = t2[X] then t1[Y] = t2[Y]. X functionally determines Y, so X uniquely determines the values of Y.

Notation & basic idea: X -> Y (read ‘X determines Y’). If X is a candidate key, then X -> all attributes of R.

Types of functional dependencies:

• Trivial FD: Y ⊆ X, e.g. (A,B) -> A.
• Non-trivial FD: Y ⊄ X, e.g. A -> B where B is not in A.
• Fully functional dependency: Y depends on whole of X and not on any proper subset of X. Example: (A,B) -> C is full if neither A -> C nor B -> C holds.
• Partial dependency: Some proper subset of a composite key determines Y. Example: (A,B) -> C but A -> C holds → partial dependency.
• Transitive dependency: X -> Y and Y -> Z implies X -> Z (indirect). Example: StudentID -> DeptID and DeptID -> HOD implies StudentID -> HOD.

Why it matters: FDs capture redundancy and are the basis for normalization (2NF, 3NF, BCNF). They help identify keys and determine safe decompositions.

Key concepts & procedures:

• Closure of an attribute set (X+): The set of all attributes functionally determined by X given a set of FDs. Used to test if X is a key (if X+ includes all attributes of R).
• Armstrong's axioms (sound & complete rules to infer FDs):
  • Reflexivity: If Y ⊆ X then X -> Y.
  • Augmentation: If X -> Y then XZ -> YZ for any Z.
  • Transitivity: If X -> Y and Y -> Z then X -> Z.
• Additional useful rules: Union (if X -> Y and X -> Z then X -> YZ), Decomposition (X -> YZ implies X -> Y and X -> Z), Pseudotransitivity.
• Minimal cover (canonical cover): A minimal equivalent set of FDs where: right sides are single attributes, extraneous attributes removed from left sides, and no FD is redundant.

How to compute X+ (algorithm): Start with X+ = X. Repeatedly add attributes B to X+ whenever there is an FD Y -> B with Y ⊆ X+. Stop when no more attributes can be added.

Relation to keys: X is a superkey iff X+ contains all attributes of the relation. X is a candidate key if it is a minimal superkey (no proper subset of X is a superkey).

Normalization role: Use FDs to decompose relations to eliminate undesirable dependencies (partial/transitive) and reduce redundancy while preserving data and dependencies when possible.

What is normalization? Normalization is a systematic process in relational database design that organizes tables to reduce redundancy and eliminate undesirable anomalies (insertion, update, deletion). It uses functional dependencies (FDs) and keys to decompose relations into well-structured smaller relations while preserving data and dependencies when possible.

Key concepts

• Functional dependency (FD): X → Y means attribute set X functionally determines attribute Y.
• Superkey / Candidate key / Primary key: A superkey uniquely identifies a tuple. A candidate key is a minimal superkey. One candidate key is chosen as the primary key.
• Partial dependency: In a relation with a composite key, an attribute is partially dependent if it depends on part of the key (violates 2NF).
• Transitive dependency: A → B and B → C implies A → C transitively; if A is key and C is non-prime this can violate 3NF.
• Decomposition properties: Lossless-join (no spurious tuples) and dependency preservation (able to enforce FDs on decomposed tables).

Normal forms (common ones studied in Class 12)

• 1NF (First Normal Form): All attributes contain atomic (indivisible) values; no repeating groups or arrays in a single column.
• 2NF (Second Normal Form): Table is in 1NF and every non-prime attribute is fully functionally dependent on the whole of every candidate key (i.e., no partial dependencies).
• 3NF (Third Normal Form): Table is in 2NF and there are no transitive dependencies of non-prime attributes on candidate keys. Formal condition: for every FD X → A, either X is a superkey or A is a prime attribute (part of some candidate key).
• BCNF (Boyce–Codd Normal Form): Stronger than 3NF. For every non-trivial FD X → A, X must be a superkey.

Why normalize? To avoid:

• Update anomalies: multiple places to change the same data.
• Insertion anomalies: inability to add data without extra unrelated data.
• Deletion anomalies: loss of needed information when deleting tuples.

How to normalize (high-level steps)

1. List attributes and determine all functional dependencies.
2. Find candidate keys (use attribute closure X+ to test).
3. Check 1NF, then 2NF (remove partial dependencies by decomposing), then 3NF (remove transitive dependencies), and if necessary BCNF.
4. Ensure decompositions are lossless and try to preserve dependencies.

Notes: BCNF may break dependency preservation even though it is lossless. Practical design often aims for 3NF with dependency preservation and lossless decomposition.