jay@umd5.umd.edu (Jay Elvove) (05/31/90)
A friend of mine put this question to me:
Given a two-column table, where column one is a primary key
designating an employee and column two designates his boss, and
columns one and two are identical when an employee is his/her own
boss; using SQL, how would one go about displaying the chain of
command of each employee in the table? Assume each employee can
only have one boss. A simple example follows:
Given F, the chain A
of command is D B A / \
B C
/ \
D E
/ \
F G
I don't know the answer.
--
Jay Elvove jay@umd5.umd.edu
c/o Academic Software
Comp. Sci. Center, Univ. of Md., College Parkdavidm@uunet.UU.NET (David S. Masterson) (06/01/90)
In article <6588@umd5.umd.edu> jay@umd5.umd.edu (Jay Elvove) writes:
Given a two-column table, where column one is a primary key
designating an employee and column two designates his boss, and
columns one and two are identical when an employee is his/her own
boss; using SQL, how would one go about displaying the chain of
command of each employee in the table? Assume each employee can
only have one boss.
Unless you assume a maximum length of the chain of command, then it can't be
done. This is one of the shortcomings of relational languages (like SQL) that
I've seen so far. It comes under the title of the "parts explosion" (I think
that's the example most people use) which given a part constructed from
subparts, then show what parts will be affected downline by a change in a
subpart.
If you make an assumption about the maximum length (say N), then you can outer
join the table with itself N-1 times to produce the answer. BTW, this outer
join would not care whether an employee had one or more than one bosses.
--
===================================================================
David Masterson Consilium, Inc.
uunet!cimshop!davidm Mt. View, CA 94043
===================================================================
"If someone thinks they know what I said, then I didn't say it!"jkrueger@dgis.dtic.dla.mil (Jon) (06/01/90)
jay@umd5.umd.edu (Jay Elvove) writes (paraphrased): > consider a table > > +-----+ > | emp | emp mgr > +-----+------+------+ > | F | D | > | G | D | > | D | B | > | B | A | > | E | C | > | C | A | > +------+------+ > > representing the hierarchy > > A > / \ > B C > / \ > D E > / \ > F G > > it may be assumed that each employee has exactly one manager; > how to write a SQL query that finds the chain of command for > an employee, e.g. given F, the chain of command is D B A SQL (and other query languages for RDBMS) can't express recursive queries. So the simple answer is it can't be done. The longer answer is (1) it can't be done in a single query, (2) nor any finite number of queries, (3) nor any reasonable number of queries, where "reasonable" is defined as spending more time executing queries than dispatching them, (4) nor without writing a program in some general purpose programming language (see below). -- Jon #include <stdio.h> char *malloc(); main(argc, argv) int argc; char *argv[]; { setup(); if (argc > 1) gen_chain(argv[1]); else fprintf(stderr, "usage: %s employee\n", argv[0]); cleanup(); } #define SIZE 50 /* column width, longest emp name */ ##gen_chain(the_emp) ##char *the_emp; ##{ ## char the_mgr[SIZE]; ## int mcount; /* exec sql select count (mgr) into :mcount from emp where mgr = the_emp */ ## retrieve (mcount = count(emp.mgr where emp.emp = the_emp)) if (mcount == 0) { printf("%s is at the top\n", the_emp); } else { /* select mgr into :the_mgr from emp where mgr = the_emp */ ## retrieve (the_mgr = emp.mgr) where emp.emp = the_emp printf("%s is the manager of %s\n", the_mgr, the_emp); gen_chain(the_mgr); } ##} -- Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger Drop in next time you're in the tri-planet area!
tgreenla@oracle.uucp (Terry Greenlaw) (06/01/90)
In article <jkrueger.644204650@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: >jay@umd5.umd.edu (Jay Elvove) writes (paraphrased): > >> consider a table >> >> +-----+ >> | emp | emp mgr >> +-----+------+------+ >> | F | D | >> | G | D | >> | D | B | >> | B | A | >> | E | C | >> | C | A | >> +------+------+ >> >> representing the hierarchy >> >> A >> / \ >> B C >> / \ >> D E >> / \ >> F G >> >> it may be assumed that each employee has exactly one manager; >> how to write a SQL query that finds the chain of command for >> an employee, e.g. given F, the chain of command is D B A > >SQL (and other query languages for RDBMS) can't express recursive >queries. So the simple answer is it can't be done. The longer answer >is (1) it can't be done in a single query, (2) nor any finite number of >queries, (3) nor any reasonable number of queries, where "reasonable" >is defined as spending more time executing queries than dispatching >them, (4) nor without writing a program in some general purpose >programming language (see below). ... 3GL deleted ... >Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger >Drop in next time you're in the tri-planet area! Oracle has an extension to SQL which was designed for tree traversal like the problem shown above. Two clauses were added to the select statement; connect by and start with. In the example above, you would need to add a record for employee A (The Big Cheese) with a mgr set to null. Then to traverse the tree, you would use the statement select emp from emp start with mgr is null connect by prior emp = mgr; There also is a pseudocolumn called level that reflects the current traversal depth. It's handy for formatting your output to look like a tree. Hope this helps those of you with Oracle out there. Terry O. Greenlaw Sheathed within the Walkman, Staff Engineer Wear a halo of distortion. Oracle Corporation Aural contraceptive, tgreenla@oracle.oracle.com Aborting pregnant conversation - Marillion
jkrueger@dgis.dtic.dla.mil (Jon) (06/04/90)
tgreenla@oracle.uucp (Terry Greenlaw) writes: > Oracle has an extension to SQL which was designed for tree traversal Sounds great. Except for one small problem: the only reason I use SQL is compatibility and applications portability. Clearly at this point you can't have this and a cleanly designed query language too, but with SQL extensions you can have neither. -- Jon -- Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger Drop in next time you're in the tri-planet area!
segel@Tellabs.COM (Mike Segel) (06/04/90)
If I can use a 4gl like Informix, the solution would be :
input employee name;
select manager from table
where employee_name = emp; /* from Jon's cut */
Print "The chain of command for employee ", employee_name, "is \n";
While ( employee_name != manager) {
print manager , " - ";
employee_name = manager;
select manager from table
where employee_name = emp;
}
print manager , "\n";
-----------------------------------
Now the above program is in a pseudo code. Notice that there is no
recursion, just a while loop. If you really wanted to get dirty,
you could implement this in an Assembler language.
Now Oracle has an extension to SQL ?
Their solution is cute. depending on how they did it, I can think of
some drawbacks to it. Does it keep the querried items in a temp table?
Or on a stack? So now you have your sample querry done, how do you get
the data out.
If it is stored in a temp table, then the same solution can be done in
any 4gl. Does it really matter if the extension occurs to the SQL, or
if you are using a 4gl ?
I really question Oracle's solution. Where is the information stored?
If on a stack, then depending on the depth of the querry, and the size
of the information stored, then you could run into trouble. This type
of example is good reason for 4GLs. They allow for high language type
of control, merged in with std sql. My point is, you need to use
the right tool for the job.
Am I making sense or have I been working too long?
-Miketgreenla@oracle.uucp (Terry Greenlaw) (06/04/90)
In article <jkrueger.644437146@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: >tgreenla@oracle.uucp (Terry Greenlaw) writes: > >> Oracle has an extension to SQL which was designed for tree traversal > >Sounds great. Except for one small problem: the only reason I use >SQL is compatibility and applications portability. Then you must be one very frustrated individual, since SQL compatability between vendors falls into the "virgin nymphomaniac" class of events. I don't think SQL is mature enough at this point to freeze expansion of the language in the name of compatability. The extensions that Oracle and other vendors have provided are the driving forces that will lead to a language robust enough to be used in a unextended form. For now, the basic SQL syntax is a good starting point for understanding a relational query language, but I wouldn't be relying on it for portability across vendors. > Clearly at this >point you can't have this and a cleanly designed query language >too, but with SQL extensions you can have neither. > >Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger >Drop in next time you're in the tri-planet area! I think you will find that you can, but it's name will be SQL II. Terry O. Greenlaw Sheathed within the Walkman, Staff Engineer Wear a halo of distortion. Oracle Corporation Aural contraceptive, tgreenla@oracle.oracle.com Aborting pregnant conversation - Marillion
peter@brontolo.sublink.ORG (SINDATA Network administrator) (06/04/90)
In article <6588@umd5.umd.edu>, jay@umd5.umd.edu (Jay Elvove) writes: > A friend of mine put this question to me: > > Given a two-column table, where column one is a primary key > designating an employee and column two designates his boss, and > columns one and two are identical when an employee is his/her own > boss; using SQL, how would one go about displaying the chain of > command of each employee in the table? Assume each employee can > only have one boss. A simple example follows: > > > Given F, the chain A > of command is D B A / \ > B C > / \ > D E > / \ > F G > It is the very hard problem of the "recursive cursor" that Date told is not already resolved, because cursors are NOT recursive. An ugly answer may be the following (using Informix's ESQL/C) : Assume that the table is named "company" and that column names are "emp_name" and "boss_name". ....... void employee_search(); main() { ........ employee_search("Big Boss"); /* Assume A's name is "Big Boss" */ } /* Employee_search search for one layer of the employees tree */ void employee_searc(boss_tos) $string *boss_tos; /* Name of the boss to search */ ${ $ string emp_name[xx]; /* Employee name */ $ string boss_name[xx]; /* Boss name */ $ static string last_name[xx]; /* Last name found */ short end_fl=0; last_name[0]='\0'; /* Reset employee name search */ while(!end_fl) { /* Endless loop */ $ declare search_curs cursor for select emp_name,boss_name into $emp_name,$boss_name from company where boss_name = $boss_tos and emp_name > $last_name order by 2,1; $ open search_curs; for(;;) { $ fetch search_curs; if(sqlca.sqlcode == SQLNOTFOUND) { $ close search_curs; return; } /* Here we have the employee name to handle may be he or her is a boss */ /* Check if the employee is also a boss */ $ select boss_name from company where boss_name = $emp_name; if( sqlca.sqlcode == 0L ) { /* Yes, it is ! */ $ close search_curs; employee_search(emp_name); /* Search next layer*/ strcpy(last_name,emp_name);/* Go back to current*/ break; } } } } This is the answer to an "explosion" problem. It may be easily adapted to an "implosion" one, such as the one you stated. Peter -- Peter Komanns ************- SINDATA srl -***************** Via Rovereto 17 | BANG ..!rutgers!deejay!yachaya!brontolo!peter 20059 Vimercate MI ITALY | SUBLINK peter@brontolo (voice) +39-39-6083733 (fax) +39-39-6083957
benl@adt.SanDiego.NCR.COM (Ben.Lheureux) (06/05/90)
In article <1990Jun4.151555.3479@oracle.com> tgreenla@oracle.UUCP (Terry Greenlaw) writes: >In article <jkrueger.644437146@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: >> >>> Oracle has an extension to SQL which was designed for tree traversal >> >>Sounds great. Except for one small problem: the only reason I use >>SQL is compatibility and applications portability. > >Then you must be one very frustrated individual, since SQL compatability >between >vendors falls into the "virgin nymphomaniac" class of events. I don't think SQL >is mature enough at this point to freeze expansion of the language in the name >of compatability. Let's not forget that every vendor's ME-TOO desire to support SQL and the relational model provided -- for the first time -- a meaningful level of compatibility among divergent DMS's. Unfortunately because SQL is not SQL is not SQL, there is a strong desire to identify a commonly used subset of SQL features among vendors, so that the highly marketed compatibility supposedly provided by SQL can actually be realized by users. I.e. formation of SAG, Ingres Open SQL, etc. >The extensions that Oracle and other vendors have provided >are the driving forces that will lead to a language robust enough to be used >in a unextended form. A convenient position to take, since Oracle just happens to have one of the (perhaps THE) most robust SQL languages :-) Exceptions anyone? >For now, the basic SQL syntax is a good starting point >for understanding a relational query language, but I wouldn't be relying on it >for portability across vendors. I'm sure your disclaimer disqualifies you from speaking for all Oracle Marketing organizations, but perhaps you can reconcile this position with Oracle's HIGHLY-TOUTED SQL*Star concept, where Oracle applications, presumably carefully coded in THE WONDERFUL, COMPATIBLE SQL language may transparently run against Oracle, DB2, SQL/DS, or <name of your favorite version of SQL*Connect here>? Benoit.Lheureux@sandiego.NCR.COM #################################### Application Dev Tools, Dept 4775 # Opinions are my own, not NCR's # 16550 West Bernardo Drive # Farewell Micro C Magazine # San Diego, CA 92127 619/485-3578 ####################################
john@anasaz.UUCP (John Moore) (06/05/90)
In article <1990Jun4.151555.3479@oracle.com> tgreenla@oracle.UUCP (Terry Greenlaw) writes: ]In article <jkrueger.644437146@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: ]>Sounds great. Except for one small problem: the only reason I use ]>SQL is compatibility and applications portability. ] ]Then you must be one very frustrated individual, since SQL compatability between ]vendors falls into the "virgin nymphomaniac" class of events. I don't think SQL mmmmm... its not quite that bad! We've run the same stuff on Oracle and Informix, for example. ]is mature enough at this point to freeze expansion of the language in the name ]of compatability. The extensions that Oracle and other vendors have provided ]are the driving forces that will lead to a language robust enough to be used ]in a unextended form. For now, the basic SQL syntax is a good starting point ]for understanding a relational query language, but I wouldn't be relying on it ]for portability across vendors. ] ]> Clearly at this ]>point you can't have this and a cleanly designed query language ]>too, but with SQL extensions you can have neither. ]> ]>Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger ] ]I think you will find that you can, but it's name will be SQL II. Hopefully the RDBMS vendor community will realize that SQL is far from an ideal query language for many commercial systems, and will thus put in the extensions needed to both the language AND the model. If not, I predict that OODB's or network DB's w/OODB's will cause the current RDBMS success to stall! SQL + RDBMS suffers from many shortcomings, including: (1) Lack of support for truly ordered data (2) Lack of the concept of a subset defined by position in an ordered sequence plus count. (3) The previous poster's comment about inability to express a hierarchical query. From the standpoint of one who is concerned with performance, I view SQL and RDBMS as designed with NO throught to performance, with indexes sort of tossed in as an afterthought (while collective purists held their noses). (and Jon Krueger, please don't give me this BS about not having the RIGHT tools - we MUST use large-market share tools or our customers will not buy from us!), While it is true that much performance issues should be the concern of the database engine and hidden from most users, that doesn't mean that the user should have no significant control over it. We like to use an approach where we oversee performance issues in low level primitives that WE provide, which do performance oriented SQL (as much as possible), and turning database tables into "objects classes", the use of which is transparent to the main application. Unfortunately, with SQL, we had to write our own DDL and DML extensions of SQL, using preprocessors, in order to achieve both this encapsulation of function and to allow central control of performance and complex integrity rules. Now, I know that various vendors have various "extensions" to the language, or subroutines that represent extensions, that help with performance. However, as a creator of large scale software products (hotel central reservation systems, among others), we also need STANDARDIZATION and MARKET ACCEPTANCE. Let me give a simple example of a performance issue where the language fails to help. There are plenty of others. Lets say we have a table of names and related data. I want to read 5 names starting at a certain point so that I can display in a screen that allows a max of 5. Finally, I'm doing this with a front-end/back-end implementation such as Oracle 6 or Informix Turbo/OnLine using embedded queries. I have to define a cursor such as SELECT stuff FROM my-table WHERE name LIKE :host_variable ; or ... WHERE name > :host_variable ; Then, I open the cursor and do 5 fetches. Now, what goes on behind my back? Unless the database is prescient, or there is a NON-STANDARD extension to SQL, it has no way of knowing that I want exactly 5. So, a typical back-end/front-end system will fetch one message buffer's worth of data, and send it back. If this is more than 5, I have payed to read a bunch of records I will never use. If it is less than 5, I end up with extra message exchanges between the front end and the back-end. If sometime later, after the cursor has been closed [sometimes you are forced to close a cursor for practical reasons], I want name #6. I have no way of saying to SQL "hey you, give me the next row after row #x according to such and such ordering rule." I end up having to cook up some wierd query that may or may not give me exactly what I want (depending on whether a primary key enters into the where clause). On top of this, what I really want is an Object Oriented database. I eagerly await OODBs reaching enough market penetration that we can use them portably. And... I hope the standards that evolve or are created by committee take into account real world problems such as described above. others. -- John Moore HAM:NJ7E/CAP:T-Bird 381 {asuvax,mcdphx}!anasaz!john john@anasaz.UUCP Voice: (602) 951-9326 (day or eve) FAX:602-861-7642 Advice: Long palladium, USnail: 7525 Clearwater Pkwy, Scottsdale, AZ 85253 ......: Short petroleum Opinion: Support ALL of the bill of rights, INCLUDING the 2nd amendment!
tgreenla@oracle.uucp (Terry Greenlaw) (06/05/90)
In article <548@iss-rb.SanDiego.NCR.COM> benl@adt.SanDiego.NCR.COM (Ben.Lheureux) writes: >In article <1990Jun4.151555.3479@oracle.com> tgreenla@oracle.UUCP (Terry Greenlaw) writes: >>In article <jkrueger.644437146@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: >>> >>>> Oracle has an extension to SQL which was designed for tree traversal >>> >>>Sounds great. Except for one small problem: the only reason I use >>>SQL is compatibility and applications portability. >> >>Then you must be one very frustrated individual, since SQL compatability >>between >>vendors falls into the "virgin nymphomaniac" class of events. I don't think SQL >>is mature enough at this point to freeze expansion of the language in the name >>of compatability. > >Let's not forget that every vendor's ME-TOO desire to support SQL and the >relational model provided -- for the first time -- a meaningful level of >compatibility among divergent DMS's. > >Unfortunately because SQL is not SQL is not SQL, there is a strong desire >to identify a commonly used subset of SQL features among vendors, so that >the highly marketed compatibility supposedly provided by SQL can actually >be realized by users. I.e. formation of SAG, Ingres Open SQL, etc. > >>The extensions that Oracle and other vendors have provided >>are the driving forces that will lead to a language robust enough to be used >>in a unextended form. > >A convenient position to take, since Oracle just happens to have one of >the (perhaps THE) most robust SQL languages :-) Exceptions anyone? > >>For now, the basic SQL syntax is a good starting point >>for understanding a relational query language, but I wouldn't be relying on it >>for portability across vendors. > >I'm sure your disclaimer disqualifies you from speaking for all Oracle >Marketing organizations, but perhaps you can reconcile this position >with Oracle's HIGHLY-TOUTED SQL*Star concept, where Oracle applications, >presumably carefully coded in THE WONDERFUL, COMPATIBLE SQL language may >transparently run against Oracle, DB2, SQL/DS, or <name of your favorite >version of SQL*Connect here>? > >Benoit.Lheureux@sandiego.NCR.COM #################################### >Application Dev Tools, Dept 4775 # Opinions are my own, not NCR's # >16550 West Bernardo Drive # Farewell Micro C Magazine # >San Diego, CA 92127 619/485-3578 #################################### Actually, the SQL*Connect products (previously grouped under the SQL*Star blob of information) use SQL plus OUR extensions to SQL. We don't use DB2's SQL when connecting to a DB2 database. Our architecture is designed to seperate the underlying database type from the applications. Terry O. Greenlaw Sheathed within the Walkman, Staff Engineer Wear a halo of distortion. Oracle Corporation Aural contraceptive, tgreenla@oracle.oracle.com Aborting pregnant conversation - Marillion
davidm@uunet.UU.NET (David S. Masterson) (06/07/90)
In article <2371@anasaz.UUCP> john@anasaz.UUCP (John Moore) writes: > > Hopefully the RDBMS vendor community will realize that SQL is far from an > ideal query language for many commercial systems, and will thus put in the > extensions needed to both the language AND the model. If not, I predict > that OODB's or network DB's w/OODB's will cause the current RDBMS success > to stall! SQL is definitely lacking when it comes to many things that users are beginning to want. Everyone from Dr. Codd on down has admitted that at one point or another. The drive for standards (IMHO) has caused more harm than good in these areas because the standard is based on today's capabilities (which by now is a couple of years old) rather than where the definition should eventually be. If past track record holds, 2-3 years from now we'll probably have a relational language standard that incorporates OO concepts (whether it will be called SQL is anyone's guess). The relational model, on the other hand, is consistent with what it was defined to be consistent with (sets). In fact, it is more consistent (aka standard) than either the networked model or the OO model. What is needed (if anything) is a clear and complete OO model. Such a model will either supplant the relational model (because the relational model will simply be a subset of the OO model) or be incorporated into the prevailing model of the time (because the prevailing model will have the base functionality needed to represent the new model). > SQL + RDBMS suffers from many shortcomings, including: > (1) Lack of support for truly ordered data. I still have trouble understanding "truly ordered data". What is it that it is not expressed in an "ORDER BY" clause? The relational model works with sets and sets are not ordered. Ordering is a post-condition placed on the set of objects that meet a query. However, although a set does not imply an order, an index does. Is this "having your cake and eating it too"? > (2) Lack of the concept of a subset defined by position in an ordered > sequence plus count. The problem I have with this is the time-dependent nature of the subset. People usuall desire this capability so that they can close a cursor, go off and do other things, and come back to the cursor to pick up where they left off. The one question I have is what if the subset changed in between accesses (a likely thing in a high transaction environment)? That is, suppose what was the fifth item is now the sixth item because a new second item was added. > (3) The previous poster's comment about inability to express a > hierarchical query. This is definitely an area that needs more treatment in relational implementations. The relational model seems fully capable of representing such concepts, the problem is how to efficiently access such an arrangement and return it in a representation that can be dealt with. What does a hierarchical set look like? > From the standpoint of one who is concerned with performance, I view SQL > and RDBMS as designed with NO throught to performance, with indexes sort of > tossed in as an afterthought (while collective purists held their noses). Do you think an OODBMS gives any more thought to performance? Everything I've seen about OODBs leads me to believe the opposite -- the only performance considerations are the ones the database (not database system) designer designs in. The system designers merely provide functionality to help the database designer improve performance. IMHO, I think relational systems have a leg up in this area because of a more concrete model. > Now, I know that various vendors have various "extensions" to the language, > or subroutines that represent extensions, that help with performance. > However, as a creator of large scale software products (hotel central > reservation systems, among others), we also need STANDARDIZATION and MARKET > ACCEPTANCE. Define STANDARDIZATION? How does it differ from MARKET ACCEPTANCE? Is what the market accepts the "defacto" standard or are you looking for more in the name of standardization (a complete model, something that will last more than a couple of years, etc.)? After all, a standard is a standard is a standard... > On top of this, what I really want is an Object Oriented database. I > eagerly await OODBs reaching enough market penetration that we can use them > portably. And... I hope the standards that evolve or are created by > committee take into account real world problems such as described above. Don't jump too quickly on the OODB bandwagon. There may be nothing wrong with OODB, but move too quickly and you may be back in the same boat a couple of years from now. Its obvious from your message above that all your "questions" about relational databases have not been answered. Have all your "questions" been answered by object oriented databases (both those above and those yet to be stated)? (BTW, that's a rhetorical question directed at the group) -- =================================================================== David Masterson Consilium, Inc. uunet!cimshop!davidm Mt. View, CA 94043 =================================================================== "If someone thinks they know what I said, then I didn't say it!"
john@anasaz.UUCP (John Moore) (06/07/90)
In article <CIMSHOP!DAVIDM.90Jun6112135@uunet.UU.NET> cimshop!davidm@uunet.UU.NET (David S. Masterson) writes:
]should eventually be. If past track record holds, 2-3 years from now we'll
]probably have a relational language standard that incorporates OO concepts
](whether it will be called SQL is anyone's guess).
My guess also.
]anything) is a clear and complete OO model. Such a model will either supplant
]the relational model (because the relational model will simply be a subset of
]the OO model) or be incorporated into the prevailing model of the time
](because the prevailing model will have the base functionality needed to
]represent the new model).
Agreed.
]
]> SQL + RDBMS suffers from many shortcomings, including:
]> (1) Lack of support for truly ordered data.
]
]I still have trouble understanding "truly ordered data". What is it that it
]is not expressed in an "ORDER BY" clause? The relational model works with
Yeah... I wonder what I was thinking when I wrote that... Anyway the
point below (#2) indicates my real problem with ordering.
]> (2) Lack of the concept of a subset defined by position in an ordered
]> sequence plus count.
]
]The problem I have with this is the time-dependent nature of the subset.
]People usuall desire this capability so that they can close a cursor, go off
]and do other things, and come back to the cursor to pick up where they left
]off. The one question I have is what if the subset changed in between
]accesses (a likely thing in a high transaction environment)? That is, suppose
]what was the fifth item is now the sixth item because a new second item was
I suspect different answers suffice for different cases. For example,
I use the case of a name lookup, where I can only handle a few at a
time. Now, names may be added in that I didn't see before, that
would come before (in alpha ordering) the remaining names. I could
imagine one customer wanting the new names to show (after all, they
do satisfy the initial query conditions), while another might decide
that it was too confusing, so they want to just get the next name
from the last one displayed. Now, of course, the last one displayed may
have disappeared by the time we continue, but this can be handled
by backing up the "I'm here" pointer. Cursor options already allow
this sort of thing.
]> (3) The previous poster's comment about inability to express a
]> hierarchical query.
]
]This is definitely an area that needs more treatment in relational
]implementations. The relational model seems fully capable of representing
]such concepts, the problem is how to efficiently access such an arrangement
]and return it in a representation that can be dealt with. What does a
]hierarchical set look like?
I'm not sure single SQL queries can be written to deal with it. Obviously
the data can be stored in a relational database, but perhaps it has to
be retrieved by hand (i.e. - do a select, get something, look at it to
decide the next select, etc).
]
]> From the standpoint of one who is concerned with performance, I view SQL
]> and RDBMS as designed with NO throught to performance, with indexes sort of
]> tossed in as an afterthought (while collective purists held their noses).
]
]Do you think an OODBMS gives any more thought to performance? Everything I've
Sadly enough, they probably don't. But they will in the future. Who knows
whether the standards will adopt it.
]Define STANDARDIZATION? How does it differ from MARKET ACCEPTANCE? Is what
]the market accepts the "defacto" standard or are you looking for more in the
]name of standardization (a complete model, something that will last more than
]a couple of years, etc.)? After all, a standard is a standard is a
]standard...
A de-facto standard is just fine. All I want is to be able to run my
application using several different vendors' product, without rewriting
it or making significant changes.
]
]Don't jump too quickly on the OODB bandwagon. There may be nothing wrong with
]OODB, but move too quickly and you may be back in the same boat a couple of
]years from now. Its obvious from your message above that all your "questions"
Yep. We jumped on RDBMS when we had to, and at the time there was no
product on the market that could meet our needs. However, we anticipated
(after talks with vendors, this was informed anticipation ;-) )
that there would be before we went production. We have been working on the
project now for 2 years and go production in 5 months. We think we might
finally have a vendor product that will work. [I should mention that
another of our areas is 24 hr/7 day per week operation. At the time
we started, some products didn't allow you to archive the database while
it was running].
]about relational databases have not been answered. Have all your "questions"
]been answered by object oriented databases (both those above and those yet to
]be stated)? (BTW, that's a rhetorical question directed at the group)
No! I'll never be completely satisfied with a product in this area. The
techno-nerd in me complains that it could be better. The businessman responds
that everything could be better, but we have to deal with what we have :-)
--
John Moore HAM:NJ7E/CAP:T-Bird 381 {asuvax,mcdphx}!anasaz!john john@anasaz.UUCP
Voice: (602) 951-9326 (day or eve) FAX:602-861-7642 Advice: Long palladium,
USnail: 7525 Clearwater Pkwy, Scottsdale, AZ 85253 ......: Short petroleum
Opinion: Support ALL of the bill of rights, INCLUDING the 2nd amendment!jkrueger@dgis.dtic.dla.mil (Jon) (06/08/90)
tgreenla@oracle.uucp (Terry Greenlaw) writes: >it's name will be SQL II. Someone asked McCarthy what programming language would be like in thirty years. He said, in effect, "I don't know what they'll be like but they'll call it FORTRAN". Have we learned nothing? -- Jon -- Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger Drop in next time you're in the tri-planet area!
moiram@tekcae.CAX.TEK.COM (Moira Mallison) (06/08/90)
In article <jkrueger.644204650@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: > >SQL (and other query languages for RDBMS) can't express recursive >queries. So the simple answer is it can't be done. The longer answer >is ... without writing a program in some general purpose >programming language ... About a year and a half ago, I was working on a similar problem ( closure traversal of an n-ary sub-tree from an arbitrary node in the tree). The solutions I ended up with were similar to the one Jon proposed. At that time, I was told that Version 6.X would include cursors in ESQL which could be defined as a host-language variable. This solves the problem of not knowing the length of the path one is trying to follow, as the programmer could pass a counter and construct a cursor-name using the counter to assure uniqueness. Thus, we could at least use the recursive capabilities in the host language. Did this in fact make it into Ingres Version 6.0 ESQL or was it vaporware? (We're mostly running on machines that haven't been upgraded yet, for one reason or another). Moira Mallison CAX Data Management Tektronix, Inc
jkrueger@dgis.dtic.dla.mil (Jon) (06/08/90)
tgreenla@oracle.UUCP (Terry Greenlaw) writes: >>The extensions that Oracle and other vendors have provided >>are the driving forces that will lead to a language robust >>enough to be used in a unextended form. benl@adt.SanDiego.NCR.COM (Ben.Lheureux) writes: >A convenient position to take, since Oracle just happens to have >one of the (perhaps THE) most robust SQL languages :-) What does "robust" mean as used above? I am familiar with robust implementations; what makes a language itself "rubust"? Ability "to be used in an unextended form"? If so, good, I need to write device drivers, "robust" SQL will be just the thing. If not, how about letting us know what you're talking about? -- Jon -- Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger Drop in next time you're in the tri-planet area!
bg0l+@andrew.cmu.edu (Bruce E. Golightly) (06/08/90)
Actually, 6.2 and up can go that one better. Ingres now supports
dynamic SQL, which may be built on the fly. Cursors may involve host
langauage variables, according to the 6.2 doc on the shelf. I haven't
used wither of these features as yet, so I cannot relate any stories
based on personal experience.
#############################################################################
!
Bruce E. Golightly ! bg0l@andrew.cmu.edu (BeeGeeZeroEl)
Chief of Data Base Development ! (412)268-8560
Telecommunications Group !
Carnegie Mellon University ! UCC 117, 4910 Forbes Ave.
! Pittsburgh PA 15213-3890
President, Western Penna IUA !
#############################################################################tgreenla@oracle.uucp (Terry Greenlaw) (06/08/90)
In article <jkrueger.644779126@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: >tgreenla@oracle.uucp (Terry Greenlaw) writes: > >>it's name will be SQL II. > >Someone asked McCarthy what programming language would be like >in thirty years. He said, in effect, "I don't know what they'll >be like but they'll call it FORTRAN". > Sounds to me like he pretty much hit the nail right on the head. ForTran is still around in force, like it or not. For that matter, CoBOL has been carbon-dated at approx. Big Bang minus 4.5 million years and even our friend C is pushing 20. What I've learned is that I'd rather predict the stock market than anything with the word "COMPUTER" in it. >Have we learned nothing? > >Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger >Drop in next time you're in the tri-planet area! As far as learning nothing goes, I really think C was the language that I picked up the concept of nothing from. Good thing we don't still use Roman numerals, or we'd never be able to get at that first array element. But then again, I could be making Much Ado About Nothing ;-} Terry O. Greenlaw Sheathed within the Walkman, Staff Engineer Wear a halo of distortion. Oracle Corporation Aural contraceptive, tgreenla@oracle.oracle.com Aborting pregnant conversation - Marillion
davidm@uunet.UU.NET (David S. Masterson) (06/09/90)
In article <jkrueger.644779126@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: Have we learned nothing? Of course not. To paraphrase the old Simon and Garfunkel tune (forgive me, I forget which one): "The more things change, the more they stay the same" -- =================================================================== David Masterson Consilium, Inc. uunet!cimshop!davidm Mt. View, CA 94043 =================================================================== "If someone thinks they know what I said, then I didn't say it!"
benl@adt.SanDiego.NCR.COM (Ben.Lheureux) (06/10/90)
In article <jkrueger.644790134@dgis.dtic.dla.mil> jkrueger@dgis.dtic.dla.mil (Jon) writes: > >benl@adt.SanDiego.NCR.COM (Ben.Lheureux) writes: >>A convenient position to take, since Oracle just happens to have >>one of the (perhaps THE) most robust SQL languages :-) > >What does "robust" mean as used above? > >I am familiar with robust implementations; what makes a language >itself "robust"? Ability "to be used in an unextended form"? If so, >good, I need to write device drivers, "robust" SQL will be just the >thing. If not, how about letting us know what you're talking about? > That was a misleading use of "robust". I meant to say that Oracle supports a large number of SQL extensions like ROWID, statistical aggregate functions, and hierarchical queries, along with recently announced object-oriented features. Are these in SQL Level 1, 2 or 3? Nice to have, unless you're... ... developing portable applications which attempt to utilize a subset of SQL in its evolving state. Then this issue, rather than "robust" to define completeness of SQL as the-solution-to-all-DBMS-requirements, which is a concern. Vendors' products (Oracle*Star, Ingres Star, SQL/Windows from Gupta, Free-Form, etc.) base some application portability claims on SQL's "portability" values -- and in this case extensions are difficult to reconcile. Consider... >In article <1990Jun4.151555.3479@oracle.com> tgreenla@oracle.UUCP (Terry Greenlaw) writes: > >Actually, the SQL*Connect products (previously grouped under the SQL*Star blob >of information) use SQL plus OUR extensions to SQL. We don't use DB2's SQL when >connecting to a DB2 database. Our architecture is designed to seperate the >underlying database type from the applications. ...how is this accomplished? If you do not use "DB2's SQL", what do you mean by saying you use "SQL plus OUR extensions"? When using Oracle tools or applications through SQL*Connect (e.g. DB2), all, some or none of Oracle's SQL extensions must be handled by SQL*Connect. And DB2 must receive some form of the SQL command. Benoit.Lheureux@sandiego.NCR.COM #################################### Application Dev Tools, Dept 4775 # Opinions are my own, not NCR's # 16550 West Bernardo Drive # Farewell Micro C Magazine # San Diego, CA 92127 619/485-3578 ####################################
sweiger@sequent.UUCP (Mark Sweiger) (06/13/90)
In article <2371@anasaz.UUCP> john@anasaz.UUCP (John Moore) writes: <...legitimate gripes about SQL/RDBMS functionality problems deleted...> >On top of this, what I really want is an Object Oriented database. >I eagerly await OODBs reaching enough market penetration that we >can use them portably. And... I hope the standards that evolve or >are created by committee take into account real world problems >such as described above. > The problem with the current OODB world is that there is no standard OODB language, unlike SQL for RDBMS. Furthermore, there seems to be no evolution toward a standard. Add to this problem the current trend toward adding object-oriented extensions to SQL (Ingres Corporation's latest "Intelligent Database" releases, for example). I have the feeling that an object-oriented SQL RDBMS is what you are going to get, if you want portability. And us "old-time religion" RDBMS types can only hope that this OO-trend does not bring back those dreadful, application dependent, pointers that we thought we managed to rid the world of through the introduction of relational technology. Sometimes OODB seems like a rediscovery of the network model with abstract datatypes thrown into the resultant soup. The abstract types I like, but the pointers I could do without. -------------------------------------------------------- -- Mark Sweiger Sequent Computer Systems Database Software Engineer 15450 SW Koll Parkway Beaverton, Oregon 97006-6063 (503)526-4329 ...{tektronix,ogcvax}!sequent!sweiger
hunt@dg-rtp.dg.com (Greg Hunt) (06/16/90)
> In article <CIMSHOP!DAVIDM.90Jun6112135@uunet.UU.NET > cimshop!davidm@uunet.UU.NET (David S. Masterson) writes: > What does a hierarchical set look like? I presume you are asking about the internals of how the set is organized. I can give you my perspective on how a network model database organizes sets. I don't know if other systems are similar or not. The set itself is a B-tree index, using all the useful B-tree options. The pointer stored with a key value is the address of the data record that contains the key. That part is pretty standard. The rest of the "network model" is stored in the record header. There are two lists that are maintained. The first list contains a number of elements, one for each set that this record could potentially be a member in. If it is a member in a given set, the element contains the record address of the owning record occurrence. The second list also contains a number of elements, one for each set that this record could possibly be an owner of. If it owns a given non-empty set occurrence, then the element contains the address of the root node of the B-tree that contains the keys and record pointers in that set that this record owns. In traversing a path trough the database, you start with the system record, which always exists. From it, find the root node address of the first set in which you want to find a member record. You then search that B-tree to find the key or positional record you're interested in. The index contains the record address of that record. From there on, you repeat this going, down levels until you find the final record you want. The "owner list" in the record header is used to traverse the tree in the reverse direction, or upwards towards the root. This allows you to find the owner of a given record, in a given set occurrence. There is no requirement that a record be connected in all sets that it could potentially be. The pointers in the record header may be null. This is quite valid, and quite useful. Is this what you were interested in? Is my explanation clear? -- Greg Hunt Internet: hunt@dg-rtp.dg.com Data Management Development UUCP: {world}!mcnc!rti!dg-rtp!hunt Data General Corporation Research Triangle Park, NC These opinions are mine, not DG's.
garyp@cognos.UUCP (Gary Puckering) (06/20/90)
In article <355@brontolo.sublink.ORG> peter@brontolo.sublink.ORG (SINDATA Network administrator) writes: >In article <6588@umd5.umd.edu>, jay@umd5.umd.edu (Jay Elvove) writes: >> A friend of mine put this question to me: >> >> Given a two-column table, where column one is a primary key >> designating an employee and column two designates his boss, and >> columns one and two are identical when an employee is his/her own >> boss; using SQL, how would one go about displaying the chain of >> command of each employee in the table? Assume each employee can >> only have one boss. A simple example follows: >> >> >> Given F, the chain A >> of command is D B A / \ >> B C >> / \ >> D E >> / \ >> F G >> >It is the very hard problem of the "recursive cursor" that Date told >is not already resolved, because cursors are NOT recursive. >An ugly answer may be the following (using Informix's ESQL/C) : > >Assume that the table is named "company" and that column names are >"emp_name" and "boss_name". A more beautiful answer to this problem can be found in PowerHouse StarBase (from Cognos) and in InterBase (from Interbase Software Corporation). You can code requests that will be instantiated each time a recursive procedure calls itself. The above problem requires can be handled with the following C program: main () { int emp_no; printf ("\t\tEmployee Roster\n\n"); FOR e IN employees WITH e.boss MISSING printf ("%s %s\n",e.last_name,e.first_name); print_next (0, e.emp_no); END_FOR; EXEC SQL COMMIT RELEASE; } static print_next (lvl, boss_no) short lvl; int boss_no; { char dots[40]; int i; for (i=0; i<lvl; i++) dots[i]='.'; dots[i]='\0'; FOR (LEVEL lvl) e IN employees WITH e.boss = boss_no printf ("%s%s %s\n",template,e.last_name,e.first_name); print_next (lvl + 1, e.emp_no); END_FOR; } Sample output: Employee Roster Saluki Dimitri Chow Maudloop .Shepard Harold ..Basset Hermione ..Griffon Ronald .Setter Brenda ..Collie Alan ..Dalmation Edwin Bluetick Walter .Dachshund Emily The FOR construct is part of a relational sublanguage that can be intermixed with SQL. Among other things it: * sets up a cursor without explicit declaration * sets up a looping construct in the host language * sets up the termination condition for the loop * automatically defines host-language variables of the correct type and size The FOR construct also provides for passing in a request instantiation level number (the value provided after the LEVEL keyword). Essentially, this allows a new "cursor" to be opened each time the level number changes. -- Gary Puckering Cognos Incorporated VOICE: (613) 738-1338 x6100 P.O. Box 9707 UUCP: uunet!mitel!sce!cognos!garyp Ottawa, Ontario INET: garyp%cognos.uucp@uunet.uu.net CANADA K1G 3Z4
hunt@dg-rtp.dg.com (Greg Hunt) (06/27/90)
In article <CIMSHOP!DAVIDM.90Jun22125818@uunet.UU.NET>, cimshop!davidm@uunet.UU.NET (David S. Masterson) writes: > > A set is a collection of records, but a hierarchical set might contain > records > that are also sets (a collection of records). The question I have is what is > this concept useful in representing and what types of queries would result in > a hierarchical set (like what is the management chain of an employee)? This > leads to the question of modelling techniques for a database system that > incorporates this concept. Are normalization techniques capable of arranging > the data model to take advantage of this concept? I think I've misunderstood what you mean by a "hierarchical set". I was thinking you were refering to a set as defined by a hierarchical or network database model (e.g., CODASYL databases). In them, a record occurrence may own other sets of records, but the record itself is not a set. Sets are purely the "connections" between records. A set is owned by an owner record occurrence. The set contains pointers to the member record occurrences that are owned by that owner record. This may have been a terminology problem. A CODASYL "set" is not the same beast as a relational "set" which is based on the definition of an algebraic "set". It seems you mean that the set of records can be "rolled up" into a set that is a record in another set. That is quite a bit different than what I was thinking. Sets and records are not handled that way in the hierarchical or network model databases that I am familiar with. This concept sounds more like what might be found in an object-oriented database, where a set would contain objects, some of which are "records" and some of which are objects that contain other "records". I may have the analogy to an OODB all wrong since I have little experience with them. I posted a way to handle a "parts explosion" problem in a network model database in this thread a couple of weeks ago. If you missed it, I'd be happy to mail it to you. The quick answer to how it's done is this: it's a many-to-many relationship, which cannot be modeled directly since the "employee" record type would have to be both the owner and member in a set. Instead, a "link-record" is used and two sets are defined with the employee record as the owner and the link-record as the member. One of them is a "managed by" set, and the other is a "manager of" set. One or both of the sets must have a manual insertion criterion to allow you to build the proper relationships. To my knowledge, normalization techniques do not simply handle these types of many-to-many relationships. Some more artificial mechanism (like the link-record above) must be used. Other normalization techniques that are regularly applied to relational databases can (and should IMHO) be applied to network databases as well. They help reduce redundant data and relationships. Seeing that I've misunderstood what you were talking about, I'll stop describing the internals of network model databases and how they are used. -- Greg Hunt Internet: hunt@dg-rtp.dg.com Data Management Development UUCP: {world}!mcnc!rti!dg-rtp!hunt Data General Corporation Research Triangle Park, NC These opinions are mine, not DG's.
jkrueger@dgis.dtic.dla.mil (Jon) (06/29/90)
garyp@cognos.UUCP (Gary Puckering) writes: >A more beautiful answer to this problem can be found in PowerHouse >StarBase (from Cognos) and in InterBase (from Interbase Software >Corporation). You can code requests that will be instantiated each >time a recursive procedure calls itself. Clearly a better solution than is available through standard SQL. The program is cleaner to write and easier to read. However, from your code it appears that your engine doesn't support recursive queries, rather your query language allows programs recursively to submit many ordinary queries. Is this true? If so, one still writes a recursive program instead of a query, and performance will still be inherently poor. If not, could you give us an example of a recursive query? -- Jon -- Jonathan Krueger jkrueger@dtic.dla.mil uunet!dgis!jkrueger Drop in next time you're in the tri-planet area!