Schema design: entity-relationship modelling and normalisation

The first unit asked what a fact is. A schema is usually judged by its shape against a normal form, and that test is too weak for the decision it carries. This second unit asks where each named fact is written down. A normal form says how many places the fact is written down, and which of those places may correct it. Normalisation is a theory of what a fact is and where it lives.

The claim has two halves. Denormalising is sound when a single write path owns each duplicated copy and the read path that justifies the copy has been measured. When either fails, the duplication is debt, and the repayment is reconciliation work nobody scheduled.

Naming the things decides what can be stored

Chen (1976) proposed the entity-relationship model to incorporate important semantic information about the real world, and the diagrammatic technique introduced with it is the tool offered for design. The paper draws out implications for data integrity, retrieval and manipulation, and offers the model as a basis for unifying the network, relational and entity-set views. Naming entities and relationships before any storage code exists is a design act, and the diagram records it.

Chen (1983) examines how English sentence structure maps onto entity-relationship diagrams. He uses the correspondence to guide how entities, relationships and attributes are told apart. A model should use the words its users use, because a fact never named as a value cannot be constrained later. Teorey, Yang and Fry (1986) carry naming into a procedure. They conceptualise in an extended entity-relationship model, decompose it into basic constructs, transform those into candidate relations, and then normalise. Elmasri and Navathe (2016) give the same passage at textbook length, and it is the consensus the argument presupposes.

A normal form is a claim about a fact, not a shape

Kent (1983) sets out the five principal normal forms in simple terms, and he avoids the dependency theory behind them. One fact must not be recordable in two places, and each new form widens what counts as the same fact. Fagin (1977) makes that widening formal. He defines multivalued dependencies, which include functional dependencies as a special case. He uses them to define fourth normal form, and he proves it strictly stronger than Boyce-Codd normal form. He also proves every schema decomposes into fourth normal form without loss of information. Redundancy can hide where functional dependencies cannot see.

Fagin (1981) ties the definition to its purpose. He defines domain-key normal form on domains, keys and constraints rather than on traditional dependencies. He formalises insertion and deletion anomalies, and proves a schema is in DK/NF exactly when it has neither. Normalisation is an argument that a fact has one home, and it stands or falls with whether the anomaly it names can occur.

A worked case shows the mechanism. One table holds student, module and tutor together: student id and name, module code and title, tutor id and office. Each module determines its title and tutor, and each tutor determines one office. A tutor who moves office must then be updated in every enrolment row for that tutor. If the update misses a single row, the same tutor holds two offices, and the database records both without complaint. Splitting the table into a student relation, a module relation, a tutor relation and an enrolment relation of keys alone removes the duplication. The case is constructed to exhibit the insertion and deletion anomaly Fagin (1981) formalises, and it measures no workload, so it does not by itself decide whether a particular denormalisation pays.

Deriving a schema is a bounded search, not a mechanical rewrite

Bernstein (1976) presents an effective procedure that synthesises a schema from a set of functional relationships. He proves the result is in third normal form and contains the fewest possible relations. Maier (1980) shows that a minimum cover of functional dependencies can be found in polynomial time, contrary to the widespread belief that the problem is NP-complete.

Beeri and Bernstein (1979) define the price. They give a tree model of dependency derivations, a linear-time test for dependency membership and a quadratic-time implementation of Bernstein's synthesis algorithm. They then show that most questions about Boyce-Codd normal form and keys are NP-complete. The boundary between the tractable and the intractable runs through the task, which is why some steps became tools and others stayed the work of whoever owns the schema.

The conditions under which duplication is sound

The normal-form account is not the whole literature, and the strongest case for denormalising comes from the side that made it standard. Kimball and Ross (2013) treat dimensional modelling as the right shape for analytical read paths, and they denormalise into star schemas. That is a design position rather than a measured effect, because the read path it serves is where a normalised join is felt.

