"Converting SQL to Relational Algebra", part II

When I wrote the first posts in this blog, it seemed to generate traffic from places I found rather curious, until it occurred to me that search engines are not entirely unlikely to present "Relational Model" as a useful search result to people who are searching for a Relation with a Model ...

Likewise, the former post on the same subject as this one, gave quite some traffic, and it seems not unreasonable to assume that most of that traffic was from students who were looking for info on how to solve "Convert SQL to RA" problems, and who were not looking for my philosophical agonies on why these problems are even being taught ...

As somewhat of an apology to all those disappointed students, and to prevent further disappointments in the future, a concise set of guidelines, in the form of SQL_KEYWORD to RA_OPERATOR mappings, and whatever additional comments I think might be useful.

SELECT maps to (any combination of) PROJECT, RENAME and EXTEND.

If the select clause involves exclusively column names of the table defined in the FROM clause, then PROJECT is all that is involved.

If the select clause involves constructs such as <columnname> AS <othercolumnname>, then a RENAME is involved as well.

If the select clause involves scalar expressions (quantity+1, HOUR(<colname>), ...), then an EXTEND is involved.  Note that if such scalar expressions are not followed by an AS <colname> construct, then there is no relational equivalent for this SQL, because the SQL yields an unnamed column, and the relational model and/or the relational algebra do not allow unnamed attributes.  Note also that if the expression "quantity + 1" is used in a SELECT clause (and quantity is a column of the table in the FROM clause), then the EXTEND operation by itself will not "project away" the quantity attribute.  Don't forget to explicitly PROJECT away such attributes in the RA formulation.

In all cases, observe that Relational Algebra does not allow duplicate rows, but SQL does.  If the SQL

SELECT QUANTITY FROM ...

could possibly give rise to the same quantity appearing multiple times in the result table, then there simply isn't any relational-algebra equivalent of this query.  In such cases, for the query to even have a relational-algebra equivalent, it is required that the SELECT is a SELECT DISTINCT.


FROM maps to CARTESIAN PRODUCT, NATURAL JOIN, or just nothing at all.

It maps to nothing at all if (and I think only if) its comma-separated list of table expressions has cardinality one.  In that case, the table expression simply defines the input argument to the "surrounding" [combination of] PROJECT/RENAME/EXTEND.

It maps to NATURAL JOIN between pairs of table expressions (say, T1 and T2), if and only if, for all the columns that have the same name in T1 and T2, there is an equality condition in the WHERE clause (WHERE T1.<colx> = T2.<colx>).

In all other cases, it maps to CARTESIAN PRODUCT.  Note that in CARTESIAN PRODUCT, the tables involved are not allowed to have any column names in common.  You might need to introduce additional RENAMEs in order to resolve/do away with any such column name overlappings.  Also note that whatever you write in front of a dot, does not magically become part of the column name itself.  Not in SQL, and, well, relying on it in some RA notation isn't a very attractive idea either.



WHERE maps to RESTRICT, or SEMIMINUS (aka ANTIJOIN), or SEMIJOIN.

It maps to RESTRICT if the WHERE clause involves boolean expressions comparing columns of the table against each other, or against literal values.  E.g. WHERE <colname1> != <colname2>, WHERE HOUR(<colname>) BETWEEN 8 AND 18, ...

It maps to SEMIJOIN if the WHERE clause involves an EXISTS(...) construct.  The nature of the inner SELECT embedded in that clause will give you the second argument for the SEMIJOIN.  Note that this inner SELECT might contain a WHERE clause itself, and that the nature of this WHERE clause may dictate that additional RENAMEs might have to be applied to this second argument.  For example,

SELECT ... FROM T1 WHERE EXISTS ( SELECT * FROM T2 WHERE T2.A = T1.B)

requires a RENAME to be applied to T2, renaming A to B, in order for RA's SEMIJOIN to expose the same behaviour as the SQL EXISTS(...).

And finally, WHERE maps to an ANTIJOIN if the WHERE clause involves a NOT EXISTS(...) construct.  All remarks for SEMIJOIN apply here as well, mutatis mutandis.

If >1 of these constructs are involved in the WHERE clause, then these constructs will have a logical connective between them.  Split the overall query in as many parts as are needed (one for the scalar conditions, one for each EXISTS and one for each NOT EXISTS).  Each logical connective so eliminated becomes a NATURAL JOIN or INTERSECTION if the connective was AND, and becomes a UNION if the connective was OR.  The nesting of these INTERSECTIONs and UNIONs is as dictated by the parentheses and/or the precedence rules between the AND/ORed expressions in the SQL.



GROUP BY ...  HAVING ... maps to nothing at all.  Or more precisely, if you are studying for an exam, do as your course tells you, and try to forget it as soon as possible after you've passed the exam, because whatever you were told in your course/classes was probably about the biggest crap one could imagine.

The same applies if you don't see any GROUP BY ..., but your SELECT clause has an aggregate function in it, like, say, SELECT SUM(QUANTITY) FROM MYTABLE.  That's logically the same as having an "empty" GROUP BY clause.

There do exist definitions/versions of Relational Algebra that can properly handle all this kind of aggregation-like functionality, but it is unlikely that you have been taught these.  So, do as your course tells you and forget it ever after.



