Re: Objects and Relations

From: Marshall <>
Date: 31 Jan 2007 23:30:50 -0800
Message-ID: <>

On Jan 31, 7:24 am, Bob Badour <> wrote:
> Marshall wrote:
> >
> > As a logical model nested relations have a long history of
> > study, and they do solve some problems. My personal model
> > includes nested relations.

> NF^2 nested relations? Or relation-valued attributes?

Whoops! I guess I don't know the precise difference. The phrase "relation-valued attributes" seems to describe exactly what I have in mind, but maybe there are nuances I'm not aware of.

> > Yes however I consider this a non-issue. The advantage of
> > recursive structures is that one can deal with each level
> > at a time, and not have to address them all at once.
> And I would expect a String type to permit multiple possible
> representations. If one can represent a String as an array, one already
> represents them as a relation given the operations to convert back and
> forth. So why not have a relation-valued representation?
> /amplification

Yes, absolutely!

> > I don't believe I have made any claims as to where the anus of
> > proof lies.
> Intentional? ;> LOL


> > Some of what we're discussing are design questions and
> > they are not subject to proof. (In fact, surprisingly little *is*
> > subject to proof.)
> Indeed. The more we make subject to proof, the better, however.

Agreed! And even in the absence of proof, the more we make subject to theory, the better.

> Or cross-product which I hope everyone will agree is a meaningul and
> useful operation too.


> > Again, I note that you're not accounting for the size() and prefix()
> > methods; you have to include them in the total count.
> I tend to disagree with that. You do not account for the physical
> implementation of join or min.

What we decide to count and what we decide not to count is a tricky choice. My justification for the above is an approximate sense of what would be a primitive in the abstract language, (or the core language) and what functions are so tiny as to be inlined 100% of the time, often at the single-instruction level. Thus, I don't count + or <. In a relational language I wouldn't count join because it's a relational primitive. Even if it might be computationally expensive, it's a single node in the abstract syntax tree. Min() is trickier; it might be a primitive in one relational system and a library function in another. But I lean away from counting it, because it's essentially just aggregation and <, each of which is primitive in a relational language individually.

I claim no distinguished validity to my choices; they are arbitrary. However they are not offhand nor capricious!

> [...]
> > I don't think it is the integrity constraint that matters so much as
> > that there is a total order on int, the type of index. Furthermore
> > the system understands the relationship between the comparators
> > (<, >=, etc.) and this order, and it understands the relationship
> > between < and min(). Knowing this it can know that it doesn't
> > have to examine any values for index that are <= fromIndex,
> > and it knows once it has found a single matching value, it doesn't
> > need to examine any values larger than that. Couple this with
> > the fact that if the system is using a naive array implementation
> > of the string, it will also know that the index values are laid
> > out *in order* in memory. (The fact that these values aren't
> > reified is irrelevant; they are still ordered. We can consider
> > the (index, char) tuple as being sequential, with the index
> > taking up 0 bytes and the char sizeof(char) bytes.) Oh, and
> > that the optimizer will know how to take advantage of joining
> > on an attribute that is in order in memory. IIUC these are all
> > things that optimizers are capable of doing in today's products.
> Indeed. Considering the physical representation might omit any
> representation of the index other than in the relative physical position
> of the characters, the compiler would absolutely have to understand the
> relationship between index and physical location.


> The Dragon Book mentions how algorithmic replacement can achieve far
> greater optimizations than the sum of all the optimizations it describes
> and notes that nobody has yet figured out how to do algorithmic
> replacement. Declarative languages expressing needs at a higher level
> change algorithmic replacement into a matter of algorithmic choice,
> which is far far easier to automate.
> /amplification

Marshall Received on Thu Feb 01 2007 - 08:30:50 CET

Original text of this message