Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Schema design and SQL practice
Page 5 of 20

Functional dependencies: state what determines a fact

Use functional dependencies, closure, and minimal covers to expose keys and update anomalies from domain rules—not from a lucky sample.

Lesson briefSchema design and SQL practice · 8 h · 3 outcomes

Required knowledge

  • Relation grain, candidate keys, and constraints
  • Sets, subset reasoning, and proof by a short derivation

Learning outcomes

  • State a functional dependency as a claim about every legal instance and distinguish it from a sampled correlation.
  • Compute an attribute closure and use it to test whether an attribute set is a superkey or candidate key.
  • Simplify a small dependency set while preserving its implications.

Assessment target

Given a relation, business rules, and a proposed determinant, compute a closure, justify a candidate key, and repair one dependency claim that is unsupported by the domain.

Scope boundary

  • Multivalued dependencies, join dependencies, and automated dependency discovery are outside this course foundation.

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.

Definition 2.1.1Functional dependency

For a relation schema RR and attribute sets X,Y⊆RX, Y \subseteq R the functional dependency

X→YX \to Y

holds when every legal instance of RR has this property: any two tuples that agree on XX also agree on YY XX is the determinant; YY 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).

(cluster_id,service_name,instance_id)→(node_ip,port)(cluster\_id, service\_name, instance\_id) \to (node\_ip, port)

Worked example. In Instance(cluster_id, service_name, instance_id, node_ip, port), the stated scheduling rule makes (cluster_id, service_name, instance_id) determine node_ip and port. It does not say that port determines node_ip: different instances can use the same port number across different nodes.

Counterexample. A sample in which every row has a different service_fqdn does not prove service_fqdn→service_idservice\_fqdn \to service\_id 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 datacenter→operatordatacenter \to operator What extra domain rule would make it valid?

HintExpand

A dependency must survive every future legal row, not merely the current sample.

Worked solutionExpand

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 XX what attributes can the dependency set force? Let

F={A→B,  B→C,  CD→E}.F = \{A \to B,\; B \to C,\; CD \to E\}.

To calculate AD+AD^+ begin with {A,D}\{A,D\} and add only a right side whose left side is already present.

StepAvailable attributesDependency enabledNew attribute
StartA,DA,D——
1A,DA,DA→BA \to BBB
2A,B,DA,B,DB→CB \to CCC
3A,B,C,DA,B,C,DCD→ECD \to EEE

So AD+={A,B,C,D,E}AD^+ = \{A,B,C,D,E\} 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 proof

Each step preserves equality on the starting attributes. If two tuples agree on A, A→BA \to B 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.

Interactive exploration

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.

Choose a determinant, then begin its closure.
Seed attributes

Closure

{ }

Proof trace

  1. 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.

Build an attribute closure one justified step at a time

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

(service_name,cluster_id)→(node_ip,port).(service\_name, cluster\_id) \to (node\_ip, port).

Is (task_id, service_name, cluster_id) a candidate key under this dependency set? Show the closure and the minimality check.

HintExpand

The proposed attributes already include three columns; use the dependency to add the remaining two, then try removing one attribute at a time.

Worked solutionExpand

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.

RuleFormExample
ReflexivityIf Y⊆XY \subseteq X then X→YX \to YAB→AAB \to A
AugmentationIf X→YX \to Y then XZ→YZXZ \to YZA→BA \to B implies AD→BDAD \to BD
TransitivityIf X→YX \to Y and Y→ZY \to Z then X→ZX \to ZA→BA \to B B→CB \to C implies A→CA \to C

Worked example. From A→BA \to B and B→CB \to C derive A→CA \to C by transitivity. With A→BA \to B derive AD→BDAD \to BD by augmentation. In the earlier closure, these steps explain why A,D can eventually enable CD→ECD \to E—first it gains B, then C.

Check a derivation

Given F={A→B,B→C,CD→E}F = \{A \to B, B \to C, CD \to E\} can D→ED \to E be derived? Can AD→EAD \to E be derived?

HintExpand

Compute the two closures separately. A dependency can fire only when all determinant attributes are available.

Worked solutionExpand