UNION maps, unsurprisingly, to UNION.  But do note that basically the same remark applies as with SELECT/projection : Relational Algebra does not allow duplicate rows.  So if your SQL UNION could possibly give rise to duplicate rows, then this UNION query simply does not have any relational-algebra equivalent.



Modern SQL also has operators such as EXCEPT, INTERSECT, NATURAL JOIN, JOIN ...ON ...  These map to relational difference, relational intersection, natural join, or some combination of natural joins and cartesian products, mostly in obvious ways.



FROM clause missing ...  That's not standard SQL, but some products allow it (and as a consequence, some courses may even teach it).  In principle, SELECT statements without a FROM clause are used to denote table literals.  Use whatever notation your RA course used for denoting relation literals.

A letter by Carl Hewitt

Recently, an article by Erik Meijer entitled "all your databases are belong to us" created a bit of commotion among Relationlanders.  One Carl Hewitt subsequently wrote a letter in support of Meijer's article.  A few observations and personal thoughts about Hewitt's letter.

Hewitt writes :

"Relational databases have been very useful in practice but are increasingly an obstacle to progress due to the following limitations:"

This clearly implies that mr. Hewitt believes that at least once upon some time, a relational database has actually ever existed somewhere, and he has been able to observe, directly or indirectly, that that database was "useful in practice".  Considering the overwhelming evidence that SQL is not relational, I wonder what "relational database" mr. Hewitt has so observed to be "useful in practice".  Anyway.  Is mr. Hewitt unaware of the difference between "relational technology" and "SQL technology" ?  Or does he consider the difference (and its consequences) between the two so meaningless and futile that it does no harm at all to gloss over that difference and speak of SQL as if it were indeed relational ?

Besides.  Looking at his arguments in support of his claim (inexpressiveness of the RA, for example), one cannot help but wonder if mr. Hewitt is even aware of the difference between a "database" (that's the word he used) and that thing that most knowledgeable people usually use the term "DBMS" for ...  Can "inexpressiveness of the RA" possibly a shortcoming of "an organized collection of data" (if so, how ?), or could it only possibly be a shortcoming of "the software system, the foundations of which are in RA, used to manage the collection of data" ?

What does that tell you about how thorough, accurate and meticulously precise mr. Hewitt tries/bothers to be in his published writings ?



Hewitt writes :

"Inexpressiveness. Relational algebra cannot conveniently express negation or disjunction, much less the generalization/specialization connective required for ontologies;"

Codd's Relational Algebra was proven equivalent to predicate calculus, no ?  So that means that Codd's RA can express both negation and disjunction, right ?  And subsequent definitions of RA that emerged over time (think, for example, of the addition of a transitive closure operation) did not exactly remove the MINUS operator from the existing algebra, right ?  So that indicates that the key operative word in the claim is that vague qualification "conveniently", right ?  Using such a word without being precise about its intended meaning, is just cheap handwaving.

Anyway, the RA has MINUS (and its nephew SEMIMINUS, aka antijoin), and Relationlanders have known for over 40 years that this operator perfectly suits the purpose of expressing any predicate like "... and it is not the case that ...".  It remains an open question what mr. Hewitt thinks is "inconvenient" about writing things such as "<xpr1> MINUS <xpr2>" in, say, Tutorial D code.

Also, there is nothing to stop anyone from defining an algebra that has a "complement" operation (well, so long as all the domains/types are finite, presumably).  This algebraic operation by itself is the exact relational counterpart of the logical operation of negation, taken by itself.  Having to actually compute complements will be contraindicated in most circumstances, as it will typically involve actual computation of what is known in relationland as the "universal relation" for a given heading.  All of that is probably exactly the reason why Codd did not want to include such a "complement" operation in his algebra.

At any rate, I'm still left wondering what mr. Hewitt's problem is here.



Hewitt writes :

"Inconsistency non-robustness. Inconsistency robustness is information-system performance ..."

Note very carefully that Hewitt's complaint here is that the RM lacks "inconsistency robustness", which he then defines to be a performance characteristic.  Performance is not a characteristic of the model.  Anyway. Once writers start going down this alley, readers can already suspect the kind of , eurhm, "talk" that is about to follow ...



"... in the face of continually pervasive inconsistencies, a shift from the once-dominant paradigms of inconsistency denial and inconsistency elimination attempting to sweep inconsistencies under the rug. In practice, it is impossible to meet the requirement of the Relational Model that all information must be consistent, but the Relational Model does not process inconsistent information correctly. ..."

"Inconsistent" in the context of data[base] management, means the presence of information that is in violation of some stated rule that is supposed to apply to the database.  Or iow, that accepting the "inconsistent" information in the database, makes the proposition that states that the violated rule holds, a false one.  Or iow, the proposition that states that the rule holds in the database, is in contradiction with the "inconsistent" information.  Or iow, accepting inconsistent information in the database is tantamount to accepting contradictions.

And I've been told that it is a proven property that you can prove really just anything from a contradiction.

In RM, it is "possible" to consider "inconsistent information", just like in 2-valued propositional and/or predicate logic, it is "possible" to consider contradictory propositions/predicates.  Querying an RM system that holds "inconsistent information" is like applying the rules of logical reasoning to a set of contradictory axioms/premisses.  And blaming the RM for "not processing inconsistent information correctly", is like blaming logic for "not dealing with contradictions correctly" (where by 'correctly', it is implied that it should be something other than just 'false', of course).




"... Attempting to use transactions to remove contradictions from, say, relational medical information is tantamount to a distributed-denial-of-service attack due to the locking required to prevent introduction of new inconsistencies even as contradictions are being removed in the presence of numerous interdependencies;"

Anyone who is familiar with the RM, and also with how it is typically criticized, will recognize this immediately as criticizing the model on grounds of implementation issues (locking and transactions), which are orthogonal to the model.  Typical.



Hewitt continues :

"Information loss. Once information is known, it should be known thereafter;"

Should it really ?  I dispute that.  A requirement to never ever ERASE or DELETE or REMOVE just anything, will inevitably bring us to the point where planet earth does not have enough atoms to store all our stuff.

At any rate, there is absolutely nothing in the RM that prevents any database designer from defining structures that keep a record of "which information was known to the database owner during which period of time" and/or "at which point in time the database owner regarded this particular piece of information as no longer relevant and removed it from his operational system".  Even SQL has included features to support such stuff in the new 2011 standard.

And in the end, when to DELETE a piece of information, should be at the user's discretion (if regulatory bounds apply, then that user should of course be staying within those bounds, if that wasn't obvious), not at the model's discretion.



