Real World: Database Schemas & Relations

Math for CS · Axiom Academy

How set theory powers every database -- from tables to joins The word "relational" in "relational database" comes directly from mathematical relations. A database table is literally a relation -- a subset of a Cartesian product of domains. Each row is an ordered tuple in . The table is a finite subset of that Cartesian product. A primary key is a set of attributes that uniquely identifies each tuple. In set theory terms, it guarantees the relation is a function from key values to rows. A foreign key connects two relations by referencing the primary key of another table. Every SQL join has a precise set-theoretic definition: INNER JOIN: R S -- Cartesian product filtered by matching keys UNION: R S -- all tuples in either relation INTERSECT: R S -- tuples in both relations EXCEPT: R S -- tuples in R but not in S Normalization organizes tables to minimize redundancy using functional dependencies -- functions in the set-theory sense. 1NF: Each cell is atomic -- the relation is a well-defined set of tuples 2NF: No non-key attribute depends on part of a composite key 3NF: No non-key attribute depends on another non-key attribute (no transitive dependencies) SQL is syntactic sugar over relational algebra -- six operations defined using set theory: Selection _ (R) : filter rows by condition (WHERE) Projection _A(R) : keep certain columns (SELECT columns) Cartesian product R S : all pairs of rows (FROM with no join) Union R S : combine rows (UNION)

This is the written version of the interactive lesson above. See the full Math for CS course.