A functional dependency is a design claim: once you know one fact, another fact is forced. It is not an observation that happened to hold in three rows of a spreadsheet. That distinction lets us ask whether a relation stores one fact once or repeats it under many keys.
For a relation schema and attribute sets the functional dependency
holds when every legal instance of has this property: any two tuples that agree on also agree on is the determinant; is determined by it.
For a relation schema and attribute sets the functional dependency
holds when every legal instance of has this property: any two tuples that agree on also agree on is the determinant; is determined by it.
Begin with a domain rule, not a table pattern
Assume a cloud platform assigns exactly one node IP and one network port to each service instance identified by (cluster_id, service_name, instance_id).
Worked example. In
Instance(cluster_id, service_name, instance_id, node_ip, port), the stated scheduling rule makes(cluster_id, service_name, instance_id)determinenode_ipandport. It does not say thatportdeterminesnode_ip: different instances can use the same port number across different nodes.
Counterexample. A sample in which every row has a different
service_fqdndoes not prove The domain name may be unmapped, aliased, or dynamically routed unless the infrastructure configuration declares and enforces it as a unique identifier. Dependencies come from the legal domain, ideally backed by a key or explicit policy.
Prediction: spot the unsupported dependency
The first three rows of a telemetry table all show datacenter = 'us-east' and operator = 'ops-team-a'. May you infer What extra domain rule would make it valid?
HintExpandCollapse
A dependency must survive every future legal row, not merely the current sample.
Worked solutionExpandCollapse
No. Another service or cluster can be maintained by another operator in the same datacenter. The dependency would be valid only under a much stronger rule such as “the platform assigns exactly one operator to every cluster in every datacenter,” which is not the intended domain.
Compute closure as a trace
Attribute closure answers: starting with attributes what attributes can the dependency set force? Let
To calculate begin with and add only a right side whose left side is already present.
| Step | Available attributes | Dependency enabled | New attribute |
|---|---|---|---|
| Start | — | — | |
| 1 | |||
| 2 | |||
| 3 |
So The order of enabled steps can vary; the final closure cannot, provided you keep applying dependencies until none adds an attribute.
Why the trace is justifiedExpand proofCollapse
Each step preserves equality on the starting attributes. If two tuples agree on A, forces agreement on B; agreement on B forces C; agreement on both C and D forces E. Thus any two tuples agreeing on A,D agree on every attribute in the closure.
Try the closure tool
Choose seed attributes, fire each dependency only when its determinant is available, and compare your trace to the displayed closure. Use A,D after trying a smaller seed such as A.
Build an attribute closure one justified step at a time
The dependency set is A → B, B → C, and CD → E. Pick a seed, then try to fire only dependencies whose left-hand attributes are present.
Closure
{ }
Proof trace
- Nothing has been assumed or derived yet.
Model scope: dependencies are semantic rules over every legal instance of one relation. A closure proves implication only relative to the stated dependency set and attribute universe; it does not establish that a business rule is true.
For seed {A, D}, apply A → B, B → C, then CD → E.
AD⁺ = {A, B, C, D, E}
Static state: AD is a key for the five-attribute universe because the closure reaches every attribute.
Apply closure to a real key question
Let TaskAllocation(task_id, service_name, cluster_id, node_ip, port) have the dependency
Is (task_id, service_name, cluster_id) a candidate key under this dependency set? Show the closure and the minimality check.
HintExpandCollapse
The proposed attributes already include three columns; use the dependency to add the remaining two, then try removing one attribute at a time.
Worked solutionExpandCollapse
Its closure starts with task_id, service_name, cluster_id and adds node_ip, port, so it is a superkey. Removing task_id cannot identify which individual task allocation is meant. Removing service_name or cluster_id prevents the given dependency from identifying the assigned node and port. Under the stated dependency set, it is a candidate key. A different domain rule, such as an immutable UUID, can produce an additional candidate key.
Derive dependencies without hand-waving
Three sound inference rules are enough for many small derivations.
| Rule | Form | Example |
|---|---|---|
| Reflexivity | If then | |
| Augmentation | If then | implies |
| Transitivity | If and then | implies |
Worked example. From and derive by transitivity. With derive by augmentation. In the earlier closure, these steps explain why
A,Dcan eventually enable —first it gainsB, thenC.
Check a derivation
Given can be derived? Can be derived?
HintExpandCollapse
Compute the two closures separately. A dependency can fire only when all determinant attributes are available.
Worked solutionExpandCollapse
so cannot be derived. gains B from then C from so it contains C,D and gains E from Therefore is derivable.
Reduce a dependency set before using it
A minimal cover gives a compact equivalent set of dependencies. It is a tool for reasoning, not a claim that the compact version is easier for every reader to understand.
Split the right side: and Then follows from and so remove it. AB → C follows from because B is already part of AB, so remove it too. A minimal cover is
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 2.1.1: Attribute Closure Computation
Given schema and functional dependency set compute the attribute closures and Conclude which of the dependencies or is logically implied by
HintExpandCollapse
Apply Armstrong's axioms or the attribute closure algorithm iteratively until no new attributes can be added.
Worked solutionExpandCollapse
because no dependency in has determinant subset therefore is not implied. For start with adds yielding adds yielding adds yielding Since is logically implied by
Exercise 2.1.2: Armstrong Axiom Soundness and Reversal Fallacy
An engineer observes that in the current service catalog snapshot every display_name is associated with exactly one service_id. Explain why inferring from this snapshot is unsound under Definition 2.1.1
HintExpandCollapse
Functional dependencies express invariant constraints across all legal instances, not coincidental properties of a single snapshot.
Worked solutionExpandCollapse
A functional dependency is a semantic assertion that must hold across all legal instances admitted by the domain. Observing unique display names in one snapshot does not preclude registering distinct services under the same human-readable label (e.g. Edge Proxy) in future regional or versioned deployments. Inferring confuses temporary instance data with an invariant domain constraint.
Exercise 2.1.3: Canonical Minimal Cover Derivation
Compute a canonical minimal cover for Show each reduction step: right-hand side decomposition, extraneous attribute elimination, and redundant dependency removal.
HintExpandCollapse
Decompose into singleton right sides, test determinants for extraneous attributes, then test each FD for redundancy.
Worked solutionExpandCollapse
- Decompose right-hand sides:
- Check extraneous attributes: In since holds, is extraneous; the dependency reduces to (a duplicate).
- Check redundant dependencies: In computing under yields showing is transitive and redundant. The minimal cover is
Exercise 2.1.4: Multi-Region Service Endpoint Dependency Redesign
A routing table currently claims The platform introduces multi-region deployments (e.g. production traffic in us-east on 10.0.1.5 and in eu-west on 10.0.2.8). Provide a counterexample instance refuting the dependency, specify a revised relation schema with grain ‘one regional service endpoint’, and state its valid functional dependency.
HintExpandCollapse
A single service now has multiple regional deployments. The determinant must incorporate the region.
Worked solutionExpandCollapse
Counterexample tuples: (auth-svc, prod, us-east, 10.0.1.5) and (auth-svc, prod, eu-west, 10.0.2.8). Both share but differ in violating the functional dependency.
Revised schema: with grain ‘one regional endpoint for a deployed service’. Assuming a service has exactly one primary ingress host per region in an environment, the valid dependency is