Monday, September 19, 2016

The Principle of Orthogonal Database Design Part I (UPDATED)

REVISED: 11/2/16; 11/10/16
 


Note: This two-part post replaces several previous posts which now redirect here. The example is not meant to be realistic, but to convey specific points in an accessible way.
"The principle of orthogonal design (abbreviated POOD) ... is the second of the two principles of database design, which seek to prevent databases from being too complicated or redundant, the first principle being the principle of full normalization (POFN). Simply put, it says that no two relations in a relational database should be defined in such a way that they can represent the same facts. As with database normalization, POOD serves to eliminate uncontrolled storage redundancy and expressive ambiguity, especially useful for applying updates to virtual relations (views). Although simple in concept, POOD is frequently misunderstood ... is a restatement of the requirement that a database is a minimum cover set of the relational algebra. The relational algebra allows data duplication in the relations that are the elements of the algebra. One of the efficiency requirements of a database is that there be no data duplication. This requirement is met by the minimum cover set of the relational algebra." --Wikipedia.org
Well, not quite.

Base and Derived Relations

Every database relation has an associated formal relation predicate (RP), a conjunction of integrity constraints expressed in a DBMS-specific data language. They represent in the database informal business rules comprising a conceptual model, which denote the meaning of the relation and its tuples assigned by the database designer.

Relational databases consist of a set of base and derived relations, the latter--query results, views and snapshots--derived from the former by relational algebra operations. Because SQL stored tables are called base tables, they induce the mistaken notion that base means stored, but while their data can and often will be stored (not necessarily as tables), base relations does not mean stored relations! Rather, they represent the base facts--axioms--about the real world entities of interest (i.e., serve as the base of the database). Derived relations represent facts that are logical implications of the axioms--theorems--and are also about the entities represented by base relations--no new entities are created in deriving relations from the base relations.

Relations are derived from base relations either directly, or via other derived relations and inherit the integrity constraints on the relations from which they were derived, supplemented by any constraints added by the relational operations applied to produce them (e.g., restrictions, projections, joins and so on). Thus, at every relation derivation a true RDBMS records the derived RP (constraints) in the database catalog--another way of saying that it supports constraint inheritance--and thus always knows how the derived constraints relate back to the base constraints. 


Some derived relations (e.g., views) are given names, but they are just a shorthand for their RPs (constraints). Others (e.g., query results) don't have names. Note very carefully that in a truly relational system application developers and end-users should not need to know if they interact with base and when with derived relations. In fact, in a truly relational environment the database should be accessible to applications only via views, to take advantage of logical independence--insulation from logical reorganizations of the database.

Three Formal Design Principles


Formal systems adhering to three principles have certain desirable properties. Relational databases are formal logic systems and, therefore, will acquire those properties if their design adheres to these principles [1] which, applied to databases, are:
  1. Principle of Orthogonal Design (POOD): Base relations are independent;
  2. Principle of Representational Minimality (PORM): There are no superfluous base relations;
  3. Principle of Expressive Completeness (POEC): All meaningful relations are derivable from the base relations.
Note: There is a McGoveran conjecture that the Principle of Full Normalization (POFN) implies the three principles, but not vice-versa.

A base relation is independent if it is not derivable from other base relations. Here's Codd in the first ever paper (1969) that launched the RDM: "A relation R is derivable from a set S of relations if there exists a sequence of [relational operations] which yields R from members of S." In other words, a base relation is independent if the facts it represents are not derivable from those represented by the other base relations (identical relations are a trivial case of non-independence)

While POOD (and the POFN) reduce logical redundancy, their principal objective is  
  • Logical correctness: the facts represented by derived relations are true;
  • Semantic correctness: There are no update anomalies (i.e., updates of derived relations have no undesirable side-effects on base relations).

Entity Supertypes and Subtypes


Consider a (very) simple conceptual model consisting of the following business rules and assume for now that no data are missing.
  • All employees have an id, name and hire date;
  • Some earn a salary, some make a commission (salary and commission are mutually exclusive).

