To be in the third normal form each non key column must depend only on the primary key

VI.E. Third Normal Form

Third normal form is based on the notion of transitive dependency. If A, B, and C are attributes of relation R, such that A → B, and B → C, then C is transitively dependent on A, unless either B or C is a candidate key or part of a candidate key. Equivalently, a transitive dependency exists when a nonprime attribute determines another nonprime attribute. A relation is in third normal form if it is in second normal form and no nonprime attribute is transitively dependent on any candidate key. In the Employee table of the company database in Figure 17, we see that deptID → deptMgr, so we have one nonprime attribute determining another. The only candidate keys for the relation are empID and SSN. This means that deptMgr is transitively dependent on empID, the primary key, since neither deptID nor deptMgr is part of any candidate key for this relation. Because of the transitive dependency, we can still have anomalies. If we have a new department with a new manager, we cannot insert this information unless we have an employee, which is an insertion anomaly. If the manager of department 10 changes from Munez to Miller, we may update one employee's record and fail to update another's in the same department, leading to an update anomaly. If we delete the record of the only employee in a department, we lose the information about the department, including the manager's name.

To correct the design, we can decompose the Employee table into

resulting in the schema shown in Figure 18. The Project and Assignment tables are already in third normal form. In the Project table, projID and projName are both candidate keys, and there are no transitive dependencies. In Assignment, only the composite {empID, projID} is a candidate key, and there are no other functional dependencies.

Third Normal Form

Third normal form is designed to handle situations like the one you just read about in the preceding section. In terms of entities, the item relation does contain two entities: the merchandise item and the distributor. That alone should convince you that the relation needs to be broken down into two smaller relations, both of which are now in third normal form:

Item (item_numb, distrib_numb)

Distributor (distrib_numb, warehouse_phone_number)

The theoretical definition of third normal form says:

The relation is in second normal form.

There are no transitive dependencies.

The functional dependencies found in the original relation are an example of a transitive dependency.

Boyce-Codd Normal Form

Third normal form, which eliminates most of the anomalies known in databases today, is the most common standard for normalization in commercial databases and computer-aided software engineering (CASE) tools. The few remaining anomalies can be eliminated by the Boyce-Codd normal form. Boyce-Codd normal form is considered to be a strong variation of 3NF.

A table R is in Boyce-Codd normal form (BCNF) if for every nontrivial FD X ->A, X is a superkey.

BCNF is a stronger form of normalization than 3NF because it eliminates the second condition for 3NF, which allowed the right side of the FD to be a prime attribute. Thus, every left side of an FD in a table must be a superkey. Every table that is BCNF is also 3NF, 2NF, and 1NF, by the previous definitions.

The following example shows a 3NF table that is not BCNF. Such tables have delete anomalies similar to those in the lower normal forms.

Assertion 1: For a given team, each employee is directed by only one leader. A team may be directed by more than one leader.

emp_name, team_name -> leader_name

Assertion 2: Each leader directs only one team.

leader_name -> team_name

The following table is 3NF with a composite candidate key (emp_name, team_name).

The team table has the following delete anomaly: If Sutton drops out of the Condors team, then we have no record of Bachmann leading the Condors team. As shown by Date (2003), this type of anomaly cannot have a lossless decomposition and preserve all FDs. A lossless decomposition requires that when you decompose the table into two smaller tables by projecting the original table over two overlapping subsets of that table, the natural join of those subset tables must result in the original table without any extra unwanted rows. The simplest way to avoid the delete anomaly for this kind of situation is to create a separate table for each of the two assertions. These two tables are partially redundant, enough so to avoid the delete anomaly. This decomposition is lossless (trivially) and preserves functional dependencies, but it also degrades update performance due to redundancy, and necessitates additional storage space. The trade-off is often worth it because the delete anomaly is avoided.

9.6 Boyce-Codd Normal Form (BCNF)

A table is in BCNF when for all nontrivial FDs (X → A), X is a superkey for the whole schema. A superkey is a unique set of columns that identify each row in a table, but you can remove some columns from it and it will still be a key. Informally, a superkey is carrying extra weight.

BCNF is the normal form that actually removes all transitive dependencies. A table is in BCNF if for all (X → Y), X is a key—period. We can go to this normal form just by adding another key with UNIQUE (room_nbr, time_period) constraint clause to the table Classes.

There are some other interesting and useful “higher” normal forms, but they are outside of the scope of this discussion. In our example, we have removed all the important anomalies with BCNF.

Third Normal Form was concerned with the relationship between key and nonkey columns. However, a column can often play both roles. Consider a table for computing each salesman's bonus gifts that has for each salesman his base salary, the number of sales points he has won in a contest, and the bonus gift awarded for that combination of salary range and points. For example, we might give a fountain pen to a beginning salesman with a base pay rate somewhere between $15,000 and $20,000 and 100 sales points, but give a car to a master salesman, whose salary is between $30,000 and $60,000 and who has 200 points. The functional dependencies are, therefore,