What makes it defensible is that the reconciliation is a studied engineering problem rather than an accident. Gupta and Mumick (1999) motivate materialised views. They give a taxonomy of view-maintenance problems by view class, resource used, modification type and generality, and describe the literature's techniques against it. A duplicated, precomputed relation carries an ongoing reconciliation obligation that can be designed and bounded, which is the condition the argument adds.

A schema is never designed once

The second condition is that the read path be measured, and the reason lies in what a schema costs after it ships. Rahm and Bernstein (2001) survey automatic schema matching, the problem of finding correspondences between elements of heterogeneous schemas. They classify the approaches by the level at which a matcher works and by whether it reads language or constraints. Matching, reconciling and reusing schemas are recurring operations with their own literature, and that literature has moved: Liu and colleagues (2025) match schemas by retrieving candidate columns with a small language model and reranking them with a large one.

Curino, Moon and Zaniolo (2008) state the cost directly. Web information systems have made schema change frequent, while tolerance for downtime has nearly disappeared. Evolution stays error-prone because the administrator lacks the tools to predict a change's effects or migrate the data. Their PRISM workbench is a first step, and it expresses changes as schema modification operators.

Contested question: is denormalisation debt or design?

The literature disagrees, and the disagreement is about what a schema is for. One position defines a good schema by the anomalies it excludes. Fagin (1977) proves that redundancy exists which functional dependencies cannot see. Fagin (1981) ties a normal form to the absence of a named insertion or deletion anomaly. Kent (1983) supplies the plain statement that one fact belongs in one place. Here a duplicated copy is a defect by construction, and measurement is beside the point.

The second position defines a good schema by the workload it serves. Kimball and Ross (2013) denormalise into star schemas for analytical read paths and defend the trade in maintenance effort against query simplicity. Here the normalised schema is the one that costs time, because the joins it forces are paid on every query rather than once at design.

A third position refuses the choice and asks for the accounting. Gupta and Mumick (1999) show that maintaining a duplicated relation is a designed process. Curino, Moon and Zaniolo (2008) show that schema change remains error-prone and frequent. If both costs land in maintenance, the question is which maintenance is bounded. What would settle it is a study that measures, for one workload, the query cost of the denormalised shape against the total reconciliation cost of its duplicated copies. That count would include view maintenance and schema change together with the code held outside the database.

Rate each side by its evidence. Fagin (1977) and Fagin (1981) prove properties of a schema, and Kent (1983) states the definitions, so the anomaly side rests on proof rather than on measurement. Kimball and Ross (2013) argue from worked practice, a design position rather than a measured effect. Gupta and Mumick (1999) survey the maintenance problem instead of measuring it. The strongest objection is that a proof against redundancy needs no workload, so asking the dimensional case for a measurement applies a standard the normal forms never had to meet. While the dispute is open, a designer names who owns the reconciliation of each duplicated copy and records the read path it serves.

Where the argument is heading

The direction the named work points to is the schema as a versioned artefact with its change accounted for. Curino, Moon and Zaniolo (2008) expect schema evolution to stay the pressing problem while the frequency of change rises, and they offer tooling for predicting a change's effects. Rahm and Bernstein (2001) show that matching and merging schemas already have a literature of their own. The question to carry forward is whether the reconciliation that justifies a duplicated copy can become a measured, automated part of design, or stays a promise the next schema change has to keep.

The sources this unit rests on

