DATABASE DEBUNKINGS

by David McGoveran

[Ed. Note]
This part uses a more formal language and in order to make it easier for the reader, here are the terms used in this part and the equivalents I used in the previous three parts:

• relation: R-table
• tuple: row
• attribute: column (I reserve attribute for the conceptual level)
• relation predicate: intersect of integrity constraints to which an R-table is subject

David refers to the tables whose data is stored (base tables in SQL) as the physical design. I prefer to reserve the term for the internal storage and access methods which are used to implement the tables' representation on disk.

His discussion of user-managed missing data is in the context of SQL DBMSs. Consider it as yet another burden left by vendors to developers. For a proposed relational (metadata) solution supportable by a TRDBMS see my paper The Last NULL in the Coffin. For an implementation technology that would facilitate such TRDBMS support see Go Faster! - The TransRelational(TM) Approach to DBMS Implementation]
[End Ed. Note]

The question how to handle missing information such as birth dates and death dates in a database about people has raised a number of issues. I addressed these issues somewhat abstractly in previous articles[1] and in more depth in seminars and workshops. The present attempt is both a bit more narrow in scope and more concrete.

Note: I invent language here to support the concepts as necessary. If you are using a data modeling tool, you should be able to translate into the language of that tool easily enough. (Otherwise obtain a better one!) Implementation is addressed as part of physical design (see below).

Whenever a database design issue arises, it is crucial that we begin with a purely logical design. At the logical level we do not make decisions about what is or is not physically stored. The logical design of the database representing the business (conceptual) model in Part I should be as follows:

PEOPLE {PERSON_ID, NAME};
LIVE_PEOPLE {PERSON_ID, NAME, BIRTH} PROPER SUBTYPE OF PEOPLE;
DEAD_PEOPLE {PERSON_ID, NAME, BIRTH, DEATH} PROPER SUBTYPE OF LIVE_PEOPLE;

