Database systems · Chapter 3 · The relational database model · Study guide
A short, plain summary of every term you need from Chapter 3. Each entry is a definition and the one or two facts that usually get asked about: keys, integrity rules, the data dictionary, functional dependence, and the relational algebra operations SQL is built on.
Two branches of mathematics the relational model borrows from, and the formal name for what a table actually is.
Set theory is the branch of mathematics that studies collections of distinct objects with no inherent order. Codd built the relational model on it: a table is a set of rows, which is exactly why the relational algebra operators UNION, INTERSECT, and DIFFERENCE are just the ordinary set operations applied to rows instead of numbers. Predicate logic is the branch that studies statements which are true or false depending on the values plugged into them. It is what makes a query condition possible: a clause like balance > 0 is a predicate, and evaluating it against every row is exactly what SELECT does. Together the two give the relational model both its structure, tables as sets, and its way of asking questions, conditions as predicates.
A relvar, short for relation variable, is the formal term for a named object that holds a relation, in practice a table. The distinction matters in theory because a relvar is the container, named once when the table is created, while the relation itself is the current set of rows sitting inside it at a given moment; the same relvar holds a different relation after every insert or delete. In everyday use the word table covers both ideas, but relvar is the term Chapter 3 uses when it needs to say the container rather than the contents.
Every key in this chapter answers the same question, what makes a row unique, except one, which exists purely to help you find rows fast.
A key is one or more attributes that determine other attributes: knowing the key's value tells you everything else in the row. A superkey is any attribute, or combination of attributes, that uniquely identifies each row in a table; it may contain extra attributes that are not actually needed for uniqueness. A candidate key is a superkey with the excess trimmed off, a minimal superkey, meaning that removing any one attribute from it would destroy its uniqueness. A table can have several candidate keys; a driver's license number and a social security number might both uniquely identify an employee. Any single attribute that is part of a key, whether that key is a primary, candidate, secondary, or foreign key, is called a key attribute.
The primary key (PK) is the candidate key selected by the designer to uniquely identify every row in the table; once chosen it cannot contain a null value in any row, that rule is entity integrity, covered next. A composite key is a primary, candidate, or foreign key made up of two or more attributes, needed whenever no single column is unique on its own, for example an order line identified only by the pair order number and product number together. A secondary key is different in kind rather than degree: it is an attribute or combination used strictly to retrieve data, such as searching invoices by customer last name, and it is not expected to be unique, a search on it can legitimately return several rows.
Entity integrity protects a table from itself; referential integrity protects a table from what other tables say about it.
A foreign key (FK) is an attribute, or attribute combination, in one table whose values must either match a primary key value in another table or be null. Entity integrity is the rule that every table must have a primary key and that no part of that primary key may ever be null, which guarantees every row can always be told apart from every other row. Referential integrity is the rule governing the foreign key itself: its value must either match an existing primary key value in the referenced table, or be null, so a query can never be pointed at a row that does not exist.
A null is the absence of any data value; it means the value is unknown, not applicable, or not yet entered, and it is not the same thing as zero or a blank string, both of which are actual values. Nulls are exactly what referential integrity permits in a foreign key and exactly what entity integrity forbids in a primary key. A domain, also called an attribute domain, is the set of all possible values a given attribute is allowed to hold, for example whole numbers from 1 to 5, or the two values true and false. Two attributes are said to share a domain when they draw from the same set of legal values, which is exactly the requirement behind union-compatibility, covered later in this page.
An index speeds up one table. The data dictionary and system catalog describe every table.
An index is an ordered arrangement, maintained by the RDBMS, that is used to access rows quickly based on the values of one or more columns, the same idea as a book's index letting you skip straight to a page instead of reading cover to cover. The index key is the column, or columns, the index is built on. A unique index is an index built on a column where every value must be distinct, so it both speeds up lookups and enforces a uniqueness constraint at the same time; a primary key is automatically backed by a unique index.
The data dictionary is a comprehensive description of every table in the database: its structure, the meaning of each attribute, its data type and domain, and the constraints and relationships attached to it. It is the database's metadata, data about the data. The system catalog is a detailed, system level data dictionary that the RDBMS itself creates, maintains, and queries automatically every time SQL runs, storing information such as table names, column names and types, index names, and access rights. In practice the two terms describe the same information at two levels: the data dictionary is the concept, and the system catalog is the RDBMS's live, queryable implementation of it.
Three small vocabulary hazards a data dictionary exists partly to prevent.
A homonym is the use of the same attribute name to mean two different things in two different places, for example a type column that means product category in one table and payment method in another; it is confusing and should be avoided or renamed. A synonym is the opposite problem, using two different attribute names to describe the very same thing, for example customer_id in one table and cust_no in another; it makes it harder to see that a relationship even exists. Flags are special values, often a short code or a true or false indicator, placed in an attribute's domain to signal that a row meets some condition an application needs to check, such as a reorder flag on inventory that trips once quantity on hand drops below a threshold.
| Term | The problem | Example |
|---|---|---|
| Homonym | One name, two different meanings | type meaning category in PRODUCT, meaning method in PAYMENT |
| Synonym | Two names, one meaning | customer_id and cust_no for the same attribute |
| Flag | Not a naming problem, a domain design choice | a reorder_flag that turns on at low stock |
A many to many relationship cannot be built directly. These four terms are how it gets built anyway.
A composite entity, also called an associative entity or a bridge entity, is used to transform a many to many relationship into two one to many relationships that a relational database can actually implement. It is composite because its primary key is typically built from the primary keys of the two entities it connects, an example of a composite key. Chen notation calls it an associative entity because it associates two entities while also holding its own attributes, such as a grade or an enrollment date; the term bridge entity emphasizes its structural role, spanning the gap an M:N relationship leaves. Once it is actually created as a table, it is commonly called a linking table, the implementation level name for the same object.
The relationship a primary key has with every other attribute in its row, stated precisely enough to test.
Functional dependence means that the value of one attribute depends on, and is uniquely determined by, the value of another: for a given value of A there is exactly one associated value of B. When that holds, A is written A → B, read as "A determines B." The attribute doing the determining, A, is the determinant; the attribute being determined, B, is the dependent; and determination is simply the name for that determinant to dependent relationship itself. A primary key is, by definition, a determinant of every other attribute in its table.
Full functional dependence only becomes a meaningful question when the determinant is a composite key. An attribute displays full functional dependence, meaning it is fully functionally dependent, when it depends on the entire composite key and not on just part of it. In an ENROLL table keyed on {stu_id, class_code}, the grade depends on both parts together, that enrollment's grade in that specific class, so grade is fully dependent on the composite key. If stu_lname were also stored in that same table, it would depend on stu_id alone, only part of the key, which is a partial dependency and the exact flaw full functional dependence is checked for.
Eight operations, all of them tables in, one table out. Every SQL query is built from some combination of these.
Relational algebra is a set of mathematical operations, rooted in set theory, used to manipulate one or more relations and produce a new relation as the result. Codd defined eight of them: SELECT, PROJECT, JOIN, PRODUCT, UNION, INTERSECT, DIFFERENCE, and DIVIDE. They are the theoretical foundation SQL sits on: every SQL statement can be rewritten, at least in principle, as a combination of these eight operations, which is exactly why SQL feels consistent even though its syntax hides the underlying algebra. Every one of the eight takes relations in and hands a relation back, never anything else, a property called closure. Closure is what makes the algebra usable in practice: because the output of one operation is itself a relation, it can be fed straight into the next operation as input, which is exactly how a nested query, a subquery, or a view built on another view is able to work.
SELECT yields the rows that satisfy a given predicate, a horizontal subset of a table; because SQL later claimed the word SELECT for an entire query, the relational algebra operation is also called RESTRICT to keep the two from being confused. PROJECT yields the values for a chosen set of attributes, a vertical subset of a table, discarding the rest of the columns and any resulting duplicate rows.
UNION combines all rows from two tables into one, automatically dropping any duplicate rows. INTERSECT keeps only the rows that appear in both tables. DIFFERENCE keeps the rows that appear in the first table but not in the second, so order matters, A DIFFERENCE B is not the same as B DIFFERENCE A. All three require the two tables to be union-compatible: they must have the same number of attributes, and each corresponding pair of attributes must draw from the same, or a compatible, domain.
PRODUCT, short for Cartesian product, yields every possible combination of rows from two tables, pairing each row of the first with every row of the second; a table with 2 rows PRODUCT a table with 3 rows produces 6 rows. It is rarely useful on its own, but it is the operation a JOIN is built from: a join is a PRODUCT followed by a SELECT that keeps only the pairings where the join columns match. DIVIDE answers a for all question: given a two column table and a single column table, it returns the values from the two column table's first column that are paired with every single value listed in the one column table, for example which students have completed every course in a required list.
One operation, several dialects, depending on which rows survive when a match cannot be found.
JOIN combines rows from two or more tables into a single result table based on a common attribute; it is what makes it possible to store customer data once and invoice data separately, then bring them back together only when a query needs both. The join columns are the attributes the join condition compares, typically a primary key in one table and the matching foreign key in the other. A natural join links tables on all columns that share the same name and value, and it drops the duplicate copy of the join column from the result, which is the join most people picture when they hear the word. An equijoin is a join whose condition uses equality, matching column, but unlike a natural join it keeps both copies of the join column in the result. A theta join is the general case: a join whose condition can use any comparison operator, not just equals, for example matching rows where one date falls before another; an equijoin is simply the theta join that happens to use the equals operator.
An inner join returns only the rows that have a match in both tables, discarding any row on either side with no counterpart, natural join and equijoin are both inner joins. An outer join keeps rows even when they have no match on the other side, filling in the missing columns with null so unmatched rows are not lost. A left outer join keeps every row from the left, or first listed, table, matched where possible and null-padded where not; a right outer join does the same thing for the right, or second listed, table.