Hewitt still hasn't finished :

"Lack of provenance. All information stored or derived should have provenance;"

There is absolutely nothing in the RM to stop a DBMS user from defining structures that record exactly the kind of "provenance" information that Hewitt is talking about (whatever that may be), there is nothing in the RM to stop a DBMS designer from building facilities to automagically populate such structures, and there is nothing in the RM to stop a DBMS user from using such facilities.

Nor should there be any such thing in the RM.



And on and on it goes :

"Inadequate performance and modularity. SQL lacks performance ..."

So once again he unambiguously states that he thinks that "The RM is obsolete" (that's what the title says) because "SQL lacks performance".  OMFG.



"... because it has parallelism but no concurrency abstraction. Needed therefore are languages based on the Actor Model (http://www.robust11.org) to achieve performance, operational expressiveness, and inconsistency robustness. To promote modularity, a programming language type should be an interface that does not name its implementations contra to SQL, which requires taking dependencies on internals."

Is the term "programming language type" used here with the same meaning as the term "data type" in relationland ?  If so, then the last sentence seems to demand nothing else than that which relational advocates have been demanding for decades already : that the relational model should and must be "orthogonal to type", that is, that it is not up to the model to prescribe which data types should exist/be supported, and which shouldn't.

Of course, relationlanders have known for a long time already that SQL basically flouts that idea, and that its attempts at supporting -in full- the notion of abstract data types are quite crippled and half-baked.  But apparently it does indeed seem to be the case that mr. Hewitt mistakenly equates "the relational model" with SQL.



And Hewitt concludes :

"There is no practical way to repair the Relational Model to remove these limitations."

Well, this is the first time I can agree with something Hewitt says.  Sadly, as far as I can tell, "these limitations" are not limitations that derive from the Relational Model, rather they seem to derive from his limited understanding thereof.  And indeed there is no repairing a piano when the problem is in its player.

"Converting SQL to Relational Algebra"

It's that time of the year again.  Introductory courses in relational data management (I'm a bit reluctant to call them "courses in relational theory") are starting again, all over the world, and consequently, students seeking advice and assistance from "professionals" start posing "Converting SQL to Relational Algebra" questions again on various database-related discussion fora, when they are not able to solve assignments given to them in class, or when they are uncertain their solution is correct.

I would actually like any of the teachers who give such assignments to try and explain to me what purpose they hope to be achieving by giving such assignments.  What do students learn from this ?  I recently got involved in such a "Converting SQL to Relational Algebra" question, and one remark the student made, in the discussion that ensued, confirms my feeling regarding this : they learn nothing at all, and "Converting SQL to Relational Algebra" is completely pointless, only adding to the confusion instead of resolving it.  (The remark was, literally, : "we do not either understand why we are learning this".)

Why is this so ?  Well, it's because Relational Algebra is foundational, and SQL is not.  That's because Relational Algebra is completely abstract, and SQL is not.  Not in the same sense that Relational Algebra is abstract.  SQL is abstract with respect to the procedures and algorithms that the implementing engine executes in order to carry out a given SQL command.  But that is not quite as "profound" or "foundational" a level of abstraction as the one the Relational Algebra can be said to have.

SQL is just a syntax for expressing formulae of the RA.  One possible syntax for it.  Of the plethora of distinct possible syntaxes that can be conceived to do the same.  And SQL is an awful syntax for that purpose, come to that.  That's because initially, SQL was firmly rooted in predicate calculus, not in relational algebra.  That SQL can express relational algebra, is only a "coincidental" consequence of the fact that predicate calculus and relational algebra were later proven equivalent.  That historical reason is why, for example, relational difference had to be expressed using WHERE NOT EXISTS (...), and EXCEPT was only introduced in the standard decades later.

