Relational Databases, The Good Parts: Part 1
Every successful technology has good ideas. Raw merit alone however does not propel technologies from just being good ideas to becoming widely adopted. Careful strategy and haphazard social forces both play a part in deciding what technology will emerge as the leader and how long it will stay on top.
Well designed databases using the Relational Model, from a technical perspective, are said to be normalized. There are very specific logical standards to the process of designing normalized databases.
From a human perspective, normalization tends to increase the complexity of a database. Normalizing a database typically involves breaking down into more relations. Working directly with normalized databases requires a greater level of expertise with the technology and more abstract thinking. This conflict between making databases easier to interact with and technically correct implementation is at the center of much of the ugliness of modern database technology.
Relational databases should be interactive, but they should also be normalized. A de-normalized database is little more than a spreadsheet, a useful technology in-and-of itself.
The elegant solutions to the normalization/usability dilemma this series of posts will explore are solutions that focus on abstraction through other technologies to provide both ease of use and ease of development.
As succinctly as possible, with the possibility of over simplifying the concepts, it is possible to define the relational model as:
Something to note with the definitions above is that a system using the relational model may have only a single database rather than a set. Many common uses of relational databases focus on a single database, but it is important to be aware that implementations spanning multiple databases exist.
Additionally the databases, relations, tuples, and data in a database are said to be variables. There may be some variables in a particular relational database that should not or cannot be changed but for the purpose of this overview of the relational model all three of these things are variable, meaning they can change over time.
Of particular importance in this definition is the notion of types. Each discrete piece of data in a tuple has a type, but tuples also have a type which. The type of a data variable is dictated by the type in the referenced attribute. The type of a tuple value is dictated by the set of attributes for the relation. Relations and databases too can be said to be typed. The attributes that dictate the types of tuples also dictate a type for the relation. The set of relation types in-turn dictate a type for the database. This system of typing will be explored in more detail in following sections.
Finally, the notion of uniqueness in naming should be explained as to say that no two databases may have the same name, and within each database no two relations may have the same name, and so on. Each entity in the relational model can be said to have a fully qualified name that includes the entities that contain it.
Thus two relations with the same name, but in different databases are allowed because the fully qualified name of each would include different database names. Similarly, two attributes in different relations may have the same name, and an attribute may have the same name as a relation. Because keys and attributes are both contained by relations, it is highly counterindicated to use the same name between the two in the same relation. Some database implementations may allow it, but it is a bad idea.
The terminology used above is in following with terms defined by the Relational Model. Relations are commonly referred to in database terminology as "tables". Attributes are commonly referred to as "columns" and tuples as "rows". The table-column-row model of database design is certainly useful when thinking about relations conceptually, but can be misleading if you take the analogy too far.
This series comes from the perspective that "simple" is a subjective quality. The normalized relational databases that arise from the approaches described will be more "complex" to the naked human eye than a practical de-normalized database, but more powerful and elegant to the human eye when focused through appropriate technology.
The methods described will not only create highly normalized databases, but to also normalize naming and design conventions in a way that does not limit the raw power of the relational model, but rather tames it. Using well established technology outside the scope of the relational model, each successive post will reveal a more elegant perspective on relational database technology.
Without getting to far on a tangent, it is important to note that relational databases can model the same kinds of information possible in many other models. These models include prose text, xml, binary files, and just about any information representation imaginable. These different models each have different traits that make them better suited to different applications.
Many primers on relational databases describe database design in terms of Entity-Relation modeling and diagrams. These techniques can be useful, but for the purpose of this discussion a more basic type based exploration will be employed. As the name implies, Entity-Relation modeling implies its own model which is not always held to be the same thing as the Relational Model.
Each variable in a relation's tuple references a value. The value must always be of the type specified by the corresponding attribute in the same relation.
To keep things as simple and powerful as possible it will suffice to define these types as a set of possible values. The value referenced by a variable of a type, must be a value in that type's set of possible values.
Again to keep things simple, we will define a value to be any possible value: a number, a boolean value, a string, a complex data type such as an array, or even a relation, tuple, or database. There are a great many implementations of the relational model, each with its own specific limitations as to what a value may be.
Tuples are the singular entity in the relational model that do not have an inherent unique identifier. The variables within each tuple are uniquely associated with an attribute of the relation. The tuple itself only has one way to be uniquely identified, itself. For this reason, each tuple in a relation must be unique. No two tuples may be comprised of variables associated with the exact same values.
As mentioned in the definition above, keys come in two varieties: local and foreign. Local keys designate one or more proper subsets of the attributes of the relation which must also have unique values for every tuple. Each local keys restrict the possible tuple values and create a functional dependence between attributes not in the key on attributes in the key.
Note that the definition of a relation creates an implicit "key" on the set of all attributes, since each tuple must be unique. If a relation has an explicitly defined key on one attribute, no more than one tuple in that relation may ever have each of the possible values for that attribute. Other attributes for which there is no key may have duplicate occurrences of the same value, both collectively and each individually.
A key may include more than one attribute, when it does it does not constrain values in each attribute, but rather the pair, trio, quartet, etc. of attributes. That is to say, if a there is local key on a single boolean attribute the relation may have exactly two tuples: one for key "0" and one for key "1". It there is a local key on a pair of boolean attributes the relation may have four tuples with keys: "00", "01", "10", and "11". This is not the same net effect if each attribute was in a key by itself. In this case there could be any two of the previous four pairs. The existence of the third would always logically violate the uniqueness constraint on one of the two attributes. Of "00" was the first tuple defined, the only other tuple could be "11" since "01" would violate the uniqueness of the first column and "10" would violate the uniqueness of the second.
Attributes may appear in more than one key, and though keys are named, and therefore not required to be functionally unique there is no reason to have non-functionally-unique keys.
Foreign keys are defined as:
Just as local keys enforce an additional uniqueness constraint on values associated with the attribute (on top of constraints from that attribute's type), foreign keys also enforce an additional constraint. Instead of requiring that values be unique, the foreign key requires that values associated with the attribute be in the set of values of the foreign relation. As an example, if the type of the attribute is boolean as in the earlier example and the foreign relation has only a "1" value, the foreign key would require that the local relation only have a "1" value. If that attribute in the local relation was also a local key, the relation could only have one tuple at all. If the attribute was not also a local key in the local relation, the relation could have multiple tuples, so long as each tuple was unique and no tuple had a value for that attribute other than "1". Foreign keys limit the value in the local attribute to the set of values associated with the foreign attribute. This is always a subset (though not always a proper subset) of the attributes type.
The Relational Model, and many database technologies draw a distinction between different types of what this series will call "local keys": primary and candidate. These can be semantically important when working directly with specific database technologies, but the prescribed design practices will make distinction unnecessary aside from implementation specific quirks.
Just as relations have a type as defined by the set of attributes, keys too have a type based on their own set of attributes. The type of a foreign key includes the name of both the local and foreign relations. Key types in-and-of-themselves are not an important consideration in the design practices that will be discussed, but they give rise to another type that is central: Correlation Types.
The strongest form of correlation in a database is the direct correlation, a one-to-one mapping. Direct correlations come in two varieties: those formed between functionally independent values in a tuple, those formed between functionally dependent values in a tuple.
In the relational model, the attributes of a relation variable define one-to-one (reciprocally required) relationships between two value types. This implicit relation is the only acceptable method of creating a one-to-one relationship directly between two values. It is also conveniently the only method required.
Mathematically speaking, each tuple of i attributes defines ((i-1)^2 + i-1) / 2 direct correlations. In relations with no explicit keys, all of the values are said to have an independent correlation with each other. This means that any combination of any of values in the tuple that otherwise conform to the associated attribute type constraints are allowed.
Relations with at least one key however create a different kind of correlation between the set of values participating in the key, and the set of values not participating in the key. This distinction hinges on the notion of Functional Dependence, but to keep the definition simple for the purpose of this series an assumption will be made:
To simplify design decisions, it is helpful to consider that in a highly normalized database it is rarely the case that any key with more than one attribute is needed. It follows to infer that, as much as possible, the design methodology this series describes will avoid keys using multiple attributes in a key. With this assumption in mind, rather than saying one set of values of functionally dependent on another set of values, it is possible to say one ore more individual values is functionally dependent on one or more single values.
A functional dependency between two values means that the value of one in some way constrains possible values within the same relation for others. In a relation, if value B is functionally dependent on A then the following statements are true:
This notion of correlation is specifically directional, meaning that while the correlation may be reciprocally identical for both participants in some cases, there are other cases where the nature of the relationship for each participant is different. For direct relationships between values in a tuple two values may be:
The interplay between the attribute that creates a foreign key, and the local key in another relation it points to creates a different kind of constraint than functional dependency. Take the following entities into consideration:
The local key on A adds further constraint from dependent correlation such that for every a there is only one value for b. There may be multiple values for a for each b however.
The same two statements above also apply to C, c, D, and d. as the relationships mirror those of A, a, B, and b respectively.
So far, nothing can be said about any relationship between A and C, A and C, A and D, or B and D.
There is nothing mutually exclusive about attribute's ability to be a local key and a foreign key. Attributes may be either, neither, or both. The basis for different indirect correlation types and the functional effect they have on relationships between values focuses on the following two conditions:
In the formal Relational Model, many authors discuss two forms of local keys: Primary keys and candidate keys. Technically speaking, the distinction is arbitrary. Implementation specific quirks aside, there is no functional difference in the relational model between primary and candidate keys. This is precisely the reason these two terms are not used elsewhere in this series. If a pure theory approach is taken, it suffices to say that all "local keys" are candidate keys and if one is assigned as a primary key arbitrarily there is no technical significance to that selection.
This goes back to the earlier point about difference in the pure theory, and human friendly design choices. There is sometimes disagreement about why normalization is good, bad, or important, or undesirable. Reasons for normalization include both robustness and economy of storage. The compromise this design process will exemplify considers the following from most to least important:
As mentioned, by default the assumption is that for every relation there is a primary key comprised of a single attribute. For most relations the safe assumption is to assign an artificial primary key, and many relational database technologies make this easy. An artificial key is a value that is part of each tuple but does not functionally change the information the tuple represents.
It has already been mentioned that in the relational model tuples alone lack a unique name. Databases, relations, attributes, and keys are all named uniquely. The notion of a local key is vaguely analogous to a the unique names available to other entities in the relational model. Any local key for a relation can be used to select exactly one tuple uniquely. The notion and perceived importance of a "primary" key is probably deep seated in the human tendency to name and label things.
Sometimes the information represented by a tuple inherently includes a "unique identifier". The identifier is part of the information. When this unique identifier is truly unique, meaning no other distinct tuple in the relation could ever logically use the same identifier. This means all the other information in the tuple is functionally dependent on the identifier. It stands to reason then that it would be desirable to make that identifier a local key, and as it turns out this is exactly the right design decision.
The problem however is that while this part of the information may always be unique, the decision to make it an identifier is a bit tricker. Uniqueness is a semantic property that can safely be relegated to local keys. Identity on the other hand presents a challenge: could the value with the identity change? The semantic property of identity can take on different meanings depending on the intent of the designer. Exactly what is meant by "semantic" will be covered in the next post, but for now it is important to simply state that from a design perspective it is undesirable for the identity associated with a tuple to ever change. For this reason the assumption is that the identifier attribute chosen (the primary key) for each relation is one that is arbitrary assigned by the database and is never changed.
Designers may explicitly decide that a primary natural key is appropriate for a relation. There are certainly cases where this choice makes sense. It is however a choice that should be both deliberate and carefully made. Beyond this point this series will only refer to primary keys as identifiers when they are artificial keys and natural identifiers otherwise.
To return to the reason for this explanation of the significance of a local key to its relation, identifiers and local keys that are not identifiers have slightly different meanings. Both convey the exact same logical constraints on a values, what distinguishes the two is the designer's intention behind the correlation they create. The three basic indirect correlation types, and variants of each are the focus of the remainder of this post.
The next post will clarify how value types and correlation types are similar and how they are different. For now it will suffice to mention that this series will focus on a type oriented approach to design and that every type mentioned is a subtype, supertype, or both of some other type.
Interestingly, the super correlation itself has no subtypes (only supertypes).
There is one specialized version, a subtype, of the enum correlation: Unique Enum. In this correlation type the foreign key (in X) is also a local key, but not an identifier. The result is that while tuples in Y represent options for a value in tuples in X, the cardinality is different: zero-or-one-to-one.
This cardinality is the same (just in the reverse direction) as that of the super correlation, but the conveyed design intention is different. It means that Y represents options for values in tuples in X, but each option represented in Y may only correlate to exactly one tuple in X, and not all options in Y have to be represented in X. In the unique enum, instead of saying that X aggregates Y it can instead be said that X owns from Y.
The foreign key association through Z creates an indirect many-or-zero-to-many-or-zero between X and Y. This jointype is formed by two enum relations, but is defined be the indirect correlation between X and Y, not either of those two relations' direct correlation to Z. The properties of this correlation type are:
The two subtypes of the jointype relation involve one or both of the enumtype correlations from Z being converted into a super correlation.
In an Enum JoinType correlation, one of the foreign keys in Z associated with an identifier in X (or Y, but for the purpose of this definition it will suffice to pick only one) is also a local key. This creates a super correlation between X and Z. The correlation between Z and any other other relations that are still enum correlations remains unaffected.
The effect of this change between X and Y is that now in Z there is a functional dependency of g on f, and thus there may only be up to one correlated tuple in Y for each tuple in X. Tuples in X and Y may exist independently of any correlation from Z or from each other. The cardinality of the relationship between X and Y becomes zero-or-one-to-zero-or-many.
While is it important to note that the local key in Z on X (or Y) does not have to be the identifier for Z, in most cases it should be. The main consideration is that as stated above, the identifier for a tuple should never change. If the correlation between X and Y is defined as a trait of the information that X represents, then using that F as the identifier for Z is worth considering (or likewise for G if the information Y represents defines the correlation between the two). The distinction is subtle, and best left alone if there is any doubt.
In a Unique JoinType correlation, both of the foreign keys in Z associated with identifiers in X and Y are also local keys in Z. This creates a super correlation between X and Z and between Y and Z.
The effect of this change between X and Y is that now in Z there is a mutual functional dependency between g and f , and thus there may only be up to one correlated tuple in Y for each tuple in X and vice-versa. Tuples in X and Y may exist independently of any correlation from Z or from each other. The cardinality of the relationship between X and Y becomes zero-or-one-to-zero-or-one.
For every good idea, there is a bad idea. In truth, ideas can seem great to some people or now and turn out to be horrible ideas in the broader scope. Great ideas are often formed by cobbling together many good ideas. To an extent this approach can work well, but eventually the growing complexity hits a critical mass. People are different, and have different tolerances for complexity. Some find certain forms of complexity appealing and challenging. Others find the same complexity bothersome and confusing while valuing different complexities. One man's toil is another's delight. People learn what they are taught, what works for them, and they learn to take the good with the bad.
In Javascript: The Good Parts, Douglas Crockford explores and exposes the best parts of a mostly good idea: JavaScript. Like so many other good ideas, finding the good in JavaScript requires the right perspective.
The aim of this and the other posts in this series is to explore the good ideas of Relational Databases and expose how to most elegantly harness the technology regardless of which of the many "flawed" implementations you might choose to pursue.
I say "flawed" because none of the current commonly used relational database technologies strictly adhere to the Relational Model. Many deviate intentionally and for purely practical reasons. Most stakeholders wanted features that go against the grain of the pure theory. This is not bad by necessity. Commercial and Open Source projects implement features that give a competitive edge, even when such an edge is short sighted. Pure theory can be a bad idea when it doesn't best serve the needs.
As with many things, people have to make decisions for themselves. The right choice is subjective. This series simply aims to layout one clear path through the myriad of options and make implementing a relational database. The goal is the cut through the maze and provide a clear method.
The Relational Model In a Real World
One of the challenges of using any technology well is finding elegant ways to interface it with reality. The Relational Model at a pure level is abstract and mathematic. Many early implementations were interactive in nature, providing a direct interface to the relational model on its own terms. This direct interaction between user and technology is one of the best features of relational databases, but also lead to some very problematic developments.Well designed databases using the Relational Model, from a technical perspective, are said to be normalized. There are very specific logical standards to the process of designing normalized databases.
From a human perspective, normalization tends to increase the complexity of a database. Normalizing a database typically involves breaking down into more relations. Working directly with normalized databases requires a greater level of expertise with the technology and more abstract thinking. This conflict between making databases easier to interact with and technically correct implementation is at the center of much of the ugliness of modern database technology.
Relational databases should be interactive, but they should also be normalized. A de-normalized database is little more than a spreadsheet, a useful technology in-and-of itself.
The elegant solutions to the normalization/usability dilemma this series of posts will explore are solutions that focus on abstraction through other technologies to provide both ease of use and ease of development.
Building Blocks, The Relational Model
The core technology this series will focus on is the Relational Database, which logically is based on the Relational Model.As succinctly as possible, with the possibility of over simplifying the concepts, it is possible to define the relational model as:
- A set of uniquely named database variables, each being:
- a set of uniquely named relation variables, each being:
- a set of n uniquely named attributes, each being:
- exactly one type of data
- a set i of tuples, each being:
- a set of n data variables. In each tuple there is exactly one variable referencing each named attribute. The value of that variable must be of the data type for the referenced attribute.
- a set of r uniquely named keys, each being:
- a set of attribute constraints. Each set is either a uniqueness constraint (local) or a constraint defined by tuple values associated with attributes in another relation (foreign constraint).
- a set of n uniquely named attributes, each being:
- a set of uniquely named relation variables, each being:
Something to note with the definitions above is that a system using the relational model may have only a single database rather than a set. Many common uses of relational databases focus on a single database, but it is important to be aware that implementations spanning multiple databases exist.
Additionally the databases, relations, tuples, and data in a database are said to be variables. There may be some variables in a particular relational database that should not or cannot be changed but for the purpose of this overview of the relational model all three of these things are variable, meaning they can change over time.
Of particular importance in this definition is the notion of types. Each discrete piece of data in a tuple has a type, but tuples also have a type which. The type of a data variable is dictated by the type in the referenced attribute. The type of a tuple value is dictated by the set of attributes for the relation. Relations and databases too can be said to be typed. The attributes that dictate the types of tuples also dictate a type for the relation. The set of relation types in-turn dictate a type for the database. This system of typing will be explored in more detail in following sections.
Finally, the notion of uniqueness in naming should be explained as to say that no two databases may have the same name, and within each database no two relations may have the same name, and so on. Each entity in the relational model can be said to have a fully qualified name that includes the entities that contain it.
Thus two relations with the same name, but in different databases are allowed because the fully qualified name of each would include different database names. Similarly, two attributes in different relations may have the same name, and an attribute may have the same name as a relation. Because keys and attributes are both contained by relations, it is highly counterindicated to use the same name between the two in the same relation. Some database implementations may allow it, but it is a bad idea.
The terminology used above is in following with terms defined by the Relational Model. Relations are commonly referred to in database terminology as "tables". Attributes are commonly referred to as "columns" and tuples as "rows". The table-column-row model of database design is certainly useful when thinking about relations conceptually, but can be misleading if you take the analogy too far.
Normalized Relational Databases
There are, by-in-large two main considerations that go into designing relational databases: normalization and practical use. A highly normalized database has two key benefits: reduced redundancy and less potential for inconsistency. The downside to a highly normalized database is it can be more complex to access useful information directly. It is not uncommon to intentionally create databases that are to some extent de-normalized, making them more practical for people to directly access the information stored in the database interactively.This series comes from the perspective that "simple" is a subjective quality. The normalized relational databases that arise from the approaches described will be more "complex" to the naked human eye than a practical de-normalized database, but more powerful and elegant to the human eye when focused through appropriate technology.
The methods described will not only create highly normalized databases, but to also normalize naming and design conventions in a way that does not limit the raw power of the relational model, but rather tames it. Using well established technology outside the scope of the relational model, each successive post will reveal a more elegant perspective on relational database technology.
Value Types
The relational model prescribes a specific structure of information: databases containing relations as described above. The relational model provides a way to store and represent information in the form of facts, truths.Without getting to far on a tangent, it is important to note that relational databases can model the same kinds of information possible in many other models. These models include prose text, xml, binary files, and just about any information representation imaginable. These different models each have different traits that make them better suited to different applications.
Many primers on relational databases describe database design in terms of Entity-Relation modeling and diagrams. These techniques can be useful, but for the purpose of this discussion a more basic type based exploration will be employed. As the name implies, Entity-Relation modeling implies its own model which is not always held to be the same thing as the Relational Model.
Each variable in a relation's tuple references a value. The value must always be of the type specified by the corresponding attribute in the same relation.
To keep things as simple and powerful as possible it will suffice to define these types as a set of possible values. The value referenced by a variable of a type, must be a value in that type's set of possible values.
Again to keep things simple, we will define a value to be any possible value: a number, a boolean value, a string, a complex data type such as an array, or even a relation, tuple, or database. There are a great many implementations of the relational model, each with its own specific limitations as to what a value may be.
Key Types
The values associated with each variable of a tuple are constrained to the set of values for that variables data type. This type comes from the an attribute of the relation, each tuple has exactly one variable per attribute. It is important to consider the use of the word 'set' in the previous definition. Sets are unordered, and each member of a set must be unique in that set. For the named entities in the relational model: database, relation, attribute, and keys; the name alone satisfies this uniqueness requirement. There may be two databases that are functionally identical because their name will always ensure uniqueness. There may also be two attributes in the same relation that associated with the same datatype because each will have a unique name.Tuples are the singular entity in the relational model that do not have an inherent unique identifier. The variables within each tuple are uniquely associated with an attribute of the relation. The tuple itself only has one way to be uniquely identified, itself. For this reason, each tuple in a relation must be unique. No two tuples may be comprised of variables associated with the exact same values.
As mentioned in the definition above, keys come in two varieties: local and foreign. Local keys designate one or more proper subsets of the attributes of the relation which must also have unique values for every tuple. Each local keys restrict the possible tuple values and create a functional dependence between attributes not in the key on attributes in the key.
Note that the definition of a relation creates an implicit "key" on the set of all attributes, since each tuple must be unique. If a relation has an explicitly defined key on one attribute, no more than one tuple in that relation may ever have each of the possible values for that attribute. Other attributes for which there is no key may have duplicate occurrences of the same value, both collectively and each individually.
A key may include more than one attribute, when it does it does not constrain values in each attribute, but rather the pair, trio, quartet, etc. of attributes. That is to say, if a there is local key on a single boolean attribute the relation may have exactly two tuples: one for key "0" and one for key "1". It there is a local key on a pair of boolean attributes the relation may have four tuples with keys: "00", "01", "10", and "11". This is not the same net effect if each attribute was in a key by itself. In this case there could be any two of the previous four pairs. The existence of the third would always logically violate the uniqueness constraint on one of the two attributes. Of "00" was the first tuple defined, the only other tuple could be "11" since "01" would violate the uniqueness of the first column and "10" would violate the uniqueness of the second.
Attributes may appear in more than one key, and though keys are named, and therefore not required to be functionally unique there is no reason to have non-functionally-unique keys.
Foreign keys are defined as:
- a set of n attribute pairs where:
- Each pair must have exactly
- one attribute in the "local" relation and,
- one attribute in some other relation, a "foreign relation".
- Both attributes in each pair must be of the same type.
- The foreign relation for every pair must be the same relation.
- The set of foreign attributes from all pairs is exactly the set of at least one local key in the foreign relation.
- No attribute, local or foreign, may appear in more than one pair.
- Each pair must have exactly
Just as local keys enforce an additional uniqueness constraint on values associated with the attribute (on top of constraints from that attribute's type), foreign keys also enforce an additional constraint. Instead of requiring that values be unique, the foreign key requires that values associated with the attribute be in the set of values of the foreign relation. As an example, if the type of the attribute is boolean as in the earlier example and the foreign relation has only a "1" value, the foreign key would require that the local relation only have a "1" value. If that attribute in the local relation was also a local key, the relation could only have one tuple at all. If the attribute was not also a local key in the local relation, the relation could have multiple tuples, so long as each tuple was unique and no tuple had a value for that attribute other than "1". Foreign keys limit the value in the local attribute to the set of values associated with the foreign attribute. This is always a subset (though not always a proper subset) of the attributes type.
The Relational Model, and many database technologies draw a distinction between different types of what this series will call "local keys": primary and candidate. These can be semantically important when working directly with specific database technologies, but the prescribed design practices will make distinction unnecessary aside from implementation specific quirks.
Just as relations have a type as defined by the set of attributes, keys too have a type based on their own set of attributes. The type of a foreign key includes the name of both the local and foreign relations. Key types in-and-of-themselves are not an important consideration in the design practices that will be discussed, but they give rise to another type that is central: Correlation Types.
Correlation Types, Direct
In relational databases, everything is connected to some extent. The most basic correlation is between all the information that is explicitly stated. All of the information represented is said to be "true". Information not represented is assumed false. Information in each database, at the very least, is related by its presence in that database. Each database is a different context of some sort. Presence in one database, but not another says something about that information, though exactly what is says hinges largely and subjectively on the designer's intent. Two different databases may represent the exact same types of information, entirely different types with no overlap, or some compromise between these two extremes.The strongest form of correlation in a database is the direct correlation, a one-to-one mapping. Direct correlations come in two varieties: those formed between functionally independent values in a tuple, those formed between functionally dependent values in a tuple.
In the relational model, the attributes of a relation variable define one-to-one (reciprocally required) relationships between two value types. This implicit relation is the only acceptable method of creating a one-to-one relationship directly between two values. It is also conveniently the only method required.
Mathematically speaking, each tuple of i attributes defines ((i-1)^2 + i-1) / 2 direct correlations. In relations with no explicit keys, all of the values are said to have an independent correlation with each other. This means that any combination of any of values in the tuple that otherwise conform to the associated attribute type constraints are allowed.
Relations with at least one key however create a different kind of correlation between the set of values participating in the key, and the set of values not participating in the key. This distinction hinges on the notion of Functional Dependence, but to keep the definition simple for the purpose of this series an assumption will be made:
To simplify design decisions, it is helpful to consider that in a highly normalized database it is rarely the case that any key with more than one attribute is needed. It follows to infer that, as much as possible, the design methodology this series describes will avoid keys using multiple attributes in a key. With this assumption in mind, rather than saying one set of values of functionally dependent on another set of values, it is possible to say one ore more individual values is functionally dependent on one or more single values.
A functional dependency between two values means that the value of one in some way constrains possible values within the same relation for others. In a relation, if value B is functionally dependent on A then the following statements are true:
- A is a local key, thus there are no duplicate values for A.
- Because there are no duplicate values for A, there is exactly one value for B for each value for A.
This notion of correlation is specifically directional, meaning that while the correlation may be reciprocally identical for both participants in some cases, there are other cases where the nature of the relationship for each participant is different. For direct relationships between values in a tuple two values may be:
- mutually dependent, or
- one may dependent on one that reciprocates the relationship independently, or
- they may be mutually independent values.
Correlation Types, Indirect
When two values are in the same tuple a direct correlation occurs. Two values in different relations that are related to each other through one or more foreign keys have an indirect correlation.The interplay between the attribute that creates a foreign key, and the local key in another relation it points to creates a different kind of constraint than functional dependency. Take the following entities into consideration:
- Attribute A with value a in Relation X, which is a local key
- Attribute B with value b in Relation X
- Attribute C with value c in Relation Y, which is a local key
- Attribute D with value d in Relation Y
The local key on A adds further constraint from dependent correlation such that for every a there is only one value for b. There may be multiple values for a for each b however.
The same two statements above also apply to C, c, D, and d. as the relationships mirror those of A, a, B, and b respectively.
So far, nothing can be said about any relationship between A and C, A and C, A and D, or B and D.
There is nothing mutually exclusive about attribute's ability to be a local key and a foreign key. Attributes may be either, neither, or both. The basis for different indirect correlation types and the functional effect they have on relationships between values focuses on the following two conditions:
- Whether the foreign key is also a local key or not, and
- The foreign key's significance as a local key (when applicable).
In the formal Relational Model, many authors discuss two forms of local keys: Primary keys and candidate keys. Technically speaking, the distinction is arbitrary. Implementation specific quirks aside, there is no functional difference in the relational model between primary and candidate keys. This is precisely the reason these two terms are not used elsewhere in this series. If a pure theory approach is taken, it suffices to say that all "local keys" are candidate keys and if one is assigned as a primary key arbitrarily there is no technical significance to that selection.
This goes back to the earlier point about difference in the pure theory, and human friendly design choices. There is sometimes disagreement about why normalization is good, bad, or important, or undesirable. Reasons for normalization include both robustness and economy of storage. The compromise this design process will exemplify considers the following from most to least important:
- Normalization towards making the database more robust is important.
- For the most part, the relational database and any complexities introduced by adhering to sound theory will be abstracted, so high normalization is good.
- Some human will eventually or occasionally have to directly interact with the relational database.
- Normalization as a means to drive down storage requirements is a lower priority than the above.
- for every relation there is a primary key which is a single attribute, and
- unless there is a significant and deliberate reason to identify a natural key (being a value inherently part to the data being stored)
- the primary key will be an artificial key.
As mentioned, by default the assumption is that for every relation there is a primary key comprised of a single attribute. For most relations the safe assumption is to assign an artificial primary key, and many relational database technologies make this easy. An artificial key is a value that is part of each tuple but does not functionally change the information the tuple represents.
It has already been mentioned that in the relational model tuples alone lack a unique name. Databases, relations, attributes, and keys are all named uniquely. The notion of a local key is vaguely analogous to a the unique names available to other entities in the relational model. Any local key for a relation can be used to select exactly one tuple uniquely. The notion and perceived importance of a "primary" key is probably deep seated in the human tendency to name and label things.
Sometimes the information represented by a tuple inherently includes a "unique identifier". The identifier is part of the information. When this unique identifier is truly unique, meaning no other distinct tuple in the relation could ever logically use the same identifier. This means all the other information in the tuple is functionally dependent on the identifier. It stands to reason then that it would be desirable to make that identifier a local key, and as it turns out this is exactly the right design decision.
The problem however is that while this part of the information may always be unique, the decision to make it an identifier is a bit tricker. Uniqueness is a semantic property that can safely be relegated to local keys. Identity on the other hand presents a challenge: could the value with the identity change? The semantic property of identity can take on different meanings depending on the intent of the designer. Exactly what is meant by "semantic" will be covered in the next post, but for now it is important to simply state that from a design perspective it is undesirable for the identity associated with a tuple to ever change. For this reason the assumption is that the identifier attribute chosen (the primary key) for each relation is one that is arbitrary assigned by the database and is never changed.
Designers may explicitly decide that a primary natural key is appropriate for a relation. There are certainly cases where this choice makes sense. It is however a choice that should be both deliberate and carefully made. Beyond this point this series will only refer to primary keys as identifiers when they are artificial keys and natural identifiers otherwise.
To return to the reason for this explanation of the significance of a local key to its relation, identifiers and local keys that are not identifiers have slightly different meanings. Both convey the exact same logical constraints on a values, what distinguishes the two is the designer's intention behind the correlation they create. The three basic indirect correlation types, and variants of each are the focus of the remainder of this post.
Super Correlation
The first correlation type is the Super correlation. Take as an example slightly modified versions of the previous relations X and Y:- Attribute A with value a in Relation X, which is an identifier for X
- Attribute B with value b in Relation X
- Attribute E with value e in Relation Y, which is an identifier for Y and foreign key to A
- Attribute F with value f in Relation Y
- Y relates additional information to some tuples of X, but not necessarily all tuples of X
- there may be no more or fewer than one related tuple in X for each one in Y
- there may be no more than one related tuple in Y for each one in X
- thus, the super correlation's cardinality considered is a one-to-zero-or-one.
The next post will clarify how value types and correlation types are similar and how they are different. For now it will suffice to mention that this series will focus on a type oriented approach to design and that every type mentioned is a subtype, supertype, or both of some other type.
Interestingly, the super correlation itself has no subtypes (only supertypes).
Enum Correlation
A similar looking, but different functioning correlation type is the Enum relation. Given the a definition for X and Y:- Attribute A with value a in Relation X, which is an identifier for X
- Attribute B with value b in Relation X, which is a foreign key to E
- Attribute E with value e in Relation Y, which is an identifier for Y
- Attribute F with value f in Relation Y
- Every tuple in X must correlated to a tuple in Y, and
- multiple tuples in X may correlate to the same tuple in Y
- tuples in Y exist independently of any correlation from X, meaning there may be tuples in Y that do not correlate to and in X
- thus the enum correlation's cardinality considered is a zero-or-many-to-one.
There is one specialized version, a subtype, of the enum correlation: Unique Enum. In this correlation type the foreign key (in X) is also a local key, but not an identifier. The result is that while tuples in Y represent options for a value in tuples in X, the cardinality is different: zero-or-one-to-one.
This cardinality is the same (just in the reverse direction) as that of the super correlation, but the conveyed design intention is different. It means that Y represents options for values in tuples in X, but each option represented in Y may only correlate to exactly one tuple in X, and not all options in Y have to be represented in X. In the unique enum, instead of saying that X aggregates Y it can instead be said that X owns from Y.
Jointype Correlation
The third common correlation type involves three relations rather than just two. It also has two subtypes. These relations are defined as:- Attribute A with value a in Relation X, which is an identifier for X
- Attribute B with value b in Relation X
- Attribute C with value c in Relation Y, which is an identifier for Y
- Attribute D with value d in Relation Y
- Attribute E with value e in Relation Z, which is an identifier for Z
- Attribute F with value f in Relation Z, which is a foreign key for A
- Attribute G with value g in Relation Z, which is a foreign key for C
The foreign key association through Z creates an indirect many-or-zero-to-many-or-zero between X and Y. This jointype is formed by two enum relations, but is defined be the indirect correlation between X and Y, not either of those two relations' direct correlation to Z. The properties of this correlation type are:
- each tuple in X exists independently of tuples in Y and Z
- likewise, each tuple in Y exists independently of tuples in X and Z
- there is no restriction on how tuples in Z may refer to tuples (so long as they exist) in X, Y, or any combination of the two so long as for every correlation to some tuple in X there is exactly one to some tuple in Y and vice version.
The two subtypes of the jointype relation involve one or both of the enumtype correlations from Z being converted into a super correlation.
In an Enum JoinType correlation, one of the foreign keys in Z associated with an identifier in X (or Y, but for the purpose of this definition it will suffice to pick only one) is also a local key. This creates a super correlation between X and Z. The correlation between Z and any other other relations that are still enum correlations remains unaffected.
The effect of this change between X and Y is that now in Z there is a functional dependency of g on f, and thus there may only be up to one correlated tuple in Y for each tuple in X. Tuples in X and Y may exist independently of any correlation from Z or from each other. The cardinality of the relationship between X and Y becomes zero-or-one-to-zero-or-many.
While is it important to note that the local key in Z on X (or Y) does not have to be the identifier for Z, in most cases it should be. The main consideration is that as stated above, the identifier for a tuple should never change. If the correlation between X and Y is defined as a trait of the information that X represents, then using that F as the identifier for Z is worth considering (or likewise for G if the information Y represents defines the correlation between the two). The distinction is subtle, and best left alone if there is any doubt.
In a Unique JoinType correlation, both of the foreign keys in Z associated with identifiers in X and Y are also local keys in Z. This creates a super correlation between X and Z and between Y and Z.
The effect of this change between X and Y is that now in Z there is a mutual functional dependency between g and f , and thus there may only be up to one correlated tuple in Y for each tuple in X and vice-versa. Tuples in X and Y may exist independently of any correlation from Z or from each other. The cardinality of the relationship between X and Y becomes zero-or-one-to-zero-or-one.