Re: Perhaps an idiotic question

On 2006-11-30, Bob Badour wrote:

> Second, to have this exactly as stated yields a potentially infinite
> progression of the type. In practical terms, one would have to settle
> for a finite recursion because computers are finite machines. ie. If
> one serially ungroups the A attribute, at some finite step, ungrouping
> would yield an empty relation with cardinality zero.

That's what necessarily happens with the relation instances, but the corresponding types need not be finite. In type theory, constructs like these are discussed under the heading of equirecursive types.

One simple way of looking at such types comes from object oriented type systems. An object valued variable in an object is often interpreted as a reference, but it could also be viewed as a directly included substructure. The distinction need not matter. If the variable happens to be of the same type as the containing object, you have precisely the situation you described; this happens e.g. with singly linked lists in Java. In practice such inclusion is still implemented by making the variable a reference/pointer under the covers. The relational model isn't too happy about this sort of thing, but then all of the approaches you'd use to map a pointer based data model into relations can be used. After you do that, the general case simply leads to cyclic schemas, nothing else.

For example, in your case you could implement the recursive reference to T as a bridge relation S with two foreign keys to R, one in the role of parent tuple id and the other in the role of the id of an associated tuple referred to by the parent. Obviously the relation is many-to-many because each parent contains an entire relation, not just a single tuple. Doing it this way allows you to store all tuples in all of the relations of type T in a single flat relation R, and do so precisely once. This is suitable when R describes entities, because it makes integrity easier to enforce.

In other situations you might want to frame R with a partition number and implement the child relation reference by referring to that, or you might even go as far as to make all relations of type T separate and refer to them by name. It all depends on what you're after, and the choices demonstrate how recursive types can become productive e.g. with respect to integrity constraints.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2