Granted, if you teach RA first and only then SQL, you are headed for a shit load of questions, "why did they make that syntax so quirky if the algebra is so simple" ?  The answer is always the same : poor historical reasons.  BTW there's a great book forthcoming that fits this line of teaching perfectly.  But at least they could understand.

And the fact still remains that if students can first manage to understand RA, then they can understand any language that implements or supports it.  They will then understand that, as far as RA operations are concerned, the difference between SQL and, say, Tutorial D, is a mere matter of syntax.  They might understand that the Tutorial D expression 'R1 JOIN R2' is the very same thing as the SQL expressions 'SELECT * FROM R1,R2 WHERE R1.<attr> = R2.<attr>', 'SELECT * FROM R1 JOIN R2 ON ...' and 'SELECT * FROM R1 NATURAL JOIN R2'.  And the reason they would understand, is precisely that their thinking would be in RA, not in SQL or any other specific language.

We urgently need to learn our database designers to think of data in terms of sets (sets of tuples, where those sets represent the extension of a logical predicate, and each tuple represents a proposition), and to think of manipulations on that data in terms of relational algebra.  Not in terms of tables and SQL.

And it means that the teaching should no longer be about "Converting SQL to relational algebra", but instead about "Converting relational algebra to SQL".  The latter, not the former, is the sensible way of doing things.

"Why EAV sucks"

We've already seen this one before as an illustration of a cartesian product establishing a tuple type :

I:INT X C:CHAR = {(I:1,C:'A') , (I:1,C:'B') , ...}

and one possible relation deriving from this :

R = { (I:1,C:'A') , (I:1,C:'B') }

or, rewriting those tuples as sets of pairs mapping attribute names to values of arbitrary domains :

R = { {(I,1),(C,'A')} , {(I,1),(C,'B')}}

In tabular form (a fairly typical form for representing relation), this could become something like

I	C
1	A
2	B

Well, tables consist of rows and columns, and with this particular view of a relation, both rows and columns turn out to have an interesting property.

Beginning with the rows.  It is obvious that one row contains precisely one tuple of the relation.  Nothing more and nothing less.  And one tuple corresponds to exactly one logical proposition that it represents.  That logical proposition being a sentence, a statement of fact.  For example, "Yesterday, the average temperature in room A was 1 degrees centigrade.".

Then the columns.  What is common for all the things mentioned in the column labeled 'I' ?  They are all numbers originating from domain INT.  Likewise for the things mentioned in the column labeled 'C'.  In our data manipulation language, this means that if we have a reference to column (/attribute) 'C', we just know that what we're referring to is a CHAR value.  We don't need to typecheck this at runtime.  It's guaranteed by the typechecks that occurred when the tuple was inserted.

Remember these two.  They're important.

A closer look at one of these two tuples themselves now.

{(I,1),(C,'A')}

That's a set of ordered pairs.  The first member of each pair coming from the domain of 'valid attribute names', the second coming from ...   Well from what exactly ?  We can't say that the second member of all pairs here comes from INT, nor from CHAR, nor in fact from any domain we used to build tuple types and relations with.  Rather, all we can say is that it's just some value from some domain, but we don't know which it is.  (We can know which one it is, by inspecting the value of the first member (the attribute name), and then linking that somehow to the original way in which we defined our cartesian product/tuple type.)

Anyway.  A "set of ordered pairs" is a relation, thus a tuple is itself also a relation.  (But do keep the distinction in mind between "relation over the domains INT and CHAR" and "relation over the domains ATTRIBUTENAME and SET_UNION_OF_ALL_DOMAINS").

Anf if a tuple is itself also a relation, we could try out what we get if we wanted to represent it tabularly using the usual technique :

??????	??????
I	1
C	A

Compare with the "interesting properties" of the (tabular representation of) the relation.  Does the interesting property of the column still survive ?  No it doesn't.  Unless we find the fact of possibly getting back just anything from any expression in our data manipulation language an "interesting" property.  Does the interesting property of the rows (tuples of a relation) still stand ?  No it doesn't.  It just tells us that there has been a temperature of 1 degrees centigrade yesterday, in some further unspecified room, for example.  (But note that in order to derive so much information, we need to inspect the value of that "first column", and iterate over a set of used attribute names : "if it's C then that value is a room identifier.  No it's not C.  If it's I then that value is an average temperature.  Ah yes that's the one.")

(Aside.  The question marks are there for a reason.  What would you put in their place ?  Can the user of a system based on this paradigm of tuples-as-relations be given the freedom to choose his own preferred replacements for the question marks, in a sense similar to how the designer of a database is at freedom to choose his attribute names, when defining cartesian products aka tuple types ?  End-of-aside.)

One step further in the predictable direction.  Take a look at

??????	ATTRIBUTENAME	VALUE
GUID-WXCVBN-AXIO	I	1
GUID-WXCVBN-AXIO	C	A
GUID-WXCVBN-AX1O	I	2
GUID-WXCVBN-AX1O	C	B

This table was obtained by prepending something very akin to a "tuple id", "entity id" or "object id" to the table, and then using those values for identifying "which attribute values belong together to form a tuple".

