ON RECURSION AND NULLS

From: MM

To: Editor

MIME-version: 1.0

MIME-version: 1.0

How can you represent recursion the relational model without NULLs -- assume you have a recursive relationship such as emp's manager is emp, or something like that.

MIME-version: 1.0

This is my understanding:

Consider a type such as emp, it has attributes such as (name, address, emp?) -- where the optional emp means it is a manager that is optional. This is perfect representation of the recursion I am talking about and you need no NULLs to represent it if you can represent it so, but what did we do here, we have a union type (name, address | name, address, emp). However, let us try to represent it in relational -- we cannot represent union types so we say it is (name, address, emp) and then to end the recursion we need NULL.

In short, I summarize it as follows: there are three possible values for attribute of a type -- it can have a non-NULL value, it can have a value which is unknown, or the attribute is not defined for that particular object. If you use union types, you can distinguish between these three, whereas in relational, you represent the last two using NULLs.

Chris Date Responds: Your original question to me was ''Can we represent a recursive list relationally?” The problem with that question, of course, is that the term recursive list is not precisely defined; I originally took it to mean something much more complicated (and more general) than what it now turns out you intended it to mean!

So first let me respond to your specific question. Surely the obvious design is:

EMP {NAME,ADDR} KEY {NAME}

Predicate : Employee NAME has address ADDR.

EM {NAME,MGR} KEY {NAME}

Predicate: Employee NAME has manager MGR.

If some employee has no manager, that employee will be represented in relvar EMP and not in relvar EM.

Now, you say ''we cannot represent union types (in the relational model) and then to end the recursion we need NULLs. These remarks are wrong on several counts. The most important is: Who says we cannot represent union types? I tried to explain in my presentation in Hong Kong that the relational model says essentially nothing about the nature of the underlying types--it just says you have to have some (Actually it says you have to have (a) type BOOLEAN and (b) a RELATION type generator. Period.) And one of the things Hugh Darwen and I tried to do in our book FOUNDATION FOR FUTURE DATABASE SYSTEMS: THE THIRD MANIFESTO was develop a theory of types, complementing but orthogonal to relational theory as such. And yes, our theory of types most certainly does allow you to have union types, and to define attributes of relation variables (relvars) over such types.

That said, I don't think we need union types in the employee/manager problem (and I certainly don't think we need NULLs for that problem either--nor for any other problem, I might add). I do think union types are needed for the more general problem of representing ''recursive lists'' relationally, however (interpreting the term recursive list to mean a list where the elements of the list can be either atoms or further lists); but I see that as a type issue, not as a relational issue, because (as I've already explained) types and relations are orthogonal.

Editor Note: Chapters 7 and 10 in PRACTICAL ISSUES IN DATABASE MANAGEMENT cover trees and recursion, why NULLs are never the correct solution for anything, and what the correct solution for missing data is.

Posted 10/25/02

[ABOUT] [QUOTES] [LINKS]