<home

Zero Degree Keys and Dependencies

Examples of zero degree keys ("empty" keys with no attributes) and zero degree dependencies (empty set of attributes as a determinant) are rarely found in the literature on dependency theory and normalization. No special treatment is needed for these concepts. Provided keys and dependencies are understood to consist of possibly empty sets of attributes then all the expected inference rules and other properties will still hold when those sets happen to be empty. However, it is worth considering some examples of a dependency on the empty set and to demonstrate why singleton relations (relations with empty keys) are a useful part of the database designer's toolkit.

A functional dependency (FD) is a constraint that specifies when one set of attributes determines another. The general form of a FD is written {A}→{B}, meaning A determines B, where {A} and {B} are sets of attributes. A dependency on the empty set is written similarly as: {}→{B}, meaning no attribute at all is required to determine the value of B. If R is a relation that satisfies {}→{B} that means the value of B must be identical for every tuple in R. It's important to understand that {}→{B} is not the same as saying that B has no determinants. If there were no determinants for B then B would be unconstrained and the value of B could be different in different tuples. {}→{B} asserts that B has only one value for all tuples in a relation at any point in time.

Consider a sales ledger database for a company called Thomson and Thompson Ltd. In the sales ledger the InvoiceNumber is the key of the Invoice table. InvoiceDate is the date of the invoice. Customer is the identifier for the customer to be billed. The database is designed to hold data for just one company. One possible design might be to put the company's name (CompanyName "Thomson and Thompson Ltd") into the Invoice table just because the CompanyName needs to be printed on every invoice. This is the Invoice table:

INVOICE
+-------------+-----------+--------+------------------------+
|InvoiceNumber|InvoiceDate|Customer|CompanyName             |
+-------------+-----------+--------+------------------------+
|1001         |2012-04-10 |AB22    |Thomson and Thompson Ltd|
|1002         |2012-04-10 |RK01    |Thomson and Thompson Ltd|
|1003         |2012-04-11 |ST02    |Thomson and Thompson Ltd|
|1004         |2012-04-11 |ED01    |Thomson and Thompson Ltd|
+-------------+-----------+--------+------------------------+

Now here are some of the dependencies that we want the Invoice table to satisfy:

{InvoiceNumber}→{InvoiceDate}

{InvoiceNumber}→{Customer}

{}→{CompanyName}

The problem here is that in our Invoice table the CompanyName is not fully dependent on the key. {}→{CompanyName} is a partial key dependency because {} is a proper subset of the key which is {InvoiceNumber} (remembering that a key is a set of attributes and the empty set is a subset of every nonempty set). This design for the Invoice table therefore violates Second Normal Form, which does not permit partial key dependencies in a relation. It is sometimes wrongly assumed that a relation which doesn't have any composite keys will inevitably satisfy Second Normal Form. This example demonstrates why that assumption is sometimes wrong.

The only way to satisfy Second Normal Form (and also in this case to satisfy Boyce Codd Normal Form[1]) with respect to the above dependencies is to make a new relation for the CompanyName attribute with a key of {} - an empty key. The empty key constrains the new relation to a single tuple, which is why that type of relation is referred to here as a "singleton". Singleton relations with their empty keys are a necessary consequence of normalization theory whenever a dependency on the empty set is being represented.

INVOICE                                  COMP
+-------------+-----------+--------+     +------------------------+
|InvoiceNumber|InvoiceDate|Customer|	 |CompanyName             |
+-------------+-----------+--------+	 +------------------------+
|1001         |2012-04-10 |AB22    |	 |Thomson and Thompson Ltd|
|1002         |2012-04-10 |RK01    |	 +------------------------+
|1003         |2012-04-11 |ST02    |
|1004         |2012-04-11 |ED01    |
+-------------+-----------+--------+

My paper here explains how to implement the Comp table in SQL and enforce the empty key constraint.

Possibly the reason why dependencies on the empty set get very little attention is that they are usually so "obvious" and at first appearance seem to be of very little significance. Most people with even a little experience of database design will quickly notice that something about putting CompanyName in the Invoice table seems wrong. However, it's worth understanding precisely why it is wrong and how to improve things by making a new table with an empty key.

Here's another example, just to underline the point. It's a simpler example than the last one but also more abstract.

CIRCLE
+-------------+--------+-------+
|Circumference|Diameter|Pi     |
+-------------+--------+-------+
|     12.56636|       4|3.14159|
|      9.42477|       3|3.14159|
|    311.01740|      99|3.14159|
+-------------+--------+-------+

Here the Circumference and Diameter are both keys, a circle being uniquely defined by either of those attributes. Pi is the ratio of the circumference to the diameter but it is a constant and therefore {}→{Pi}. To ensure we satisfy BCNF, the Pi attribute should be moved to a singleton relation keyed on {}.

Further reading about dependencies on the empty set here.


[1] Boyce Codd Normal Form (BCNF) is the highest normal form that is concerned with normalization of functional dependencies.

April 2013