“Store cluster allocations” is not a schema. First decide what one row is allowed to assert. Then make the database reject row combinations that would contradict that assertion.
A relation schema names attributes and their domains, such as Allocation(tenant_id, cluster_id, status). A relation instance is the current collection of tuples permitted by that schema and its constraints. The grain states what one tuple represents.
A relation schema names attributes and their domains, such as Allocation(tenant_id, cluster_id, status). A relation instance is the current collection of tuples permitted by that schema and its constraints. The grain states what one tuple represents.
Build one small schema carefully
We will model a tenant allocating compute resources in a cluster during a deployment lifecycle.
| Relation | Grain | Candidate key | Required checks |
|---|---|---|---|
Tenant(tenant_id, display_name) | One identified tenant | tenant_id | tenant_id is non-null and unique |
Cluster(cluster_id, cluster_name, region, capacity) | One managed compute cluster | cluster_id | capacity >= 0 |
Allocation(tenant_id, cluster_id, status) | One tenant’s current resource allocation on one cluster | (tenant_id, cluster_id) | Both IDs refer to existing rows; status is an allowed value |
The three relations and their identifying keys, with every reference from Allocation to its parents:
Figure 1. The allocation grain: one Allocation tuple asserts one tenant’s current resource state on one Cluster. The composite key (tenant_id, cluster_id) makes two rows for the same pair illegal regardless of status, and the two foreign keys confine each allocation to existing parent rows.
Worked example: declare the schema, then watch it reject rows
Given Tenant = {(t17, 'Acme Corp')} and Cluster = {(c3, 'prod-east', 'us-east-1', 30)}, declare the schema and attempt four inserts:
CREATE TABLE Allocation (
tenant_id text NOT NULL REFERENCES Tenant(tenant_id),
cluster_id text NOT NULL REFERENCES Cluster(cluster_id),
status text NOT NULL
CHECK (status IN ('active', 'queued', 'released')),
PRIMARY KEY (tenant_id, cluster_id)
);
-- Input rows, one statement per attempt:
INSERT INTO Allocation VALUES ('t17', 'c3', 'active'); -- accepted
INSERT INTO Allocation VALUES ('t17', 'c3', 'released'); -- rejected: duplicate key (t17, c3)
INSERT INTO Allocation VALUES ('t99', 'c3', 'active'); -- rejected: no Tenant row t99
INSERT INTO Allocation VALUES ('t17', 'c9', 'active'); -- rejected: no Cluster row c9
The second statement fails with a unique-violation on the composite primary key: changing status does not create a new current-allocation fact, because status is not part of the key. The third and fourth fail foreign-key checks because each NOT NULL reference must match an existing key value in its parent. Which statement fails first for the second row—the key check or a check constraint—is not fixed by the relational model; a constraint set only has to reject the row.
Prediction: what is illegal?
Assume Allocation has primary key (tenant_id, cluster_id), and tenant_id and cluster_id are non-null foreign keys.
tenant_id | cluster_id | status |
|---|---|---|
t17 | c3 | active |
t17 | c3 | released |
t99 | c3 | active |
Which rows can coexist if only t17 and c3 exist?
HintExpandCollapse
Check the composite key first, then each foreign key.
Worked solutionExpandCollapse
Only the first row (t17, c3, 'active') can exist. The second row duplicates the existing candidate key (t17, c3), while the third references absent tenant t99 in violation of foreign key integrity.
Keys identify, foreign keys connect
A superkey is a set of attributes that uniquely identifies a tuple in every legal instance. A candidate key is a minimal superkey: remove any one of its attributes and it no longer identifies tuples. A primary key is a chosen candidate key. (Ramakrishnan & Gehrke, Database Management Systems, 3rd ed., §3.2.1.)
A superkey is a set of attributes that uniquely identifies a tuple in every legal instance. A candidate key is a minimal superkey: remove any one of its attributes and it no longer identifies tuples. A primary key is a chosen candidate key. (Ramakrishnan & Gehrke, Database Management Systems, 3rd ed., §3.2.1.)
For Allocation, (tenant_id, cluster_id) is a candidate key under the stated rule. (tenant_id, cluster_id, status) is a superkey but not a candidate key because status is unnecessary for identity. (tenant_id, status) is not even a superkey: a tenant may hold the same status across two different clusters, so it does not uniquely identify a tuple.
A declared constraint must hold at its check point. By default SQL checks each constraint immediately, after every statement that could violate it. A constraint declared DEFERRABLE INITIALLY DEFERRED is checked at commit instead; the transaction may transiently violate it. Deferring never weakens the constraint—it only changes when the database checks it.
A declared constraint must hold at its check point. By default SQL checks each constraint immediately, after every statement that could violate it. A constraint declared DEFERRABLE INITIALLY DEFERRED is checked at commit instead; the transaction may transiently violate it. Deferring never weakens the constraint—it only changes when the database checks it.
Worked example (deferred check point). Constraint: “
Cluster.regionis referenced by allocations and each cluster keeps astandby_cluster_idforeign key to a backup cluster.” Swapping two clusters’standby_cluster_idvalues with twoUPDATEstatements transiently breaks referential integrity if the constraint is immediate. Declaring itDEFERRABLE INITIALLY DEFERREDlets both updates commit only if, at commit, every referencedstandby_cluster_idexists. Committing with the violation still fails—deferral moves the check, never removes it.
Counterexample (UNIQUE is not “no duplicates” in general). The SQL standard leaves
UNIQUEtreatment of multipleNULLs to the implementation; PostgreSQL’s default (NULLS DISTINCT) treatsNULLs as mutually distinct, soUNIQUE(email)admits unlimited rows withemail IS NULL. Only PostgreSQL 15’sUNIQUE NULLS NOT DISTINCTcollapses them. Claiming “UNIQUEforbids duplicates” without saying how the vendor treatsNULLis a falsifiable error a reviewer can check against the vendor’s own constraint documentation.
Counterexample.
display_namemight look unique in a three-row sample, but two tenants can share it. An observed sample pattern is not an architectural invariant. Declare aUNIQUEconstraint only when the domain truly requires uniqueness, and say whichNULLtreatment you are relying on.
Identity versus connection
An allocation row stores tenant_id and cluster_id forming a composite primary key (tenant_id, cluster_id). Evaluate each claim:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Relation semantics versus everyday SQL tables
The mathematical relational model treats a relation as a set of tuples. SQL is deliberately more complicated in practice.
| Question | Pure set relation | Typical SQL behavior to account for |
|---|---|---|
| Can equal tuples appear twice? | No | Tables and SELECT results can contain duplicate row values unless a constraint or DISTINCT removes them |
| Is there a built-in row order? | No | No order is guaranteed without ORDER BY |
| Can an attribute be missing? | Classical model has a value in its domain | SQL has NULL; predicates can evaluate to UNKNOWN |
NULL is not an ordinary value. In a WHERE condition, only TRUE retains a row. FALSE and UNKNOWN both remove it. Therefore WHERE gateway_ip <> '10.0.0.1' does not retain a row whose gateway_ip is NULL: the comparison is UNKNOWN, not TRUE.
NULL is not an ordinary value. In a WHERE condition, only TRUE retains a row. FALSE and UNKNOWN both remove it. Therefore WHERE gateway_ip <> '10.0.0.1' does not retain a row whose gateway_ip is NULL: the comparison is UNKNOWN, not TRUE.
Worked example. Suppose two allocation rows project to the same
regionafter joining with clusters.SELECT region ...can return the region twice;SELECT DISTINCT region ...returns it once. Neither query is universally “more relational”—the right one depends on whether the client wants distinct regions or allocation occurrences.
From requirements to a legal instance
Schema review starts by separating facts from presentation.
Every constraint has a scope. A key constrains rows of one relation. A foreign key constrains a reference across relations. A view controls a presented shape. None automatically proves an aggregate policy such as “at most capacity allocated.”
Every constraint has a scope. A key constrains rows of one relation. A foreign key constrains a reference across relations. A view controls a presented shape. None automatically proves an aggregate policy such as “at most capacity allocated.”
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 1.2.1: Candidate Key and Referential Integrity Validation
Consider Tenant(tenant_id, display_name), Cluster(cluster_id, cluster_name, region, capacity), and Allocation(tenant_id, cluster_id, status) with primary key (tenant_id, cluster_id). Suppose only tenant t17 and cluster c3 exist in the database. Examine these candidate rows: (t17, c3, 'active'), (t17, c3, 'released'), and (t99, c3, 'active'). Which rows can legally coexist?
HintExpandCollapse
Check the composite key first, then each foreign key.
Worked solutionExpandCollapse
The first row can exist. The second conflicts with the same composite primary key, even though its status differs. The third violates the tenant_id foreign key because t99 has no matching Tenant row. A history requirement needs a different key and grain; changing status alone does not create a new current-allocation fact.
Exercise 1.2.2: Narrowest Constraint Domain Selection
For each requirement, specify the narrowest SQL constraint that directly enforces it: (1) A cluster cannot have negative capacity; (2) A tenant cannot appear twice in the same current allocation; (3) Every allocation names an existing cluster; (4) A status must be active, queued, or released.
HintExpandCollapse
Use a check for a predicate, a key for identity, and a foreign key for a cross-relation reference.
Worked solutionExpandCollapse
Use CHECK (capacity >= 0), a primary or unique key on (tenant_id, cluster_id), a foreign key from Allocation.cluster_id to Cluster.cluster_id, and a check constraint or controlled ENUM status domain. These constraints do not by themselves enforce multi-row capacity limits; that requires transaction-aware isolation.
Exercise 1.2.3: Set vs. Bag Projection Semantics
If an Allocation relation contains two different tenants allocated on cluster prod-east, what does projecting onto cluster_name produce under pure relational set semantics versus SQL bag semantics? Explain how to align the result grain with application intent.
HintExpandCollapse
Projection removes attributes. Decide whether equal remaining tuples collapse.
Worked solutionExpandCollapse
With set semantics, the projection has one tuple prod-east. With bag semantics, it has two occurrences of prod-east. The source relation’s grain was one allocation; a result whose grain is one cluster should normally use DISTINCT deliberately rather than inherit duplicate behavior accidentally.
Exercise 1.2.4: Multi-Pool Cluster Allocation Schema Specification
A cloud infrastructure platform offers the same cluster tier across multiple resource pools in one region (prod-tier in us-east-1, pools pool-a and pool-b). Design a revised Cluster and Allocation schema. State the grain and candidate key of each relation, provide one row combination your constraints reject, and describe how allocation queuing priority is formally modeled.
HintExpandCollapse
Cluster name is no longer enough to identify a resource pool. Keep the allocation fact separate from the cluster pool fact.
Worked solutionExpandCollapse
One sound solution is Cluster(cluster_id, tier, region, pool, capacity) with candidate key cluster_id and unique constraint UNIQUE(tier, region, pool), plus Allocation(tenant_id, cluster_id, status) with composite key (tenant_id, cluster_id). The schema rejects duplicate allocations for the same tenant in one pool and rejects non-existent clusters. Queue ordering requires an explicit ranking attribute such as queue_rank with a partial uniqueness constraint.
References & Further Reading
- E. F. Codd, “A Relational Model of Data for Large Shared Data Banks,” Communications of the ACM 13(6), pp. 377–387 (1970) — relational vocabulary, relations vs. implementation. ACM DOI · IBM Research page
- Ramakrishnan & Gehrke, Database Management Systems, 3rd ed. (McGraw-Hill, 2003) — §3.2.1 superkeys and candidate keys; §3.1 relation schema and instance; §3.4 integrity constraints over instances.
- PostgreSQL, “Constraints,” Current Documentation ch. 5 — unique constraints (including the
NULLS DISTINCTdefault), check constraints, foreign keys, and deferrable check points. - PostgreSQL, “Queries,” Current Documentation ch. 7 —
DISTINCTduplicate elimination, sorting rows (ORDER BY), andLIMITwithoutORDER BY. - PostgreSQL, “Comparison Functions and Operators” —
NULLcomparisons andIS NULL.