Let’s first discuss some terminology and reading conventions. All of the following concepts are based upon the Relational Model as defined by Ted Codd in 1968. Though, this article is not as rigorous in its definitions, the basic ideas are the same.

A relation is analogous to, though not exactly, a “table,” “file,” or “record type” with a finite set of attributes and a finite number of rows. An attribute is analogous to, though not exactly, a “column” or “field” and represents a “named domain” associated with the relation. Throughout the article, we will mainly use the terms relation and attribute, though occasionally, “table” is used for “relation” and “column” is used for “attribute.”

All relations used in the examples are defined using standard SQL. When an example requires data, a table is presented below the relation definition. Each table of data contains a header row of attribute names corresponding to the relation definition.

Where applicable, empty values or NULLs are represented by “<NULL>” without quotes.

All inference of the inherent structure of data rests upon the functional dependency, defined as follows.

Given a relation R and attributes X and Y in R, Y is functionally dependent on X if for every unique value of X there is one and only one value of Y. The functional dependency is represented as,

X ® Y

and read as “X determines Y.”

In a functional dependency, the left hand side (“X”) is called the determinant and the right hand side (“Y”) is called the dependent.

For example, think about your organization. Every employee has an employee number. In fact, every employee should have a different employee number. So, for every unique value of employee number, there should be one, and only one, employee assigned that number (if not, think of the payroll, benefit, and tax implications). So, you could also say that the employee number functionally determines the employee name, address, phone number, etc.

The dependencies that illustrate this example are as follows.

Though the definition does not explicitly state it, the determinant can contain more than one attribute (e.g., order_num + order_line_id ® ordered_prod_cd, given each unique value combination of order_num and order_line_id, there is one and only one value for ordered_prod_cd).

Embedded relations exist in non-normalized files and, through the use of dependencies, can be successfully normalized out of the file without changing the underlying data or meaning of the structure. For example, an insurance policy source file may contain customer data that can be normalized out into its own relation. The customer relation is embedded in the policy data.

When modeling new systems, data analysts rarely investigate existing source data to identify the structures that are needed. The business requirements, file layouts, and documentation are the main sources of information that an analyst uses.

Unfortunately, when the existing data is migrated to the new application, the inherent structure of the data may prevent a clean and easy conversion. An analyst that manually investigates the structure of source data finds that the process is slow and takes too much time. This problem was solved with the development of dependency inference technology.

With the advent of efficient and fast mathematical algorithms that infer functional dependencies inherent within data, profiling the structure of large quantities of data became much easier. Automated software products were developed around the “dependency inference engine.” These products test all possible dependencies for a relation, and return those that are true within the data.

An advantage to testing all possible dependencies is completeness of results. All possibilities are tested in a comprehensive, structured task. Nothing is left to chance. Human error is also removed from the process.

The importance of this analysis is in its ability to infer the third normal form structure of a specified source file. The knowledge of the business, combined with the known dependencies, defines the optimal normalized structure necessary to satisfy the business requirements.

This normalized model can be used as the basis for a staging area of data, a critique of a pre-defined database or application, or a data quality effort. There are, though, some other techniques that can aid in identifying business rules and validating existing business rules that may not be enforced by the data structure.

In reviewing the inferred dependencies, the analyst uses existing business knowledge to identify important structures of data. Sometimes, these structures are readily apparent, say with “customer_id” as the data’s inferred primary key. Other times, the structures are not so apparent or may require more or different data to see them. Regardless of the efficiency or speed of the algorithms, or the speed of the hardware and software, very large source files or tables must be sampled for effective and timely results. Finally, the analyst may also investigate interesting dependencies that may signal completely new structures or rules not explicitly documented or defined.

One of the first, and most used techniques is identifying the primary key of the source file. During Attribute Analysis, a set of candidate keys may have been identified. Attributes that are 100% unique or a set of attributes that the business or DBA specified are candidates.

To identify a true candidate key, investigate dependencies for a determinant that appears most often in the list. For example, let’s examine the following table.

CREATE TABLE EMPL_JOBS
          (empl_id char(5) NOT NULL,
          job_id char(7) NOT NULL,
          job_start_dt datetime NOT NULL,
          job_end_dt datetime,
          sched_work_hours number(5,0) NOT NULL DEFAULT 0,
          actual_work_hours number(5,0) NOT NULL DEFAULT 0)

Under normal circumstances, a primary key would be defined. In this case, though, either the DBA has turned off unique indexing (to quickly load data or for performance reasons), or a key was never defined or is programmatically validated (pre-relational databases). The data analyst reviews the inferred dependencies obtained from the data and finds the following.