Many practitioners would design the following SQL table:
EMPLOYEES (EMP#,ENAME,HIREDATE,SALARY,COMMISSION)
that would contain NULLs that stand for "inapplicable". The NULLs are an artifact of poor design--the inaccurate representation of the conceptual model. The model specifies that some employees do not have salary or commission, yet the design assigns them to all tuples, forcing NULLs.  Whether they stand for missing or inapplicable, NULLs violate the core Information Principle (IP) of the relational data model (RDM), which mandates that all information in a relational database be represented explicitly and in exactly one way: as values of relation attributes defined on domains. NULL is not a value, but a marker for the absence of a value that cannot be legitimately treated as a value--that would be a logical type error--so the table is not a R-table--it does not  picture a relation. Most data professionals are oblivious to the problems caused by NULLs (see [2] and bibliography in [3]), because they focus on representation (structure) and ignore the implications for integrity enforcement and manipulation.

In the past I advocated the following NULL-avoiding three base relations design:

EMPS (EMP#,ENAME,HIREDATE)
SAL_EMPS (EMP#,SALARY)
COMM_EMPS (EMP#,COMMISSION)
but what entities do the latter two relations represent? The application developer, let alone the end user, should be presented with a logical design that reflects entities with which they are familiar.

When entities have some properties in common, but some also have properties not shared, not all entities are of the same type. Entities with unique properties in addition to common ones are a subtype of those with only common entities, the supertype i.e., there is an entity supertype-subtype (ESS) relationship.

Salaried and commissioned employees are subtypes of the employee supertype. According to the model, employees can be either salaried, or commissioned, but not both. So one possible logical design is one base relation for each type:

EMPS (EMP#,ENAME,HIREDATE)
SAL_EMPS (EMP#,ENAME,HIREDATE,SALARY)
COMM_EMPS (EMP#,ENAME,HIREDATE,COMMISSION) 

Note: Once base relations are determined, for reasons of physical efficiency (e.g., anticipation of lots of queries about all employees) and barring other application requirements, there is nothing to prevent physical storage of the data in an indexed sequantial file with the following records:
(EMP#,ENAME,HIREDATE,SALARY,COMM)
Relations do not occur, nor need they at the physical level, so this is a perfectly acceptable physical design. EMPS, SAL_EMPS and COMM_EMPS can be derived as projection views at the logical level. Default values outside the otherwise permissible value ranges for the attributes can be used instead of NULLs for inapplicable SALARY and COMMISSION values. Default values are not just NULLs by another name: they occur in the physical, not logical design. They extend the domain and, except by caveat, are not legitimate values for computational purposes (again, logical inference and relational operators occur only in the logical model). So there is never a concern to the user--they are handled by a true RDBMS transparently, provided users understand the domains.
 
Generally, ESS relationships yield designs with base relations (that may be stored) and views derived from them.  For this reason, it is assumed that applications will be built on top of views that represent particular entity supertypes or subtypes.
 
Note that this design violates the POOD: EMPS data is derivable logically as a union view from SAL_EMPS and COMM_EMPS. 

Stay tuned for Part II for the consequences.
 

References

[1] McGoveran, D., LOGIC FOR SERIOUS DATABASE FOLKS, forthcoming (chapter drafts).
[2] McGoveran, D., Nothing from Nothing, Parts 1-4.
[3] Pascal, F., The Final NULL in the Coffin: A Relational Solution to Missing Data.




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

URL: HTML link code: BB (forum) link code:

15 comments:

  1. I don't see anything wrong with having them all in one table, with nulls and a check constraint to ensure mutual exclusivity.

    ReplyDelete
    Replies
    1. There is little to respond to such a well reasoned argument.

      Delete
    2. That may work fine for a couple of sub-type entities that have only a small number of differences. Try it with many subtype entities with many unique attributes and complex validation rules though...it quickly breaks down, and may easily exceed the capability of a check constraint.

      Delete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. This comment has been removed by a blog administrator.

      Delete
    3. This comment has been removed by the author.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. Boasting about your lack of knowledge and ability to understand is not a good idea.

      Delete
  4. There is a McGoveran conjecture that the Principle of Full Normalization (POFN) implies the three principles, but not vice-versa. And McG has three other Principles that correspond to your three for Formal Systems: POOD, Principle of (Expressive) Completeness, Principle of (Representational) Minimality.

    The trouble is, I've never seen any of those Principles stated in precise language. Indeed I don't know whether they're supposed to apply to a schema (including integrity constraints/Relation Predicates) or to the formal semantics of the possible facts the application is capable of expressing.

    I'm finding in both Date's (many) and McG's treatments of View Updating (or Database Updating), a lot of high-fallutin language and capital 'P' Principles. It sounds like it's a treatment in logic. But it ends up same place as attempting to square the circle.

    Or do you know something that isn't available from the literature?

    ReplyDelete
    Replies
    1. The RDM is a formal logic system and, therefore, should be governed by formal system properties. This is something Codd understood, but many of its interpreters (including myself) did not were fully understand for quite a while. What David has been doing is developing the correct interpretation. This is VERY hard work and he did his best in some very difficult circumstances. If you follow my site you should have seen that he is working on a book that will contain all the formalisms. I am working on informal treatments to make them accessible: revising my papers, writing a book and posting some of the ideas here. But it takes time--this is not your mum and pup "RDM", SQL or otherwise.

      Specifically to the three principles--as the post states, formal systems that are governed by them have certain desirable properties. Applied to databases, they guarantee view updatability and logical independence, and logical and semantic correctness of query and update results.

      For the formalisms you will have to wait for David's book, but can read some of the draft chapters at his website. It requires intellectual effort, particularly to those without a background in formal logic.

      What I am trying to do is provide informal and more accessible explanations. You will have to wait for my paper revisions, forthcoming book and follow posts here.

      Delete
    2. It's good to see it emphasized that application programmers should never refer directly to base tables. They have enough to do without having to program the dbms. When the database as well is seen as a program, they shouldn't program it either because they can easily contradict the intentions of the data design.

      Delete
  5. I've just noticed your opening paragraph use of meaning. (Not sure if this was in your o.p. or is a recent revision.)

    Every database relation has an associated formal relation predicate (RP), a conjunction of integrity constraints expressed in a DBMS-specific data language. They that represent the informal business rules in the database, which denote the meaning of the relation and its tuples.

    Your sentence is somewhat ambiguous. Do you mean:
    * The informal business rules denote the meaning of the relation?
    * The integrity constraints denote the meaning of the relation?

    (In either case, I would say it is the relvar that carries meaning, not a relation value. Or a derived relation carries meaning derived from its based-on relvars combined with the relational expression that produces the relation.)

    The informal business rules cannot denote meaning of a relation: they are rules about the business, not about the database or its content.

    The integrity constraints cannot denote meaning: they constrain the possible values that can appear in the database, but say nothing about what it means. For example, stipulating that EMP# be a key for relvar EMPLOYEES tells nothing about what an employee number is, or what an employee is.

    McGoveran's writings seem to continually mix up 'internal predicate' (what you call RP) with 'external predicate' (what TTM calls 'relvar predicate'). It might well be that integrity constraints are a consequence of business rules, which are a consequence of the enterprise's intended meaning and usage for its descriptions of entities and possible worlds. But the integrity constraints do not denote meaning.

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
  6. You will notice that we don't use the term relvar. Codd used "time-varying" relations for a reason: set theory does not have the concept of variables. There may be relvars "under cover", but not at the data language level that users interact with.

    Each and every base relation of the 'relation type' has the same meaning denoted by the informal business rules. However, they must be formalized and symbolized as integrity constraints to be accessible to the DBMS for update decisions. They are the formal database representation of the rules. So both denote the meaning of the relations at different levels of representation.

    Of course they are about the business. But relations are assigned that meaning by the database designer.

    How exactly do you formulate constraints, what do they represent in the database? They are predicates -- formal symbolizations of informal rules. If you have problem with 'meaning', think of rules as meaning as understood semantically by humans and constraints as understood algorithmically by the DBMS. There is one meaning with two representations at two levels of abstraction.

    There are differences between the McGoveran and Date/Darwen interpretations of the RDM. It's up to you to pick one, but make sure you have sufficient knowledge and understanding of formal set theory and predicate logic.

    Some of this is explained in my recent book which I recommend. For the formal theory wait for David's book.

    ReplyDelete