Looks like anything you know ?  Rhetorical question.  This is EAV.  Strip the RM from its connection to predicate logic (that is, remove the connection with 'meaning') and strip the RM from the static type checking that is offered by its most foundational building brick, the tuple (that is, remove the most fundamental data integrity feature of all), and what is left is EAV.  As another commenter put it : "disassemble the tuple and amputate the predicate".

Some thought exercises.  Assume you want to design a database like this.  Assume the name in place of the question marks is 'OID'.  Write all the needed constraints on this three-column table to effect the following :

- values corresponding to the ATTRIBUTENAME 'I' must be of domain INT.
- values corresponding to the ATTRIBUTENAME 'C' must be of domain CHAR.
- only complete tuples can be inserted.  That is, if an I or a C is inserted, then so must the corresponding C or I be.
- only complete tuples can be deleted.  That is, if an I or a C is deleted, then so must the corresponding C or I be.


These four constraints all derive naturally from a relational declaration as simple as (two examples)

VAR RELATION {I:INT C:CHAR} IC ;

CREATE TABLE IC (I INT, C CHAR) ;

Which of the two approaches is the easiest and the simplest ?

Further thought exercises.

A constraint must be introduced to the effect that "the I value must be less or equal than the position of the C value in the alphabet."  Write a query to check whether this constraint is currently satisfied by your EAV database, and spell out the strategy you're going to follow to enforce this rule.  Is it simpler or easier or less work involved than the following ? (two examples)

CONSTRAINT IC_RULE1 ALL(IC, I<=INDEXOF(C,"ABCDEFG...XYZ")) ;

ALTER TABLE IC CHECK (I<=INDEXOF(C,"ABCDEFG...XYZ")) ;

A constraint must be introduced to the effect that the I values are unique identifiers for any tuple.  Write a query to check whether this constraint is currently satisfied by your EAV database, and spell out the strategy you're going to follow to enforce this rule, or write out the declarative constraint that will enforce this in your EAV database.  Is it simpler or easier or less work involved than the following ? (two examples)

VAR RELATION {I:INT C:CHAR} IC KEY {I};

ALTER TABLE IC KEY (I) ;

Further thought exercise.  Read this sentence carefully.  Now look at the following EAV structure.

??????	ATTRIBUTENAME	VALUE
GUID-WXCVBN-AXIO	POS	1
GUID-WXCVBN-AXIO	WORD	Read
GUID-WXCVBN-AXOO	POS	3
GUID-WXCVBN-AXOO	WORD	sentence
GUID-WXCVBN-AXO0	POS	4
GUID-WXCVBN-AXO0	WORD	carefully
GUID-WXCVBN-AX1O	POS	2
GUID-WXCVBN-AX1O	WORD	this

I could write that same sentence, in cryptic form, in four lines :

Word 1 in the sentence is Read.
Word 3 in the sentence is sentence.
Word 4 in the sentence is carefully.
Word 2 in the sentence is this.

And EAV even goes beyond that in turning that into 8 lines !  How much work and computation does it involve to reassemble the original sentence from this ?



All of that should be sufficient to illustrate how much veracity there is to the claim that "EAV makes database maintenance easier".  Instead :

If you do not care about the data type of (the values in) your database fields, then EAV is your thing.
If you do not care about the meaning of the contents of your database, then EAV is your thing.
If you do not care about the integrity of your data, then EAV is your thing.

(In each of these cases, "do not care" is supposed to also include the notion that "the user doesn't mind paying all those extra hours you put in solving problems that the DBMS has already solved for you".)

"Types, Sets, Tuples, Headings, Relations, a set mess ???"

That's a long title, and it's intended to illustrate how all of that stuff that actually underpins the Relational Model of Data, mathematically speaking, may come across as "one big tangled mess of almost-but-not-quite similar-or-equal concepts all thrown on a big pile".

And the body of this installment is about illustrating how it really is not that "perceived mess".

The following example has been used more than once already in this little corner of the internet.

I:INT X C:CHAR = {(I:1,C:'A') , (I:1,C:'B') , ...}

At this point, I need to take one more step back to basics.  The foregoing definition assumed it to be "known" or "agreed-on" what those domains INT and CHAR precisely were, respectively.  I.e. what its constituent members are.  The thing to note is that those "domains" are sets, and their members are values :

INT = {1 , 2 , ...}

CHAR = {'A' , 'B' , ...}

And that's really all it takes to be a type.  A type is a set of values.  And a value can be whatever we want it to be.  If I have a good use for the set of guitar chords, I can choose that to be a type.  If I have a good use for the set {cloud, oak, armchair} or {scissors, stone, net}, I can choose that to be a type.

(Aside : of course, in a scenario of information exchange, the parties participating in the exchange need to be in full and perfect agreement on what the types are (which values are in it and which are not).  Exchange without such a full agreement is unpleasant surprises in the air and accidents waiting to happen.)


Back to

I:INT X C:CHAR = {(I:1,C:'A') , (I:1,C:'B') , ...}

Obviously, by definition in fact, such Cartesian products are themselves a set.  Are they then also a type ?  The predictable answer is of course 'yes'.  A Cartesian Product is a set of tuples, and if we regard these tuples as being values, then any Cartesian Product of domains constitutes a tuple type.