(pay_step, points) → gift

gift → points

Let's start with a table that has all the data in it and normalize it.

Gifts

This schema is in 3NF, but it has problems. You cannot insert a new gift into our offerings and points unless we have a salary to go with it. If you remove any sales points, you lose information about the gifts and salaries (e.g., only people in the $30,000 range can win a car). And, finally, a change in the gifts for a particular point score would have to affect all the rows within the same pay step. This table needs to be broken apart into two tables:

PayGifts

GiftsPoints

13.3.5 Third normal form

The third normal form (3NF) is based on the concept of a transitive dependency. A functional dependency X → Y in a relation R is a transitive dependency if there is a set of attributes Z that is not a subset of any key of R, and both X → Z and Z → Y hold. In this case we must split this relation into two new relations and a join between both will recover the original relation. In the case of our example, for LOTS2 there is no problem, but for LOTS1 there is a transitive dependency: Property-ID → Area, and Area → Price. So we need to change LOTS1 into (Figure 13.2c):

LOTS1A (Property-ID, County_name, Lot-ID, Area)

LOTS1B (Area, Price)

The resulting rearrangement to satisfy the three normal forms is a set of three relations as shown in Figure 13.2d.

Normalizing an Entity

There are three steps to develop a third normal form database. They are shown at a high level below, and then in further detail in the subsequent sections.

1NF—Eliminate repeating groups. Make a separate table for each set of attributes (in essence, this is creating an entity). Identify a primary key for each table. If you cannot define a primary key, then you have not split up the tables into the sets of related attributes creating an entity, and you need to repeat this step.

2NF—Eliminate redundant data stored in different entities. If an attribute depends on anything other than the primary key (could be a compound key), then remove it as a separate table.

3NF—Eliminate non-key interdependencies. If you have defined the primary key and the keys within that, then all the attributes in that entity need to be related to that key. For example, if you have customer or product, you can only have attributes that are related to the customer or the product within the entity. Otherwise, remove them and put them into a separate table, as they are most likely separate entities. With these steps completed, you have defined a 3NF schema.

4NF Correction

Some designers believe that moving a database to third normal form is sufficiently free of update anomalies and stop their design work there. Modelers on more advanced projects, however, believe it is necessary to insulate their database designs against another class of anomalies, namely multivalued dependencies, and this belief causes them to search their third normal form schemas for fourth and fifth normal form violations.

A multivalued dependency exists if the keys of a table determine not just one occurrence of the remaining values in a table but instead multiple values. Consequently, if a multivalued dependency exists in a table, we need to create more than one record to store the information associated with a given key value [Singh 2011, Chapter 10]. One disadvantage of allowing this condition to exist in a data warehouse is that additional, inter-record logic must be designed and programmed into the ETL so that all the necessary records are created each time a new set of key values is added. Such multirecord logic is difficult to specify and program correctly, and so it is a common source of vexing quality errors within a data warehouse.

Multivalue dependencies can be more difficult to spot than the first three normal-form violations because one must consider the values that can occur across several records in a table, not just the values stored on a single record. To take our model beyond third normal form, we must search it for two types of multivalued dependencies. Two or more independently varying, non-key fields lead to a fourth normal form violation. Two or more fields whose values can be determined by an exogenous reference domain, such as a control list, violate the requirements for firth normal form.

To understand the fourth normal form violation, consider Table 12.2, which shows the full domain for the Sales Channel table in the third normal form data model. Looking at this listing, the designers discovered that there is more than one way to interpret the records that it holds. With multiple interpretations possible, the sales management team may draw the wrong conclusions when it uses these records to review the company’s advertising campaigns that are running on the Internet. The ambiguity emerged when the designers asked themselves what updates to this table should the ETL make when the Ask ad manager started displaying the company’s advertisements via the OnlineDepot.com website. The company is currently running two types of promotion: “1st Free” and “2 for 1.” If the data warehouse created records for both of these promotions, as shown at the bottom of Figure 12.14, it would imply that Ask displays both types of ads on OnlineDepot.com, but perhaps that would be a false picture of reality. Ask’s ad servers may have a problem with the images used for the 2-for-1 promotions, so populating this reference table with both records will imply a counterfactual notion that Ask is fulfilling its contract obligations. Conversely, if the warehouse created a record for only 2-for-1 promotions because that is the only ad found in the sales channel monitoring system, the end users might infer that Ask has deliberately chosen not to run 1st-Free ads for the company. Perhaps it is only coincidence that has kept the 1st-Free ads from running yet, so the missing record will mislead the sales management team. The inclusion of two independently varying columns in the same table leads to insert anomalies that make it impossible to populate the table so that end users can dependably interpret its information.