• Beeri, C. and Bernstein, P. A. (1979). The authors give a tree model of dependency derivations, a linear-time membership test and a quadratic-time implementation of Bernstein's synthesis algorithm, and show that most questions about Boyce-Codd normal form and keys are NP-complete. It sets the computational price of design, which makes schema design a bounded search. The results assume stated dependencies, not measured practice.
• Bernstein, P. A. (1976). Bernstein presents an effective procedure that synthesises a relational schema from a set of functional relationships, proves the result is in third normal form and holds the fewest possible relations, and reviews earlier attempts. It makes schema derivation possible, not only schema checking, and covers functional dependencies alone rather than the multivalued and join dependencies that later forms require.
• Chen, P. P. (1976). Chen proposes the entity-relationship model and introduces the diagrammatic technique that became standard for design. The model carries semantic information about the real world and is offered as a basis for unifying the network, relational and entity-set views. It is a model proposal, so it establishes expressive adequacy rather than a measured outcome.
• Chen, P. P. (1983). Chen examines how English sentence structure maps onto entity-relationship diagrams, using the correspondence to guide how entities, relationships and attributes are told apart. It supplies the labelling half of design, on which a model's words should track how people describe the domain. The abstract is published on the publisher's page and states that eleven translation rules are proposed; no index carried it.
• Curino, C. A., Moon, H. J. and Zaniolo, C. (2008). The authors argue that graceful schema evolution remains unsolved, that web information systems have made schema change frequent while tolerance for downtime has nearly disappeared, and present the PRISM workbench, which expresses changes as operators and predicts their effects. It treats schema change as a managed process rather than an emergency.
• Elmasri, R. and Navathe, S. B. (2016). This is the standard textbook account of entity-relationship modelling, the relational model, normalisation, indexing and query processing, with the functional-dependency apparatus behind each normal form. Only the publisher metadata was read, so it is cited for the consensus rather than a result.
• Fagin, R. (1977). Fagin defines multivalued dependencies, which include functional dependencies as a special case, and uses them to define fourth normal form. He proves the new form strictly stronger than Boyce-Codd normal form, and that every schema decomposes into fourth normal form without loss of information. Redundancy can hide where functional dependencies cannot see.
• Fagin, R. (1981). Fagin defines domain-key normal form on domains, keys and constraints rather than on traditional dependencies, formalises insertion and deletion anomalies, and proves a schema is in DK/NF exactly when it has neither. It answers what a normal form is for: one is worth having only if it excludes a named anomaly.
• Gupta, A. and Mumick, I. S. (1999). The authors motivate materialised views, give a taxonomy of view-maintenance problems by view class, resource and modification type, and describe the literature's techniques against it. It grounds the case for denormalising, because a duplicated precomputed relation carries an ongoing reconciliation obligation. It is a survey, so it organises the field rather than reporting one result.
• Kent, W. (1983). Kent sets out the concepts behind the five principal normal forms without assuming the dependency theory behind them. It is the tutorial that made the normal forms teachable, and supplies the vocabulary in which the argument about denormalisation is conducted. It reports no new results, so it supports definitions rather than evidence.
• Kimball, R. and Ross, M. (2013). This is the practitioner reference for dimensional modelling, which denormalises into star schemas for analytical workloads and defends the trade in maintenance effort against query simplicity. It carries the case from the side that made denormalisation standard. Only the publisher metadata was read, so it is cited for the position rather than a measured effect.
• Liu, Y., Pena, E. H. M., Santos, A. et al. (2025). Matches schemas by retrieving candidate columns with a small language model and reranking them with a large one, reporting higher accuracy than their baselines on six benchmarks. It is an experimental system, so its gains hold for the benchmarks it names.
• Maier, D. (1980). Maier shows that a minimum cover of functional dependencies can be found in polynomial time, contrary to the widespread belief that the problem is NP-complete, and notes that a smaller cover makes the algorithms that take one as input faster. Because some normalisation steps are tractable, dependency analysis became a tool rather than a hand method.
• Rahm, E. and Bernstein, P. A. (2001). Rahm and Bernstein survey automatic schema matching, the problem of finding correspondences between elements of heterogeneous schemas, and classify the approaches by level (schema or instance, element or structure) and by kind (language-based or constraint-based). It frames the claim that a schema is never designed once, since matching and merging are recurring operations with their own literature. The abstract is published on the publisher's page; no index carried it.
• Teorey, T. J., Yang, D. and Fry, J. P. (1986). The authors define a logical design methodology that conceptualises requirements in an extended entity-relationship model, then decomposes and transforms it into candidate relations. It shows how a conceptual model is carried into tables, as a procedure worked through examples rather than a measured outcome.