One step further.  Relations were defined to be any subset of this cartesian product.  Any set is a subset of itself, thus any cartesian product is also a subset of itself, thus any cartesian product is a relation, and since each cartesian product constitutes a tuple type, at least this "maximal" relation ("maximal" subset of the cartesian product of the domains) can also be said to constitute a tuple type.  But all other relations derived from the same cartesian product are also "just sets of tuples".  Likewise, really just any relation can be thought of as "constituting a tuple type".  This holds true even of the empty relation, even though it's fairly counterintuitive to imagine a type that has no values ...  (What could we possibly be using that for ???)

Is all of that important ?  The view of "really just any relation" as itself being, or constituting, a tuple type ?  Not really.  Except perhaps for this.  One could "subdivide" the set of all possible subsets of our cartesian product in three distinct "classes".  The first class consisting of just the subset that is the original cartesian product itself.  The second class being those subsets that can be defined "predicatively", by stating a constraining additional predicate such as, e.g. "I equals 1".  And the third class being "the others".  Pragmatically speaking, this third class can only be defined "by enumeration".  (Formally, there is no real distinction between "by enumeration" and "by predicate", because stating the enumeration is, from the perspective of logic, the very same thing as stating a predicate.)

The third class of subsets is thus characterized by the fact that its definition "looks like", e.g. "It's the tuple type I:INT C:CHAR where either I equals 1 and C equals 'Z', or I equals 5 and C equals 'W'".  Which is a predicate, but one that looks suspiciously much like a full enumeration.

The second class of subsets is thus characterized by the fact that its definition "looks like", e.g. "It's the tuple type I:INT C:CHAR where I equals 1".  A reasonably concise way to define possibly useful subsets/types.

The first class is thus characterized by the fact that its definition is just simply, "It's the tuple type I:INT C:CHAR".  The 'I:INT X C:CHAR' portion is the heading.  The (only) tuple type in this class can thus be said to be characterized by its heading alone.  All other conceivable tuple types with the same heading need an additional constraining predicate to define which tuples are and are not member of the type.  This is the reason why in practice, this particular tuple type is often called "the" tuple type corresponding to some heading (as if there is only one such type).  Formally, this is rather incorrect.  Many tuple types have the same heading, but the one that has all possible tuples, is the most useful, in practice.