D+={D}D^+ = \{D\} so D→ED \to E cannot be derived. AD+AD^+ gains B from A→BA \to B then C from B→CB \to C so it contains C,D and gains E from CD→ECD \to E Therefore AD→EAD \to E 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.

F={A→BC,  B→C,  AB→C}.F = \{A \to BC,\; B \to C,\; AB \to C\}.

Split the right side: A→BA \to B and A→CA \to C Then A→CA \to C follows from A→BA \to B and B→CB \to C so remove it. AB → C follows from B→CB \to C because B is already part of AB, so remove it too. A minimal cover is {A→B,B→C}\{A \to B, B \to C\}

Section Exercises

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

Constructionapplication

Given schema R(A,B,C,D,E)R(A, B, C, D, E) and functional dependency set F={A→B,B→C,CD→E}F = \{A \to B, B \to C, CD \to E\} compute the attribute closures D+D^+ and (AD)+(AD)^+ Conclude which of the dependencies D→ED \to E or AD→EAD \to E is logically implied by FF

HintExpand

Apply Armstrong's axioms or the attribute closure algorithm iteratively until no new attributes can be added.

Worked solutionExpand

D+={D}D^+ = \{D\} because no dependency in FF has determinant subset {D}\{D\} therefore D→ED \to E is not implied. For (AD)+(AD)^+ start with {A,D}\{A, D\} A→BA \to B adds BB yielding {A,B,D}\{A, B, D\} B→CB \to C adds CC yielding {A,B,C,D}\{A, B, C, D\} CD→ECD \to E adds EE yielding {A,B,C,D,E}\{A, B, C, D, E\} Since E∈(AD)+E \in (AD)^+ AD→EAD \to E is logically implied by FF

Exercise 2.1.2: Armstrong Axiom Soundness and Reversal Fallacy

Verificationrecall

An engineer observes that in the current service catalog snapshot every display_name is associated with exactly one service_id. Explain why inferring display_name→service_iddisplay\_name \to service\_id from this snapshot is unsound under Definition 2.1.1.

HintExpand

Functional dependencies express invariant constraints across all legal instances, not coincidental properties of a single snapshot.

Worked solutionExpand

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 display_name→service_iddisplay\_name \to service\_id confuses temporary instance data with an invariant domain constraint.

Exercise 2.1.3: Canonical Minimal Cover Derivation

Constructionapplication

Compute a canonical minimal cover for F={A→BC,  B→C,  AB→C}F = \{A \to BC,\; B \to C,\; AB \to C\} Show each reduction step: right-hand side decomposition, extraneous attribute elimination, and redundant dependency removal.

HintExpand

Decompose into singleton right sides, test determinants for extraneous attributes, then test each FD for redundancy.

Worked solutionExpand
  1. Decompose right-hand sides: {A→B,A→C,B→C,AB→C}\{A \to B, A \to C, B \to C, AB \to C\}
  2. Check extraneous attributes: In AB→CAB \to C since B→CB \to C holds, AA is extraneous; the dependency reduces to B→CB \to C (a duplicate).
  3. Check redundant dependencies: In {A→B,A→C,B→C}\{A \to B, A \to C, B \to C\} computing A+A^+ under {A→B,B→C}\{A \to B, B \to C\} yields {A,B,C}\{A, B, C\} showing A→CA \to C is transitive and redundant. The minimal cover is {A→B,B→C}\{A \to B, B \to C\}

Exercise 2.1.4: Multi-Region Service Endpoint Dependency Redesign

Generalisationtransfer

A routing table currently claims (service_name,environment)→host_ip(service\_name, environment) \to host\_ip 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.

HintExpand

A single service now has multiple regional deployments. The determinant must incorporate the region.

Worked solutionExpand

Counterexample tuples: (auth-svc, prod, us-east, 10.0.1.5) and (auth-svc, prod, eu-west, 10.0.2.8). Both share (service_name,environment)(service\_name, environment) but differ in host_iphost\_ip violating the functional dependency. Revised schema: RegionalEndpoint(service_name,environment,region,host_ip)RegionalEndpoint(service\_name, environment, region, host\_ip) 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 (service_name,environment,region)→host_ip(service\_name, environment, region) \to host\_ip

References & Further Reading