Explanation: We always give an instance its most specific type (and can then deduce that instance's supertype). In effect, instances of a type are necessarily disjoint from each of sets of instances of that type’s proper subtypes. We can easily see whether or not a relation B{A1, ... An, B1, ... Bn} is the subtype of relation A{A1, ... An}: B inherits all the attributes and constraints (including dependencies) of A, such that if relation predicate (i.e., the membership predicate[2] for a relation) PB is TRUE for tuple {A1, ... An, B1, ... Bn}, relation predicate PA is necessarily TRUE for tuple {A1, ... An}.

Conceptually, when a proposition (fact) is asserted as "TRUE"--i.e., when the tuple representing that proposition is inserted in the database--we start at the bottom of the type hierarchy and match attributes (more precisely, we check for consistency of the fact with the corresponding relation predicates for each relation in the hierarchy). In this example, if we know DEATH, the data can only match the relation predicate for DEAD_PEOPLE and if we know BIRTH but not DEATH, the data can only match the relation predicate for LIVE_PEOPLE. Finally, if we only know NAME, the data can only match the relation predicate for PEOPLE.

If, at a later time, we learn the birth date BIRTH of a person listed in PEOPLE as having name NAME, the type of that instance has been specialized to LIVE_PEOPLE. The corresponding PERSON_ID must be moved from PEOPLE to LIVE_PEOPLE. Similar comments apply if a death date DEATH is learned (How would you modify this example if it were possible to have (knowledge of) a DEATH without a BIRTH? What about a PERSON_ID without a NAME?).

Now let’s move on to questions of physical design. Technically, we can choose any design that is information preserving with respect to the logical design. That is, the physical design must be derivable from the logical design using relational operators. But this is where SQL DBMSs fail us horribly--they do not adequately support the full expressiveness of first order predicate logic, relation predicates, introduce NULLs, do not support a complete type theory and arbitrary expressions of constraints and of dependencies, confuse logical and physical issues, limit view updating, etc. So we are forced into designs that are product-specific and will have to use work-arounds to get the desired result.

We need to choose which of the relations in the logical design to store. Our first task is to determine if the application permits us to deduce that any of those relations will be empty. For example, if our application will only track persons that are named, and for which we have either a birth date or a birth date and a death date, then we never need to store a distinct PEOPLE relation. (Exercise: Why?) And, if we need to, we can derive the set of all instances of the PEOPLE type as:

LIVE_PEOPLE {PERSON_ID, NAME}
UNION
DEAD_PEOPLE {PERSON_ID, NAME}

By contrast, if we need to track named persons whether or not they have either a birth date or a death date, then PEOPLE should be a stored relation.

Now, for reasons of physical efficiency (e.g., anticipating lots of queries that refer to all people I’m tracking) and barring other application constraints, I may want to store a single relation

ALL_PEOPLE {PERSON_ID, NAME, BIRTH, DEATH}

and create projection views that have the attributes of DEAD_PEOPLE, LIVE_PEOPLE and PEOPLE. Instead of using NULLs, we use default values for BIRTH and DEATH that are outside the otherwise permissible values for the attributes--this escapes the use of many-valued logic, while permitting a simple projection/restriction view to select the tuples belonging to a particular subtype (write the queries for this!).

It also lets us index each of BIRTH and DEATH. In many SQL DBMSs, such single table views are updatable, assuming the defaults are declared. (What extra work is required to keep these "phony default" values from distorting data analysis? Hint: How you define your views makes all the difference!)

As I have commented elsewhere (Nothing from Nothing, Part IV), such designs are easy to extend if the application requires you to differentiate between "inapplicable" and "unknown" (missing). For example, suppose that we want to record that a person died, but we do not know their birth date. This situation is clearly different from what we have dealt with above, in which a missing death date for a living person is clearly "inapplicable". And there are many other ways in which we may want to classify so-called missing data:

• "unknown for now"
• "unknowable ever"
• "not entered"
• "have multiple possible values"

and so on. Tracking the differentiation among types of missing data is clearly "data about data" in the general case--in other words, metadata. If it is to be tracked, it should be tracked explicitly and that means it should be part of the logical design in the first place--as attributes of relations. In the general case, only the application user can tell us why they don’t have an attribute value that they believe should exist-- such as BIRTH for a row inserted into LIVE_PEOPLE. We have to collect that reason from them if it is important. In terms of physical design, there are many choices as to how to store such data.

If I’m concerned about managing data quality as a background task, I prefer to store it in a set of adjunct tables which I treat as metadata and so in the same way as I would tables in the system catalog. For example, I might create a table

MISSING {TABLE, KEY, ATTRIBUTE, REASON}

I could then search this table for REASON = "NOT_ENTERED" from time-to-time, in order to issue a request to the application user to locate the appropriate data, thereby improving the quality of the database.

On the other hand, classification of why data is missing for an attribute might be an inherent part of the application. In such cases, it is useful to add a "meta-attribute" column to the physical relation that explains the entry or lack thereof. The default for this column is a code meaning "VALID". Other entries need to be selected from a select list during data entry if no valid value is provided for the attribute in question. Meta-attributes can be hidden from the casual user with the views used to select a particular subtype.

Throughout the foregoing, I assume that the application per se will be built on top of views that select a particular type or subtype. The application programmer, let alone the business user, should never be presented with a design that reflects anything other than the entities with which they are familiar. As database experts, it is our responsibility to do our best in achieving that goal--no matter the obstacles SQL DBMS vendors may place in front of us. While the result may not be perfect, discipline and theory will help narrow the gap between how we use products and what a TRDBMS would enable.

[1] Nothing from Nothing, DBP&D, in four parts, Dec.1993-Mar. 1994. Also in C. J.Date, RELATIONAL DATABASE WRITINGS 1994-1997, Addison-Wesley, 1998.

[2] Whenever I refer to a predicate, I mean a symbolic formula that can be used for symbolic computation and, therefore, automated deduction or theorem proving. Contrary to other authors, I do not consider an English declarative statement to be a predicate--at best, such an expression is an informal (and possibly loose) interpretation of such a predicate. English interpretations can be useful for conveying the gist of relation predicates uses, but lead to serious errors if examined in detail.

Do you like this post? Please link back to this article by copying one of the codes below.

URL: http://www.dbdebunk.com/2013/02/database-design-relational-fidelity-and.html HTML link code: <a href="http://www.dbdebunk.com/2013/02/database-design-relational-fidelity-and.html">Database Design, Relational Fidelity and SQL Part IV: Data Independence and Missing Data</a> BB (forum) link code: [url=http://www.dbdebunk.com/2013/02/database-design-relational-fidelity-and.html]Database Design, Relational Fidelity and SQL Part IV: Data Independence and Missing Data[/url]