123 4NF

Informally, Fourth Normal Form, or 4NF, says that independent multi-valued facts should not be combined into one relation merely because they concern the same key.

Example which violates 4NF

The following relation records the skills and languages known by a student:

Assume the following multi-valued dependencies hold. Here ↠ denotes a multi-valued dependency:

• {student} ↠ {skill} because each student has a set of skills
• {student} ↠ {language} because each student has a set of languages

For a given student, the skills and languages are independent many-valued facts. The rows for Alice contain every combination of her skills and languages, even though knowing Logic and speaking French are separate facts. The same modelling mistake can be written in Predica:

entity StudentCapability
{
    String student;
    String skill;
    String language;

    key {student, skill, language};
}

Here the independent many-valued facts have been combined into one entity type.

Writing the dependency as a constraint

If the model is left in this shape, the multi-valued dependencies have to be imposed over the containing collection of capability records. One way to write the constraint is to say that for any two rows for the same student, the recombined row must also exist:

entity School
{
    StudentCapability capability*;

    constraints
    {
        capability.(student, skill, language).Σ =
        (
            capability.(student, skill)
            ⊓ capability.(student, language)
        ).Σ;
    }
}

This constraint says that the stored StudentCapability records must be closed under recombining skills and languages for the same student. The equality says that the stored ternary relation is exactly the join of its two binary projections. It is non-local because the representation stores a Cartesian product of independent facts instead of storing each student's skills and languages as separate predicate extensions.

Fixing the violation

The fix is to represent the two independent many-valued facts separately. In relational form, this decomposes the original relation into two relations:

In Predica, the same repair is to give the student two separate attributes with many-valued extensions:

entity Student
{
    String name;
    String skill*;
    String language*;

    key {name};
}

entity School
{
    Student student*;
}

The attributes skill and language still have singular types. Their multiplicity is represented by separate attribute extensions, so Predica does not need to manufacture the Cartesian product of skills and languages.

This repair is different from the 2NF, 3NF, and BCNF examples. There the problem was a fact stored too high up, and the fix was to introduce a more specific domain. Here the problem is an unnecessary combination of independent many-valued facts. The fix is to keep those facts as separate attributes of their common subject.

This is one of the places where Predica's treatment of attribute extensions is especially useful. Independent multiplicities can remain independent predicates. They do not have to be forced into a combined relation unless the combinations themselves are meaningful facts.