Re: Bidirectional Binary Self-Joins

"Marshall" <marshall.spight_at_gmail.com> wrote in message news:1175318215.358053.322710_at_p77g2000hsh.googlegroups.com...
> 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.

Fair enough. And I guess the braces in your syntax enclose a set and not a list. My bad.

>
> 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.

I think "any language" in the above applies to data structures in a computer as well as text languages. Sigh.

>
>
> > 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.
>

Fair enough. Just so we are all aware of the cost. Received on Sun Apr 01 2007 - 07:19:51 CEST