What does it mean for a decomposition to be dependency-preserving, and what is the practical cost when a decomposition is lossless but not dependency-preserving?
answer
- every FD checkable inside one table
- union of projected FDs must imply F
- spanning FD = no UNIQUE constraint possible
- trigger or app check, read-then-write race
- 3NF always achievable both ways
basics
~20 sA decomposition is dependency-preserving when every original functional dependency can still be checked inside a single resulting table. If one spans two tables, no single-table constraint can enforce it, so every write needs a join-based check via trigger or application logic, with race conditions under concurrency.
solid answer
~50 sDecomposition has two correctness goals. Lossless-join means the pieces rejoin to the original exactly. Dependency preservation means the functional dependencies you were relying on can still be enforced locally: for each original dependency, all of its attributes sit inside one of the resulting tables, so a UNIQUE constraint on that table enforces it. When a dependency straddles two tables you lose declarative enforcement. Classic case: R(student, course, instructor) with (student, course) determining instructor and instructor determining course. Splitting into (student, instructor) and (instructor, course) is lossless but the dependency (student, course) determines instructor now spans both tables. No index can express it. The cost is real. Enforcement moves to a trigger or to application code that joins on every insert, which is slower and, under concurrency, unsafe: two transactions can each read a consistent state and jointly write a violation unless you serialize or take an explicit lock. The violation then persists silently, which is why teams often prefer a form that keeps the dependency local.
code
sql · 15 lines-- preserved: instructor -> course lives inside one table
CREATE TABLE instructor_course (
instructor varchar(100) PRIMARY KEY,
course varchar(100) NOT NULL
);
CREATE TABLE student_instructor (
student varchar(100) NOT NULL,
instructor varchar(100) NOT NULL REFERENCES instructor_course(instructor),
PRIMARY KEY (student, instructor)
);
-- NOT preserved: (student, course) -> instructor spans both tables,
-- so no UNIQUE constraint can stop a student getting two instructors
-- for the same course.go deeper
Recall the definition: after splitting, each rule should still be checkable inside one table. Depth beyond that is not expected.
State the projection-and-implication definition, contrast it with lossless-join, and give an example of a dependency that ends up spanning two tables.
Focus on enforcement cost and the read-then-write race under snapshot isolation, and describe how you would decide whether the trade is acceptable.
Treat it as an invariant-ownership decision: which rules must be engine-enforced, and accept a weaker normal form when local enforceability is worth more than the redundancy removed.
## The two goals of decomposition When you break one table into several, you want two properties. Lossless-join is about being able to reconstruct the data. Dependency preservation is about being able to keep enforcing the rules. Formally: let F be the set of functional dependencies on the original table R. Project F onto each piece, keeping only the dependencies whose attributes all live inside that piece. The decomposition is dependency-preserving if the union of those projections implies all of F. If some dependency in F cannot be derived from the local ones, it has been lost as a locally checkable rule. ## Why locality is what matters A relational engine enforces a functional dependency X determines Y by a UNIQUE constraint on X inside the table that contains both X and Y. That is cheap, exact, and, critically, concurrency-safe: uniqueness is enforced by the index at write time regardless of isolation level, so two concurrent inserts cannot both succeed. If X and Y end up in different tables, no such constraint exists. There is no portable declarative way to say this combination of columns, assembled by a join, must be unique. Enforcement has to be reconstructed. ## The classic example R(student, course, instructor) with the rules: a student takes a course from exactly one instructor, so (student, course) determines instructor; and each instructor teaches exactly one course, so instructor determines course. Because instructor determines course and instructor is not a superkey, R is not in BCNF. The BCNF decomposition is R1(student, instructor) and R2(instructor, course). It is lossless, since instructor is a key of R2. But the dependency (student, course) determines instructor spans both tables. You can now insert (Ann, Smith) and (Ann, Jones) into R1 where Smith and Jones both teach Databases, which violates a rule that the original table enforced with a simple key. ## What enforcement costs afterwards Three options, all worse than a constraint. One, a trigger that joins the tables on every insert and update and raises an error. It runs on the hot write path, it must handle every write path including bulk loads, and it is easy to get wrong on multi-row statements. Two, application-level checks, which have a read-then-write race. Two transactions each check, each sees no conflict, and both commit. Under snapshot isolation neither sees the other, so both succeed and the invariant is broken. Fixing it requires SERIALIZABLE isolation, an explicit lock on a shared row, or a uniqueness constraint on some materialized derivation of the joined value. Three, materialize the derived column back into one table so a UNIQUE constraint can cover it, which reintroduces the redundancy you decomposed to remove and needs its own synchronisation. The operational consequence of getting it wrong is that violations are silent. Nothing errors; the data simply stops satisfying a rule the rest of the system assumes, and you discover it later through inconsistent reports. ## The theory result worth knowing A decomposition that is both lossless and dependency-preserving is always achievable at Third Normal Form, via the synthesis algorithm. It is not always achievable at BCNF; the student-course-instructor table is the standard proof, since no BCNF decomposition of it preserves all dependencies. That trade-off, and which side to take, belongs to the discussion of BCNF versus 3NF; the point here is that dependency preservation is the property being traded away, and its price is paid at every write. ## How to answer Define it as the ability to check each rule inside one table, contrast it explicitly with lossless-join so the interviewer sees you keep the two straight, give the spanning-dependency example, and then talk about enforcement cost and the concurrency race. That last part is what separates a textbook answer from an engineering one.
- How would you enforce a functional dependency that spans two tables?Options are a trigger that joins on every write, an application check, or materializing the joined value into one table so a UNIQUE constraint can cover it. All three cost more than an index-enforced constraint. The application check in particular needs SERIALIZABLE isolation or an explicit lock, because two concurrent transactions can each see a valid state and jointly create the violation.
- Is a lossless decomposition that preserves all dependencies always possible?At Third Normal Form yes, the synthesis algorithm guarantees both properties. At Boyce-Codd Normal Form no; some tables have no BCNF decomposition that preserves every dependency, so you must choose between the stricter form and local enforceability. Losslessness, by contrast, is always attainable and is never the property you trade away.
saying these in an interview costs you the question
- Confusing dependency preservation with lossless-join, or claiming one implies the other
- Saying a spanning dependency can be enforced by a foreign key
- Assuming an application-level check is equivalent to a constraint, ignoring the concurrency race
- Claiming every decomposition can preserve all dependencies if you are careful enough