Re: Bidirectional Binary Self-Joins

On Mar 30, 9:55 am, "David Cressey" <cresse..._at_verizon.net> wrote:
> [...]
> So the old bugaboo about sets versus lists surfaces once again.
>
> Marshall's description, in terms of RVA's obscures the difference between a
> set and a list, because when you lay it out in text, a set looks like a
> list.

Well, uh, I guess. I expect we can certainly agree that sets and lists are different things and that syntax should reflect this. However
if the syntax is unambiguous, (which it darn well better be) and there is still confusion, we have to put that at the feet of the reader.

Note that syntax is fundamentally ordered. Any sentence in any language is a finite sequence of symbols, and by "sequence" I mean exactly "list." (The two terms refer to the same thing, mathematically.) Therefore any syntax we have for sets must necessarily have some order to the symbols, and we explicitly distinguish when certain sequences of tokens have meaningful order and when they don't.

> Marshall, for your RVA solution, how would the query language
> handle the question, "Find all the games that Hope played"?

(To be answered later, (if at all :-))

> Also, let's say you already had the game you stated in the database, and
> you tried to insert the following game:
>
> { date=12-Dec, teamscores={(team=Calvin, score=32), (team=Hope,
> score=59)}}
>
> Would the database engine detect that the game was already in the relation?
> If so, how would it do that? I realize my question is a physical one, not a
> logical one, but I'm asking anyway.

I don't think the situation is any different when we have RVAs than when we don't. Whatever the key is, if we have an index on that key, then we look up the projection of the insert set onto the key columns in the index and if we find any overlap then we abort. If we don't have an index, then we may have to sort both source and destination and merge the results, at a cost of, what O(n logn + m logm), where n, m are the sizes of the relvar and the insert set.

Marshall Received on Sat Mar 31 2007 - 07:16:55 CEST