Table 12.2. Insert Anomaly for the 3NF Sales Channel Table

Delete anomalies exist as well for tables violating fourth normal form. If BigBuy.com decides to block Ask as an ad server for its website, the data warehouse would have to delete all the records that contain “Ask” and “BigBuy.com” (Records 5 and 6 in Figure 12.14). Record 4 would be the only indication in the data warehouse that 2-for-1 ads are running on the BigBuy.com website. If Record 4 did not exist, then deleting Records 5 and 6 would have eliminated all knowledge of this particular combination of ads and ad sites, leading to incorrect information for the sales team. In real-life data warehouses, the number of columns and records involved with fourth normal form violations will be many times higher than the two small records here; thus, the rules for avoiding and correcting the possible update anomalies can be very difficult to specify. Multivalued dependencies also require complex ETL routines that act on more than one record per event, programming, so most veteran EDW data modelers work hard to remove them from their designs.

Correcting for a fourth normal form violation follows a similar strategy that data modelers used for the first through third normal forms: The columns involved in multivalue dependencies should be relocated into their own special-themed tables. As illustrated in Figure 12.15, a fourth normal form design will split the columns in the last model’s Sales Channel table into three separate entities: Ad Manager, Ad Site, and Promotion. Furthermore, the designers will need to add two associative tables in order to express the relationships between the records in the three entities—one for tracking relationships between ad managers and ad sites and another for links between ad manager and promotions. Table 12.3 illustrates how the rows of the original Sales Channel table would be distributed across the five new tables. With this design, only one record is needed in the first associative table to document that Ask will be running the company’s advertisements on the OnlineDepot.com website. Whether that contract supports 1st-Free or 2-for-1 promotions will be documented independently in the second associative table. The existence of an advertising contract is now decoupled from the promotion it covers so that end users will not be misled by the update anomalies that could occur in the previous design. Updates to the Ad Manager–Promotions table incur no requirement to affect the records in the Ad Manager–Ad Site table, so the programming for maintaining an accurate database becomes much simpler. Business users still create the full set of records making up the previous Sales Channel table by joining these five tables together, only now the business situations that those results imply will be clear.

Table 12.3. Sample Case’s Tables After 4NF Correction Applied

This correction for a relatively simple fourth normal form violation should serve as a cautionary tale for EDW team leaders. Our example identified several columns in an apparently functional table that turned out to be varying independently. When the EDW team realized that some of the attributes no longer represented a simple set of values qualifying the primary key of a table but had instead taken on independent lives of their own, the design fix required turned out to be very involved. The correction required five new tables, each needing an ETL module of its own, in addition to data conversion for the tables that used to link to the original table before those attributes were split out. Because business changes can frequently transform simple attributes in a table into an independent entity, we will use the fourth normal form correction as a change case later in this chapter to demonstrate how much effort hyper modeled approaches can save an EDW program.

Apparent Redundancies in the Asserted Versioning Schema

However, some data modelers have objected to an apparent third normal form (3NF) violation in the bi-temporal schema common to all asserted version tables. They point to the effective end date, the assertion end date and the row creation date to support their claims. Their objections, in summary, are one or more of the following:

The effective end date is redundant because it can be inferred from the effective begin date of the following version.

The assertion end date is redundant because it can be inferred from the assertion begin date of the next assertion of a version.

The row create date is redundant because it is the same as the assertion end date.

Now in fact, none of these objections are correct. As for the first objection, an effective end date would be redundant if every version of an object followed immediately after the previous version. If we could depend on that being true, which means if we could depend on there never being a requirement to support multiple episodes of the same object, then the effective end date would be redundant.

One could make the argument that all versions within one episode have versions that [meet] and so, within each episode, the end date could be inferred. Although that is true, we would still need an episode end date to mark the end of the episode. Furthermore, the end dates on each version significantly improve performance because both dates are searched on the same row, reducing the need, otherwise, for expensive subselects on every read.

Also, we are not interested in implementing just the minimal temporal requirements a specific business use may require, especially when it would be difficult and expensive to add additional functionality, such as support for multiple episodes (i.e. for temporal gaps between some adjacent versions of the same object), to a database already built and populated, and to a set of maintenance transactions and queries already written and in use. All asserted version tables are ready to support gaps between versions. On the other hand, as long as temporal transactions issued to the AVF do not specify an effective begin date, that capability of Asserted Versioning will remain unused and the mechanics of its use will remain invisible.