The fact that relations are themselves also tuple types, is the source of quite a bit of confusion. The "design dilemma", for example.  (That's the question of whether structures such as 'customer' and 'address' should be conveyed in their own type or not.)  It's not a dilemma at all.  Defining a Customer or Address class in an OO system constitutes defining a type.  The tuple type that corresponds to it is a type too.  Whether or not to give the type a name, is another question, and one that will mostly be moot at that.

On to relations.  If relations are themselves values, then what is their type ?  Well, a type is the set of all its contained values.  Hence, a relation type is a set of relations.  The construction of such a set of relations can be done using the mathematical concept of powersets.  A powerset is the set of all possible subsets of a given set.  So if we :
- start with a tuple type such as the one in our running example,
- enumerate all the possible subsets of that tuple type (that's equivalent to enumerating all the possible relations with that heading)
- and collect all those subsets in a new set,
then this new set is our relation type.

This relation type too is characterized by its heading (and its heading alone).  As with tuple types, this relation type is not the only relation type of this heading, though.  Any subset of the tuple type (e.g. all the tuples that have I>=1, thus ruling out negative numbers), when subjected to the same procedure, will in turn give rise to some relation type (relations with the specified heading and where all its tuples satisfy the predicate that (e.g.) I>=1).  Likewise, subsetting the relation type using some predicate (for example, retaining only "the relations that have at least three tuples") gives rise to some other new relation type.

Typically, however, relational systems do not exploit this property of relation and tuple types.  Instead they give the user the possibility to specify predicates that constrain which relations and tuples can validly appear in which places.  But a system that offered named tuple/relation types, with a constraining predicate, would fundamentally (mathematically) not really be different (in what it allows the user to achieve).

"A difference that doesn't matter"

This question was touched on lightly in an aside of a previous installment, leaving the question mostly unanswered.  The previous post mentioned this to illustrate the concept of a relation as a set :

 +------------------+-------------+--------------

I:INT X C:CHAR = {(I:1,C:'A') , (I:1,C:'B') , ... }

         +--------------+-------------+----------

And then it went on to conclude that for any of those individual tuples, e.g.  (I:1,C:'A')  ,

"We can also think of a (single) tuple as itself being a set, namely a set of ordered pairs in which the first thing is an attribute name and the second thing is "some value drawn from some domain".

And then a sidenote was made observing that other sources ("Introduction to Database Systems") "say that a tuple is a set of ordered triplets", and it was added that "The difference between the two approaches is not [so important]".

A little post to expand on that "difference" and to justify the claim that indeed this difference "doesn't matter".

Indeed, "Introduction to Database Systems" speaks of "the triple <Ai,Ti,vi> being a component of [some tuple]".  We can recognize the Ai and vi parts, that's the attribute name part and the value part, respectively, and the "additional" Ti part is the name of the corresponding domain for Ai.

Thus, the "difference" is essentially one between

 +------------------+----------------------+--------------

I:INT X C:CHAR = {(I:INT:1,C:CHAR:'A') , (I:INT:1,C:CHAR:'B') , }

         +------------------+----------------------+------

and

 +------------------+-------------+--------------

I:INT X C:CHAR = {(I:1,C:'A') , (I:1,C:'B') , ... }

         +--------------+-------------+----------

Is that "difference" of great significance ?  Not really.  In both "alternatives", the LHS of the equation is a statement of the heading that the resulting tuples conform to.  In both alternatives, there is a "mechanical" way to compute the RHS, given the LHS (and given the precise definition of the domains that are used in that LHS, of course).  That "mechanical" way consists of :

• process all members of the "first" domain
• for each member of the domain, process all members of the "second" domain
• for each member of the second domain, process all members of the "third" domain
• ...
• for each member of the "next-to-last" domain, process all members of the "last" domain
• for each member of the last domain, spell out the tuple consisting of those "current" domain members.

It should be obvious that the only difference between the two is in the details of the "spell out" part.  The first approach includes "spell out the domain name", the second example doesn't.

The "mechanical way" just described is, in a sense, the way to go from the LHS of the equations to the RHS.  One could also, somewhat philosophically, contemplate things that could happen if one ever wanted to "go from the RHS of those equations to the LHS", so to speak.  "Derive the heading from an enumerated cartesian product", so to speak.  In that case, there seems to be a more important difference.  The second example simply doesn't allow us to do that ... at first sight.  Indeed, no domain names are mentioned in the RHS of the second example.  So how do we obtain them ?  Rather simply : generate them.  Name them "1", "2", "3", ...  Those names don't have to be meaningful when dealing with questions that were only philosophical to begin with !

Anyway, it should be clear that both approaches are able to "cover the same ground", and that therefore whatever difference might be perceived between them is indeed only perception, superficial, and is indeed a difference that doesn't matter.

"Relations of nothing at all"

In a previous installment, it was explained how relations, in the sense of the Relational Model of Data, are a generalization of the binary relations that are typically studied in mathematics.  Obviously, that "generalization" implies that such relations consist of "pairs" that have more than two values (drawn from the domains that were used to form the cartesian product), but the possibility was also alluded at to have "pairs" with only one value for its members, and even the possibility of such "pairs" with zero values for its members.

How does that make sense ?

First, let's revisit the "trick" that the Relational Model applied in "replacing" the concept of "ordinal" pairs with that of "unordered" pairs, "decomposing" that trick and its consequences step-by-step.

Start with the cartesian product of domains INT and CHAR :

 +-------------+---------+---------------+--------

INT X CHAR = {(1,'A') , (1,'B') , ... , (2,'A') , ...}

        +---------+---------+---------------+-----

What those lines seek to express is that we "know" that the numbers in those pairs derive from domain INT, precisely because they are the first ones in the pairs, and likewise for the quoted characters.

(Aside : computer languages that support 'tuples' natively typically use this 'ordered' version.  Haskell is a case in point.  There is a "first" operator to "retrieve" the "first" value from a tuple.  I digress.)

But for reasons of practicality, we do not want "addressability" (of the values within the tuples) by ordinal position (well at least not in settings where we are dealing with "large shared databases"), we want addressibility by attribute name.  The way to do this is by prepending attribute names to each and every thingy in that equation :

 +------------------+-------------+--------------

I:INT X C:CHAR = {(I:1,C:'A') , (I:1,C:'B') , ... }

         +--------------+-------------+----------

Aside : The equation as given states the equality between (some kind of) "predicative" way of defining a set (left side of the equation) and the "enumerative" way of defining a set (right side of the equation).  An "intensional" versus an "extensional" way of defining a type if you will.  But pls don't proliferate that latter terminology as it may be grotesquely off-base with more common usage of those terms.  Anyways.  Going in detail on that would be digressing from my main point here.  Maybe something for another installment.  End-of-aside.

Do we now still need those "pairs" (n-tuples) to be ordered ?  Well obviously, no we don't.  As long as we "know of the association" of I to domain INT and of C to domain CHAR, there is no longer any meaningful difference between (writing down that first tuple as)   (I:1,C:'A')   and (writing down that first tuple as)   (C:'A',I:1).


As a consequence, under this notation, we can also think of a (single) tuple as itself being a set, namely a set of these things that are separated by the comma's in each tuple of the enumeration.  And what exactly are those "things that are separated by comma's" ?  Eurhm, well, they are ordered pairs in which the first thing is an attribute name and the second thing is "some value drawn from some domain".

Another aside : "Introduction to Database Systems" says that a tuple is a set of ordered triplets.  The difference between the two approaches is not germane to the main point being made in this post (which is tuples and relations of nothing at all).  Suffice it to say here that the difference plays on ( / is a consequence of ) that presumption that was spelled out "As long as we "know of the association" of I to domain INT and of C to domain CHAR".  Maybe something for another installment.  End-of-another-aside.

Okay let's see what happens if we explicitly re-cast that tuple as a set of ordered pairs.
That gives us   { (I,1) , (C,'A') }.   Braces in bold for emphasis.
It should be clear that if we take a cartesian product of n domains, we get tuples that are themselves a set of cardinality n.  And since set theory is not limited to cardinalities >=2, this implies that, at least theoretically, we could also consider tuples of cardinality one and tuples of cardinality zero.

(Side remark on terminology : the number of attributes in a tuple is more commonly referred to as its degree.  I use the term "cardinality" here because that term is more closely related to set theory, and I am stressing the concept of tuples-as-sets here.  It should be clear that my "cardinality" of a tuple and the literature's more common "degree" of a tuple are the very same thing.)

We'll look briefly at tuples of cardinality one, because there is little unintuitive about them, and they will show us how tuples (and relations) of nothing at all, indeed make sense, and how they even are useful.  A tuple of cardinality one could be something like   TUPLE{ (I,1) }.   They are useful whenever the information that we want to store or retrieve, is the logical counterpart of a unary predicate, i.e. a predicate in which there is exactly one "fill-in-the-gaps" place.  For example, "The average temperature tomorrow will be §I§ degrees centigrade.".  Or "the highest customer number assigned is currently §I§".  Or "A §make of car§ has passed through our street today.".  (This latter one merely to illustrate that one must beware of confusing unary predicates with "predicates of which only one single instantiation can be true.  The talk is of unary predicates.)

Okay.  One step further down the line of decreasing tuple cardinalities (and we're finally where the title suggested we'd end up).  A tuple of cardinality zero, is, then, "a set of attribute values that has zero members".  Iow, it is the empty set of attribute values.  Iow, it is the empty set.   TUPLE{ }, in our usual notation.

How many such tuples are there ?  That's pretty obvious : exactly as many as there are "empty sets" in mathematics ... exactly one, thus.  Because the zero-tuple is unique, we can give it a name.  TUPLE_DEE in what follows.  Now where can TUPLE_DEE be useful in data management ?  That should by now be obvious too : it will be useful in any place where the information we want to store or retrieve, is logically defined by a nilary predicate.  I.e. whenever we deal with information, the defining predicate of which has no fill-in-the-gaps spots at all.  These predicates are sometimes labeled "degenerate predicates", and actually they correspond to propositions.  The following examples are drawn from "Databases, Types and the Relational Model", appendix E : "The door is open", or "The alarm is set".  No §§ marks, no fill-in-the-gaps.

Suppose you'd have to design a database to record the current state of affairs for those two predicates.  In SQL.  Would you create a "type" that can represent open/closed ?  One that can represent set/not set ?  What would you be doing to prevent your tables from containing two distinct rows, one saying that the door is "open" and the other row saying that the door is "closed" ?  Or would you design a boolean attribute "true" for open and "false" for closed ?  Yet again, how would you interpret such a table if it is empty ?  How would you enforce the rule that there must always be exactly one row in your table ?  All of that involves much more complication than is needed or warranted.

All you really need for such a database, is a relvar (/table) with no attributes (columns) at all.  If I want to record the information that "the door is closed", then I just ensure the table is empty.  How does this work ?  Well, any tuple in a relvar represents a true instantiation of the relvar's predicate.  If that predicate is a niladic, "degenerate" one, then the only instantiation possible is, the predicate itself (which already is a proposition by and of itself).  If there are no tuples at all in such a relvar, then this means that there are no true instantiations (/no true instances) of the relvar's proposition, meaning the relvar's proposition is FALSE.  If there is indeed a tuple in such a relvar, then that means that there does exist a true instantiation of the relvar's predicate, and since the only possible instantiation of that predicate is the predicate (proposition) itself, it means that the relvar's proposition is true.

Observe that there are thus two distinct possible values that such a "niladic" relvar can take on : one possible value in which no tuple is present at all (that's just the empty relation), and a value in which the empty tuple is present.  The difference between these two is a bit akin to the difference (in mathematics) between   {} and {{}}.  These values (relation values) are often assigned a name too, most often "TABLE_DUM" and "TABLE_DEE", other times more briefly "DUM" and "DEE".

I coloured the "outer" braces red to illustrate that these are the braces "associated with" a relvar and its corresponding predicate (proposition in our niladic case) and the "inner" ones green to illustrate that these correspond to a tuple that makes an instantiation of a predicate (proposition in our niladic case) true.

When querying a database, it is often claimed that DUM and DEE represent "false and true, respectively", or "no and yes, respectively".  That is a little bit sloppy.  Here's why :

If a database relvar's predicate is "The door is open", and we query that relvar, then we get back either DUM or DEE.  If it is DEE, then TUPLE_DEE appears in it, but the 'meaning' that TUPLE_DEE carries in this case is "The door is open".  It is only because of human interpretation that we "know" that this means a "yes" answer to the question "is the door open".  If we ask a question "is at least one student enrolled on any course", then we could inquire an ENROLMENT relvar and project away all of its attributes.  Once again, the result we get is either DUM or DEE.  If it is DEE, then TUPLE_DEE within it carries the meaning of the projection, which is "there exists some student and there exists some course such that that student is enrolled on that course".  It is only because of human interpretation that we know we can answer the question asked with a firm "yes" ...