Navigation vs Relational operators
x
In what way is "navigation" different from using relational operators ?
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
*** Usenet.com - The #1 Usenet Newsgroup Service on The Planet! ***
http://www.usenet.com
Unlimited Download - 19 Seperate Servers - 90,000 groups - Uncensored
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Paul G. Brown
> **** Post for FREE via your newsreader at post.usenet.com ****
>
> In what way is "navigation" different from using relational operators ?
How do you 'navigate' union / projection / restriction / intersection /
outer-join / anti-join / difference / division?
Only equi-join along a join dependency has the 'flavor' of navigation.
The obvious difference is that all relational operators have a precise
definition. "Navigation" (as its quotation marks implies) don't.
Alfredo Novoa
Brown) wrote:
> How do you 'navigate' union / projection / restriction / intersection /
> outer-join / anti-join / difference / division?
What anti-join is?
Paul G. Brown
Given two relations, R < a, b, c > and Q < a, d, e >, the anti-join
R [Aj] Q is all tuples from R where there does not exist a corresponding
tuple in Q meeting some join criteria.
It's equivalent to SQL's
SELECT *
FROM R
WHERE NOT EXISTS ( SELECT 1
FROM Q
WHERE R.a = Q.a );
for example.
It's often useful, in query planning, to 'flatten' the sub-query, because
there are a raft of other re-writes that you can do with an anti-join
and other join forms (and many you can't). You can think of it
in terms of a join and a difference if you like, but there are really
efficient physical operators for the anti-join
Alfredo Novoa
> > What anti-join is?
>
> Given two relations, R < a, b, c > and Q < a, d, e >, the anti-join
> R [Aj] Q is all tuples from R where there does not exist a corresponding
> tuple in Q meeting some join criteria.
Thanks
Dawn M. Wolthuis
news:c88knd$mc9$1...@ngspool-d02.news.aol.com...
> > In what way is "navigation" different from using relational operators ?
>
>
> 1. Record-at-a-time traversal through an ISAM database. You make calls to
a
> database library to get the next or previous record (using sequential or
indexed
> access).
> 2. In a network model database, you navigate through pre-defined sets by
making
> calls to get the next or prior member of the set, or the owner. It's
> conceptually similar to a doubly-linked list.
> 3. Relational is non-navigational. You don't need to know how to navigate
to the
> data that matches your search criteria.
>
> If you tell a taxi driver "Take Hwy 163 north to Interstate 8. Turn west
on
> Interstate 8 until you come to Interstate 5. Turn North on Interstate 5
until
> the split at Interstate 405. Take I-405 North until you get to the West
Century
> Blvd. exit. Turn west and take West Century Blvd. to Los Angeles Airport".
> That's navigation.
>
> On the other hand, if you say "Take me to Los Angeles Airport", that's
SQL. You
> rely on the driver to know the best route.
I dunno about that -- it seems to me that if you say "Take me to LAX" and
you take me down all of these streets until we get there -- that is
navigation. I didn't need to know how to get there, but someone did.
If you say "Take me to LAX" and you don't navigate there, but rather use
some set operations to beem me up to LAX, then that is relational -- no
visible navigation because no navigational operators were employed by anyone
including the taxi driver.
Or am I missing the point? --dawn
Gene Wirchenko
[snip]
>I dunno about that -- it seems to me that if you say "Take me to LAX" and
>you take me down all of these streets until we get there -- that is
>navigation. I didn't need to know how to get there, but someone did.
>
>If you say "Take me to LAX" and you don't navigate there, but rather use
>some set operations to beem me up to LAX, then that is relational -- no
>visible navigation because no navigational operators were employed by anyone
>including the taxi driver.
>
>Or am I missing the point? --dawn
I think so. In the second case, the transporter operator would
know what to do. In the first case, the taxi driver is analogous to
the DBMS. In the second case, the transporter operator is analagous
to the DBMS. In both cases, we do not need to know how they do what
they do; we just specify the desired result.
The navigation (or whatever the execution is called) is hidden
from us.
Sincerely,
Gene Wirchenko
Computerese Irregular Verb Conjugation:
I have preferences.
You have biases.
He/She has prejudices.
x
"Gene Wirchenko" <ge...@mail.ocis.net> wrote in message
news:99bga0l4713o8g0r5...@4ax.com...
> "Dawn M. Wolthuis" <dw...@tincat-group.com> wrote:
>
> [snip]
>
> >I dunno about that -- it seems to me that if you say "Take me to LAX" and
> >you take me down all of these streets until we get there -- that is
> >navigation. I didn't need to know how to get there, but someone did.
> >
> >If you say "Take me to LAX" and you don't navigate there, but rather use
> >some set operations to beem me up to LAX, then that is relational -- no
> >visible navigation because no navigational operators were employed by
anyone
> >including the taxi driver.
> >
> >Or am I missing the point? --dawn
>
> I think so. In the second case, the transporter operator would
> know what to do. In the first case, the taxi driver is analogous to
> the DBMS. In the second case, the transporter operator is analagous
> to the DBMS. In both cases, we do not need to know how they do what
> they do; we just specify the desired result.
>
> The navigation (or whatever the execution is called) is hidden
> from us.
Well, we don't need to tell the driver how to drive.
But we may need to tell him (some of) the route ...
Laconic2
You know where you want to go, but you may not know the best way to there.
The cabbie knows the best way to navigate to a variety of destinations, but
doesn't (initially) know where you want to go.
When you say "Take me to LAX", you are delegating the navigation to someone
who does that.
Now if you had some kind of SQL like interface on top of an engine that knew
how to navigate through ISAM files, you would have the "what not how", to
the extent that SQL succeeds at separating what from how. That's another
discussion.
Mike Nicewarner
The idea of suggesting a route to the taxi driver is like suggesting index
usage to some DBMS. Sometimes we force a specific order of operation by
placement of subqueries. In any event, the DBMS/taxi driver makes the final
decision about how to get the data.
And remember that in many situations, the data is no where near where you
think it is. Think "bufferpools" or other caching ideas. In other words,
"LAX" isn't always at the same location, so for you to force the taxi driver
to take a specific route might be the worst idea possible.
--
Mike Nicewarner [TeamSybase]
http://www.datamodel.org
mike@nospam!datamodel.org
Sybase product enhancement requests:
http://www.isug.com/cgi-bin/ISUG2/submit_enhancement
"x" <x-f...@yahoo.com> wrote in message news:40a8...@post.usenet.com...
x
"Mike Nicewarner" <psyclo@nospam_datamodel.org> wrote in message
news:c8acu6$9ft$1...@news.netins.net...
> Interesting discussion.
> The idea of suggesting a route to the taxi driver is like suggesting index
> usage to some DBMS. Sometimes we force a specific order of operation by
> placement of subqueries. In any event, the DBMS/taxi driver makes the
final
> decision about how to get the data.
> And remember that in many situations, the data is no where near where you
> think it is. Think "bufferpools" or other caching ideas. In other words,
> "LAX" isn't always at the same location, so for you to force the taxi
driver
> to take a specific route might be the worst idea possible.
Well, the taxi driver know the names of the places and streets (our own
names, not city hall names).
When we tell him the "route", we use these names.
What I have in mind , it is more like specifying attributes and join
conditions.
x
"Ken North" <kno...@deletethis.yahoo.com> wrote in message
news:c88knd$mc9$1...@ngspool-d02.news.aol.com...
> > In what way is "navigation" different from using relational operators ?
> 3. Relational is non-navigational. You don't need to know how to navigate
to the
> data that matches your search criteria.
>
> If you tell a taxi driver "Take Hwy 163 north to Interstate 8. Turn west
on
> Interstate 8 until you come to Interstate 5. Turn North on Interstate 5
until
> the split at Interstate 405. Take I-405 North until you get to the West
Century
> Blvd. exit. Turn west and take West Century Blvd. to Los Angeles Airport".
> That's navigation.
>
> On the other hand, if you say "Take me to Los Angeles Airport", that's
SQL. You
> rely on the driver to know the best route.
I think Relational is more like using a subway or railway system rather than
a taxi.
Laconic2
"hints". I've run into a few people who think that the really cool Oracle
people use "hints" all the time.
What those people tend not to realize is that the overuse of hints is a
symptom of a defect: bad query design, bad index design, bad table design,
and/or a defect in the optimizer.
People who use hints all the time remind me of people who use a programming
language, but are little hazy on the syntax and semantics of the language
itself. But they are real whizzes with the interactive debugger! I went
through a phase like that myself, when I was young.
D Guntermann
>
>
> "Mike Nicewarner" <psyclo@nospam_datamodel.org> wrote in message
> news:c8acu6$9ft$1...@news.netins.net...
> > Interesting discussion.
> > The idea of suggesting a route to the taxi driver is like suggesting
index
> > usage to some DBMS. Sometimes we force a specific order of operation by
> > placement of subqueries. In any event, the DBMS/taxi driver makes the
> final
> > decision about how to get the data.
> > And remember that in many situations, the data is no where near where
you
> > think it is. Think "bufferpools" or other caching ideas. In other
words,
> > "LAX" isn't always at the same location, so for you to force the taxi
> driver
> > to take a specific route might be the worst idea possible.
>
> Well, the taxi driver know the names of the places and streets (our own
> names, not city hall names).
> When we tell him the "route", we use these names.
> What I have in mind , it is more like specifying attributes and join
> conditions.
>
Relational is still navigational, but logically. The relational model frees
us from physical navigation and somewhat from logical navigation. To
further provide users the capacity to have even greater freedom from logical
navigation (e.g. specifying an attribute independent of knowledge and
application of table names, relationships, and joins), Ullman and others
(Fagin,Maier and Valdi) proposed and explored the concept of the Universal
Relation. There was quite an interesting and uncharacteristically blunt
public debate between proponents of the universal relaton assumption and
William Kent.
Refererences:
Fagin, R., Mendelzon, A., & Ullman J.. (September, 1982). A simplified
universal relation assumption and its properties. ACM Transactions on
Database Systems (TODS) 7: (3).
Kent, W. (December, 1981). Consequences of assuming a universal relation.
ACM Transactions on Databases (TODS), 6:(4).
Ullman, J. (December, 1983). On Kent's 'Consequences of assuming a
universal relation'. ACM Transactions on Databases (TODS), 8:(4).
And others that can be found in references and citings of the listed
references.
- Dan
Karel Miklav
> I think Relational is more like using a subway or railway system rather than
> a taxi.
No way. Relational engine must navigate through it's structures like
hell to find the data, it's just that the end user doesn't have to know
everything about it. And there lies a problem: you may be an owner of a
shitty RDB implementation.
There are good uses for relational databases and other technologies as
well. And this is a technical issue, I don't see the point in using
parables.
Regards,
Karel Miklav
Karel Miklav
> Well, I want to use taxies but I am unable to find one :-)
It's probably what we're all doing here :)
--CELKO--
operators? <<
Relational operators work on a set level. They can be applied in
parallel to each element of the set all at once or in a
non-determinisitic order. Navigational operations require an order of
execution.
Example: In the nested set model of a tree, given one node, you can
determine its superiors with a single predicate that can be applied to
all the nodes at once to put them into the subset. Using a simple
organizational chart:
SELECT O2.*
FROM OrgChart AS O1, OrgChart AS O2
WHERE O1.lft BETWEEN O2.lft AND O2.rgt
AND O1.emp = :myemployee;
In an adjacency list model, I have to start at the node and work my
way up the tree to the root node. I cannot take a random node and
apply a characteristic function to it.
Tony
> But we may need to tell him (some of) the route ...
Not necessarily. London taxi drivers, for example, are expected to
know their way around London. If you got into a taxi at Trafalgar
Square and said "take me to Heathrow Airport", you would *not* expect
the driver to ask you for directions! Think of the database as the
taxi driver's "patch" and the DBMS as the taxi driver; SQL is the
instruction you give the taxi driver. There is no need to specify
navigation details, because the driver (DBMS) knows his "patch" (the
database) well.
Jan Hidders
>
> Relational is still navigational, but logically. The relational model frees
> us from physical navigation and somewhat from logical navigation. To
> further provide users the capacity to have even greater freedom from logical
> navigation (e.g. specifying an attribute independent of knowledge and
> application of table names, relationships, and joins), Ullman and others
> (Fagin,Maier and Valdi) proposed and explored the concept of the Universal
> Relation. There was quite an interesting and uncharacteristically blunt
> public debate between proponents of the universal relaton assumption and
> William Kent.
>
> Refererences:
> Fagin, R., Mendelzon, A., & Ullman J.. (September, 1982). A simplified
> universal relation assumption and its properties. ACM Transactions on
> Database Systems (TODS) 7: (3).
>
> Kent, W. (December, 1981). Consequences of assuming a universal relation.
> ACM Transactions on Databases (TODS), 6:(4).
>
> Ullman, J. (December, 1983). On Kent's 'Consequences of assuming a
> universal relation'. ACM Transactions on Databases (TODS), 8:(4).
Probably nobody's interested in this anymore, but I just found a nice
short and accessible on-line presentation of the issues and positions:
http://www-db.stanford.edu/jdu-symposium/talks/mendelzon.pdf
Nice stuff, especially if you know a little the persons involved. If
only there were heated debates over *this* subject in this newsgroup... :-)
-- Jan Hidders
Paul Vernon
news:n11Fc.171714$4P6.8...@phobos.telenet-ops.be...
> D Guntermann wrote:
> >
> > Relational is still navigational, but logically. The relational model
frees
> > us from physical navigation and somewhat from logical navigation. To
> > further provide users the capacity to have even greater freedom from
logical
> > navigation (e.g. specifying an attribute independent of knowledge and
> > application of table names, relationships, and joins), Ullman and others
> > (Fagin,Maier and Valdi) proposed and explored the concept of the
Universal
> > Relation. There was quite an interesting and uncharacteristically blunt
> > public debate between proponents of the universal relaton assumption and
> > William Kent.
> >
> > Refererences:
>
> Probably nobody's interested in this anymore, but I just found a nice
> short and accessible on-line presentation of the issues and positions:
>
> http://www-db.stanford.edu/jdu-symposium/talks/mendelzon.pdf
>
> Nice stuff, especially if you know a little the persons involved. If
> only there were heated debates over *this* subject in this newsgroup...
:-)
>
> -- Jan Hidders
Well, I'm interested for one. Thanks for the link Jan.
One way this is of interest is to throw some theoretical light on the way
that some query tools (I'm thinking Cognos, Business Objects - that kind of
thing), attempt logical data independence. Here end users do not generally
specify joins, rather some designer does.
Quote from http://citeseer.ist.psu.edu/vardi88universalrelation.html
"In a universal-relational system, you must settle for eliminating the
need for logical navigation along certain paths - those selected by the
designer - while letting the user navigate explicitly in more convoluted
ways"
The tools I mentioned above fail (in my opinion) on at least that last
matter. They do not provide an easy fall back position for more convoluted
queries.
Personally, (I think) I much prefer tools that make logical navigation
visible to the users, so that you don't get a discontinuity between 'simple'
queries that can be done without logical navigation, and those that require
it. In other words, I'm probably with Codd :- "the universal-relation model
fails completely as an alternative to the relational model."
P.S. the gzip'ed pdf from off the link above is actually a plain pdf, so
just rename the extension to view the article.
Regards
Paul Vernon
Business Intelligence, IBM Global Services
x
"Jan Hidders" <jan.h...@REMOVETHIS.pandora.be> wrote in message
news:n11Fc.171714$4P6.8...@phobos.telenet-ops.be...
> Probably nobody's interested in this anymore, but I just found a nice
> short and accessible on-line presentation of the issues and positions:
> http://www-db.stanford.edu/jdu-symposium/talks/mendelzon.pdf
> Nice stuff, especially if you know a little the persons involved. If
> only there were heated debates over *this* subject in this newsgroup...
:-)
I found the presetation the same day D Guntermann provided the references,
but I was unable to find the answer to the question "Who won the Universal
Relation wars?" (Which ones are The Good Guys ?)
Maybe this war has not ended yet.
Paul Vernon
[snip]
> > Probably nobody's interested in this anymore, but I just found a nice
> > short and accessible on-line presentation of the issues and positions:
>
> > http://www-db.stanford.edu/jdu-symposium/talks/mendelzon.pdf
>
> > Nice stuff, especially if you know a little the persons involved. If
> > only there were heated debates over *this* subject in this newsgroup...
> :-)
>
> I found the presetation the same day D Guntermann provided the references,
> but I was unable to find the answer to the question "Who won the Universal
> Relation wars?" (Which ones are The Good Guys ?)
The clue is in the Star Wars picture.
http://www.progesis.net/images/codd.jpg
See the resemblance?
Mikito Harakiri
"Paul Vernon" <paul....@ukk.ibmm.comm> wrote in message
news:cc3smh$1iua$1...@gazette.almaden.ibm.com...
> The clue is in the Star Wars picture.
>
> http://www.progesis.net/images/codd.jpg
>
> See the resemblance?
I was going to ask who are the 2 other folks, as one is unmistakenly
http://www-db.stanford.edu/~ullman/
Jan Hidders
>
> Personally, (I think) I much prefer tools that make logical navigation
> visible to the users, so that you don't get a discontinuity between 'simple'
> queries that can be done without logical navigation, and those that require
> it. In other words, I'm probably with Codd :- "the universal-relation model
> fails completely as an alternative to the relational model."
Well, Moshe Vardi never claimed it was. Could be that Jeff Ullman did,
though. At a few occasions I've heard him make a remark about it that
gave the impression to me that he was still a little bit sore over this.
I don't really have a strong opinion either way. I'm sure that in some
limited cases the UR approach works splendidly (simple schema, simple
SPJ questions) but in other cases it will make things actually more
difficult than necessary.
Apologies for being so non-argumentative. :-)
-- Jan Hidders
Jan Hidders
>
> I found the presetation the same day D Guntermann provided the references,
> but I was unable to find the answer to the question "Who won the Universal
> Relation wars?" (Which ones are The Good Guys ?)
Well, it's probably most correct to say that Ted Codd won, but since the
talk was given at the Jeffrey D. Ullman symposium...
-- Jan Hidders