As for the second objection, an assertion end date would be redundant with the following asserted version's assertion begin date only if every assertion of a version followed the previous one without a gap of even a single clock tick in assertion time. But once again, we are not interested in implementing just the minimal temporal requirements a specific business use may require. All asserted version tables are ready to support deferred assertions, and deferred assertions may involve a gap in assertion time. On the other hand, as long as temporal transactions issued to the AVF do not specify an assertion begin date, that capability of Asserted Versioning will remain unused and the mechanics of its use will remain invisible.

In addition, as we will see in following chapters, single versions can be replaced by multiple versions as new assertions are made, and vice versa. In that case, the logic for inferring assertion begin dates from the assertion end dates of other versions could become quite complex. This complexity could affect the performance, not only of maintenance transactions, but also of queries. The reason is that, if we followed this suggestion, it would be impossible to determine, from just the data on any one row, whether or not that row has an Allen relationship with the assertion time specified on a query. To determine that, we would need to know the assertion time period of the row, not just when that time period ended.

As for the third objection, a row create date would be redundant with an assertion end date if Asserted Versioning did not support deferred assertions. In fact, neither the standard temporal model, nor any more recent computer science research that we are aware of, includes deferred assertions. But Asserted Versioning does. Because it does, the AVF may insert rows into asserted version tables whose assertion begin dates are later than their row creation dates.

A Technical View

The data vault modeling is a hybrid approach based on third normal form and dimensional modeling aimed at the logical enterprise data warehouse. The data vault model is built as a ground-up, incremental, and modular models that can be applied to big data, structured, and unstructured data sets.

DV2 modeling is focused on providing flexible, scalable patterns that work together to integrate raw data by business key for the enterprise data warehouse. DV2 modeling includes minor changes to ensure the modeling paradigms can work within the constructs of big data, unstructured data, multistructured data, and NoSQL.

Data Vault Modeling 2.0 changes the sequence numbers to hash keys. The hash keys provide stability, parallel loading methods, and decoupled computation of parent key values for records. There is an alternative for engines that hash business key values internally—the option of utilizing the true business keys as they are, without sequences or hash surrogates. The pros and cons of each technique will be detailed in the data vault modeling section of this chapter.

6.3.1 No-History Reference Tables

The most basic reference table is just a typical table in third or second normal form. This basic table is used when there is no need to store history for the reference data. That is often the case for reference data that is not going to change or that will change very seldom. Typical examples include:

Medical drug prescription codes and definitions

Stock exchange symbols

Medical diagnosis codes

VIN number codes and definitions (such as manufacturer codes)

Calendar dates

Calendar times

International currency codes

US state code abbreviations

Note that it depends on the actual project: e.g., in some countries other than the USA, there might be frequent changes in the medical diagnosis codes, for whatever reason.

The simple no-history reference table has no begin-date and no end-date because there are no changes in the data. Therefore, the structure is very simple, as Figure 6.7 shows.

This logical model shows a reference table to store a simple calendar in the Business Vault. The data is identified by the Date key, which is a Date field in the database. Other attributes in this example are the Year, Month, and Day, which store the corresponding whole numbers. Day of Week is the text representation of the week day, e.g. “Monday.” There is no need for keeping a history of changes because there will be no need to track those in most businesses. It doesn’t mean that there are no changes to the data in this structure. However, most changes are bug-fixes or should update all information marts, including historical data. Examples for the latter include translations of the Day of Week attribute or abbreviating the text. Figure 6.8 shows the ER model for this reference table.

The descriptive business key is used as the primary key of the table. The reason for this is that the key is used in satellites and Business Vault entities to reference the data in this table. That way, it becomes more readable and ensures auditability over time. If a business key is used as the primary key of the reference table, it has the advantage that it can be used in ER models or in referential integrity, if turned on, for example for debugging purposes.

Table 6.9 shows an excerpt of the reference data in the calendar table.

Table 6.9. Calendar Data in Nonhistory Reference Table

This example uses a RecordSource attribute again because the data is sourced from Master Data Services (MDS). If the data in MDS is changed by the user, it will overwrite the content of the reference table because there is no history tracking. In other cases, the data is not sourced from anywhere. Then, the LoadDate and the RecordSource attributes are not needed. However, it is good practice to source the data from analytical master data because it becomes editable by the business user without the need for IT. This is a prerequisite for managed self-service business intelligence (BI), a concept that is covered in Chapter 9, Master Data Management.

Once the reference table has been created in the model, it can be integrated into the rest of the model by using the primary key of the reference table wherever appropriate: the biggest use is in satellites, but they are also used in Business Vault entities. Figure 6.9 shows a typical use case where a satellite on a Passenger hub is referencing the primary key of a reference table.

The satellite Address references the reference table State via the USPS state abbreviations. That way, the reference indicates that there is more descriptive information for State in the reference table. By doing so, we don’t use readability in the satellite and keep the basic usage of Data Vault entities intact.