Parts explosion with repeated subtrees
--CELKO--
Imagine that we have a forest of trees called "Menu" which stores the
menu items for a restaurant. The first level under the root is the
dishes served. Each dish is then decomposed into its ingredients; the
ingredient can be either simple (salt, water, milk, flour, etc) or it
can have a recipe of its own (Béarnaise sauce, Hollandaise sauce,
etc.)
Let me build a tree of each dish or recipe down to its most basic
simple ingredients:
CREATE TABLE Menu
(dish_name VARCHAR (25) NOT NULL,
food_item VARCHAR (25) NOT NULL,
item_type CHAR (6) NOT NULL DEFAULT ‘simple'
CHECK (item_type IN (‘dish', ‘recipe', ‘simple')),
PRIMARY KEY (dish_name, food_item),
<< constraints >>);
INSERT INTO Menu
VALUES (‘Eggs Benedict', ‘English Muffin', ‘simple'),
(‘Eggs Benedict', ‘Canadian Bacon', ‘simple'),
(‘Eggs Benedict', ‘Egg', ‘simple'),
(‘Eggs Benedict', ‘Béarnaise sauce', ‘recipe');
INSERT INTO Menu
VALUES (‘Béarnaise sauce', ‘Dill', ‘simple'),
(‘Béarnaise sauce', ‘Hollandaise sauce', ‘recipe');
INSERT INTO Menu
VALUES (‘Hollandaise sauce', ‘Egg‘, ‘simple'),
(‘Hollandaise sauce', ‘Lemon Juice‘, ‘simple'),
(‘Hollandaise sauce', ‘Butter‘, ‘simple');
If I put the Menu into a nested set model, I would want to build a
full tree for each menu item. However, things like ‘Béarnaise sauce'
and ‘Hollandaise sauce' are going to appear all over the place.
I can recursively expand each ingredient which has a recipe of its own
until I have a result set of only simple ingredients.
But is there another model or better query which would allow us to
find all the simple ingredients of a given dish?
Costin Cozianu
(Food_Item -> Item_Type) and food_item is not candidate key.
Technically what you have is a DAG (directed acyclic graph) and not a
forest. What it boils down to is the transitive closure. What's about
this problem that is different from any other parts explosion problem ?
Transitive closure should have been part of SQL and SQL based products
ages ago, and probaby it's not yet, but can be solved relatively painful
using Db2 recursive queries, Oracle CONNECT BY operator, or using hand
made "materialized view" tables updated via triggers. I don't know
what's the problem with "trees". Vendors don't pay attention to the
users (they're busy implementing other UFOs like XML, "objects" and
object pointers), the SQL committee doesn't pay attention to anyone. I
mean recursive queries might be a cool trick in theory but it can't
address the basic needs of the user: a safe and simple way to resolve
the transitive closure.
Joe, you have to confess that you orchestrated this whole thing, so that
you can publish a whole book full of twisted and mind boggling Joe Celko
style SQL, solving a problem that in a normal world would be absolutely
trivial :)
How about SQL committee specify a TRANSITIVE CLOSURE JOIN, abd vendors
implement it correctly, would you still publish a book on trees in SQL ?
best regards,
Costin Cozianu
Is it not proven that transitive closure is impossible in SQL ?
Damjan S. Vujnovic
: It looks to me that it's a badly designed schema to begin with.
:
: (Food_Item -> Item_Type) and food_item is not candidate key.
:
: Technically what you have is a DAG (directed acyclic graph) and not a
: forest. What it boils down to is the transitive closure. What's about
: this problem that is different from any other parts explosion problem ?
:
: Transitive closure should have been part of SQL and SQL based products
: ages ago, and probaby it's not yet, but can be solved relatively painful
: using Db2 recursive queries, Oracle CONNECT BY operator, or using hand
: made "materialized view" tables updated via triggers. I don't know
: what's the problem with "trees". Vendors don't pay attention to the
: users (they're busy implementing other UFOs like XML, "objects" and
: object pointers), the SQL committee doesn't pay attention to anyone. I
: mean recursive queries might be a cool trick in theory but it can't
: address the basic needs of the user: a safe and simple way to resolve
: the transitive closure.
:
: Joe, you have to confess that you orchestrated this whole thing, so that
: you can publish a whole book full of twisted and mind boggling Joe Celko
: style SQL, solving a problem that in a normal world would be absolutely
: trivial :)
:
: implement it correctly, would you still publish a book on trees in SQL ?
How about performance issues? Optimization? Even if something like
TRANSITIVE CLOSURE JOIN (TCL from now on) becomes a standard, the alternate
hierarchy representations would still make sense (of course, depending on
what do you wanna do with your data). Can you imagine the horror of
(ab)using? SQL (as is) is "adapted" (sorry for my English) to squeeze the
best performance from relational model. The goal is to design our tables in
such a manner that we need simple SELECT on one table, and not monsters like
TCJ to make the things done.
:
: best regards,
: Costin Cozianu
:
: Is it not proven that transitive closure is impossible in SQL ?
Yes, but just because of that, you change the way you are representing your
"relation" (the one you want to find it's transitive closure) and all of a
sudden simple old SELECT is quite good enough.
Don't misunderstand me, I'm not against something like TCL (but I'll stay
away from it if I can), but IMO even after introducing TCL into SQL,
alternate representation would still make sense.
regards,
Damjan S. Vujnovic
University of Belgrade
School of Electrical Engineering
Department of Computer Engineering & Informatics
Belgrade, Yugoslavia
http://galeb.etf.bg.ac.yu/~damjan/
P.S. I haven't give it a second thought, but I think Oracle's CONNECT BY
operator won't save us here because one node can have more than one
"parent"...
Costin Cozianu
Performance issues ? Optimization ?
I guess you should bring the separation between physical and logical
models into discussion first. One you distort the logical model you
present to the user, to make room for an "optimization" you are more
than likely to suffer much more than you gain.
Once a TCLOSE operator is in place, encoded trees and the whole Celko's
book are an absolute no-no.
How do you achieve performance with TCLOSE ?
CREATE INDEX I ON "Relation" (Parent_id, Child_id)
OPTIMIZE FOR TRANSITIVE CLOSURE
// ... eventually with other options
Or CREATE MATERIALIZED VIEW AS TCLOSE("Relation")
> :
> : best regards,
> : Costin Cozianu
> :
> : Is it not proven that transitive closure is impossible in SQL ?
>
> Yes, but just because of that, you change the way you are representing your
> "relation" (the one you want to find it's transitive closure) and all of a
> sudden simple old SELECT is quite good enough.
>
Create a transitive closure view and a simple old SELECT is good enough.
> Don't misunderstand me, I'm not against something like TCL (but I'll stay
> away from it if I can), but IMO even after introducing TCL into SQL,
> alternate representation would still make sense.
>
No they wouldn't make any sense. It is abusing and damaging the logical
schema, it is a lot of duplication of code and effort by the end user
for a thing that should be solved elementarily by the vendor.
> regards,
> Damjan S. Vujnovic
>
> University of Belgrade
> School of Electrical Engineering
> Department of Computer Engineering & Informatics
> Belgrade, Yugoslavia
>
> http://galeb.etf.bg.ac.yu/~damjan/
>
> P.S. I haven't give it a second thought, but I think Oracle's CONNECT BY
> operator won't save us here because one node can have more than one
> "parent"...
>
I need to check for that. I am sure it will fail on cycles however. But
probably neither recursive views in DB2 or SQL 99 are not good for the
general case because a cycle can blow them away. One can limit the
"LEVEL" say where LEVEL < 100 and ... pray for the best :) Very far from
what we can call decent software engineering.
Computing transitive closure is an assignment to first year students on
Algorithms and Data Structures 101. It is ridiculous that multi billion
dollar vendors abdicate from their responsibility to give their users
what they need. It is also a big disaster in economical terms. A vendor
could probably solve this problem easily once and for all (don't know
maybe 1 million - 10 million dollars effort ?). Users instead suffer
great losses in terms of lost time, brittle software, bugs, data
corruption, etc, etc and they have to reinvent the same broken wheel
time and time again. No user can do this right because the only place
where this can be done right is at the DBMS engine level.
Best regards,
Costin Cozianu
Damjan S. Vujnovic
- represent polinomials, like:
Ai(x) = ai[ni]*x^ni + ... + ai[1]*x + ai[0]
- support math operations on them, like:
"For a given A1(x), ..., A1000(x) find polinomial A1001(x) where
A1001(x) = A1(x)*A2(x)* ... *A999(x) + A1000(x)"
The most frequent task would be to multiply those polinomials. Adding
polinomials is less frequent operation (say 1000 times), as well as
calculating the value of a polinomial Ai(x) for a given x.
I'm quite aware that my brain would be pleased with the representation like:
CREATE TABLE Poli (
poli_name VARCHAR(10) NOT NULL,
coeff_order INT NOT NULL,
coeff_value FLOAT NOT NULL,
CONSTRAINT pk_Coeff PRIMARY KEY(poli_name, coeff_order));
but my brain won't do any queries on those tables... RDBMS will. So, I find
myself responsible to neglect my ego and serve my data to RDBMS in a way
that is most acceptable to it.
Would it be a sin to represent those polinomials using FFT? If no, in what
way is this different to representing trees with some brain-unfriendly pairs
of numbers called "nested sets"?
regards,
Damjan
http://galeb.etf.bg.ac.yu/~damjan/
P.S. I'm quite aware that no one would ever use RDBMS to multiply
polinomials and that this example is a complete fiction, but the point to
show that the design closest to our brain is not always closest to the
"brain" of the RDBMS.
Costin Cozianu
table you described, I'd use a User Defined Type. And specifically
because I'd have to support all the algebraic operations on polynomials.
However, please tell me what *specific* operations the nested set is
designed to support that a TCLOSE can't support equally as well.
I can tell you some very common operations that are problematic with the
usual encoding of trees using nested sets, materialized path or other
things:
UPDATE, INSERT, DELETE
Add to that the fact that nested sets don't support DAGs which are quite
common in real data modeling practice. You also have to consider that
more often than not relational databases are not designed to support a
very specialized operation but to represent the "business data", i.e. a
set of true propositions about the enterprise, that usually are
exploited in more than one way to serve different user's needs,
perspectives, etc.
From this point of view, it is quite clear that in relational data
modeling a binary relation *should* be represented just as a binary
relation. And when queries such as part explosion are issued, it is
clear that the user refers to the transitive closure of a binary
relation (in their own words they might say, find me all x "related
directly or indirectly" to y such that ...).
By comparison, you can hardly conceive that the "nature" of a polynomial
is a relation on N x K (where N is naturals and K is the field where the
coefficients are drawn from), therefore I don't think the polynomial is
a good analogy.
So while I don't contend that one might encode data in a different way
than it's most "seemingly natural" representation, I'm curious to see
how this can be justified for nested sets or other tree representations.
regards,
Costin Cozianu
--CELKO--
products ages ago, and probaby it's not yet, but can be solved
operator, or using hand made "materialized view" tables updated via
triggers. <<
Actually, the WITH operator you see in DB2 is taken from the SQL-99
Standard
and gives us a nice way to hide repeated UNIONs that buyild a
transitive closure. The Oracle CONNECT BY is a hidden cursor and it
really stinks; it is not even a good kludge.
>> Joe, you have to confess that you orchestrated this whole thing, so
that
you can publish a whole book full of twisted and mind boggling Joe
Celko style SQL, solving a problem that in a normal world would be
absolutely trivial :)<<
NAH!!! I am trying to get *other people* to write a whole book full of
twisted and mind boggling Joe Celko style SQL for me!!
Seriously, I can come up with a full parts explosion in a tree, if I
repeat the explosions of all occurences of common subassemblies. But
I keep thinking that there should be a neat, clean, simple way to have
one tree for each common subassembly and somehow copy it into the full
explosion.
I can find the common subassemblies with an exhaustive search:
1) Go to each node, find the size of the subtree rooted at that node,
where size = (rgt-lft+1)/2
2) Compare the nodes in each pair of samed-size subtrees.
3) If two subtrees have the same set of nodes, then compare the
structure of the two subtrees.
4) If the two subtrees have the same set of nodes and the same
structure, then they are the same subassembly.
But should I put them into another table, give the subassembly a name
and use that name in the original parts explosion?
Joe "Nuke Me Xemu" Foster
> I can find the common subassemblies with an exhaustive search:
>
> 1) Go to each node, find the size of the subtree rooted at that node,
> where size = (rgt-lft+1)/2
>
> 2) Compare the nodes in each pair of samed-size subtrees.
>
> 3) If two subtrees have the same set of nodes, then compare the
> structure of the two subtrees.
>
> 4) If the two subtrees have the same set of nodes and the same
> structure, then they are the same subassembly.
>
> But should I put them into another table, give the subassembly a name
> and use that name in the original parts explosion?
This may depend on real-world information not captured by your schema,
especially if that same set of parts can be assembled into different
objects with different configurations, such as LEGO building blocks.
--
Joe Foster <mailto:jlfoster%40znet.com> Got Thetans? <http://www.xenu.net/>
WARNING: I cannot be held responsible for the above They're coming to
because my cats have apparently learned to type. take me away, ha ha!
Tony V
model. The SQL required to answer your question if the menu is
modeled like this is rather elegant.
/* Menu code tested on SQL Server 2000 */
Create Table Menu
( iMenuId int not null,
item varchar(25) not null,
iParentId int not null,
iLevelId int not null
)
INSERT INTO Menu select 1,'Eggs Benedict', 0, 1
INSERT INTO Menu select 2, 'English Muffin', 1, 2
INSERT INTO Menu select 3, 'Canadian Bacon', 1, 2
INSERT INTO Menu select 4, 'Egg', 1, 2
INSERT INTO Menu select 5, 'Béarnaise sauce', 1,2
INSERT INTO Menu select 6, 'Dill', 5, 3
INSERT INTO Menu select 7, 'Hollandaise sauce', 5, 3
INSERT INTO Menu select 8, 'Egg', 7,4
INSERT INTO Menu select 9, 'Lemon Juice', 7,4
INSERT INTO Menu select 10, 'Butter', 7, 4
/* All simple items used in construction of Eggs Benedict */
select distinct item from menu where iMenuId not in (select iParentId
from menu)
/* All Child Items of Eggs Benedict that are recipes */
select item from menu where iMenuId in (select iParentId from menu)
and iParentId <> 0
In the case of representing a full menu at a restaurant I would add
one more
column called iTreeId int not null.
71062...@compuserve.com (--CELKO--) wrote in message news:<c0d87ec0.02121...@posting.google.com>...
--CELKO--
this what you meant to post, if you used ISO-11179 specs, had keys,
constraints, etc. ?
CREATE TABLE Menu
(menu_id INTEGER NOT NULL PRIMARY KEY,
item VARCHAR(25) NOT NULL,
parent_id INTEGER NOT NULL
REFERENCES Menu(menu_id),
level_id INTEGER NOT NULL);
INSERT INTO Menu VALUES (1,'Eggs Benedict', 0, 1);
INSERT INTO Menu VALUES (2, 'English Muffin', 1, 2);
INSERT INTO Menu VALUES (3, 'Canadian Bacon', 1, 2);
INSERT INTO Menu VALUES (4, 'Egg', 1, 2);
INSERT INTO Menu VALUES (5, 'Béarnaise sauce', 1, 2);
INSERT INTO Menu VALUES (6, 'Dill', 5, 3);
INSERT INTO Menu VALUES (7, 'Hollandaise sauce', 5, 3);
INSERT INTO Menu VALUES (8, 'Egg', 7, 4);
INSERT INTO Menu VALUES (9, 'Lemon Juice', 7, 4);
INSERT INTO Menu VALUES (10, 'Butter', 7, 4);
Sorry, but a few decades of writing and working with standards makes
me a bit complusive. Now, another human being can read and use your
code to test things in any Standard SQL!!
Having done that work, this is an Adjacency model and it has the same
problem my nested set model does. Namely, 'Béarnaise sauce' and
'Hollandaise sauce' explosions have to be repeated in EVERY recipe.
In your model, they will get various level numbers, in mine, they get
various (lft,rgt) pairs.
What I want is a way for them to appear once in the schema and
expanded in a VIEW as tehy are used.
David Cressey
> problem my nested set model does. Namely, 'Béarnaise sauce' and
> 'Hollandaise sauce' explosions have to be repeated in EVERY recipe.
> In your model, they will get various level numbers, in mine, they get
> various (lft,rgt) pairs.
>
> What I want is a way for them to appear once in the schema and
> expanded in a VIEW as tehy are used.
Hmmm.... It seems to me that Lisp ran into a similar problem, sometime in
the late 1950s.
The way they got around it, IIRC, was to invent "atoms". If there's a
difference between "atoms"
and named variables, it eludes me. Maybe it's that with variables, the
type goes with the variable, while with atoms the type goes with the value.
Once you have given something a name, you can include it multiple times,
by merely naming it
where the expansion would have belonged. Lawyers call this "incorporating
by reference".
Maybe a similar thing is what you are looking for.
Tony V
ou are probably aware Microsoft has many proprietary extensions or
ways of writing SQL.
I see your point. I guess I will have a reason to by your new book.
:)
Tony
71062...@compuserve.com (--CELKO--) wrote in message news:<c0d87ec0.0212...@posting.google.com>...
Costin Cozianu
> me a bit complusive. Now, another human being can read and use your
> code to test things in any Standard SQL!!
>
> Having done that work, this is an Adjacency model and it has the same
> problem my nested set model does. Namely, 'Béarnaise sauce' and
> 'Hollandaise sauce' explosions have to be repeated in EVERY recipe.
> In your model, they will get various level numbers, in mine, they get
> various (lft,rgt) pairs.
So here you have it: the "Standard SQL" you seem so proud of is useless
for a very basic and common task. If I understand you correctly WITH
RECURSIVE will not work decently for anything but trees.
Would you be willing to shortly present here the semantics of WITH
RECURSIVE ? My understanding of it (and I'm sorry that I can't really
spend time and money on the standard ) is that it adds successive
generations (levels) of bags of rows, until no longer possible (for
example in case of trees ) or until the equivalent of Stack Overflow
Error happens.
If this is how it is, the solution is to either drop the standard as
unusable and technically inadequate, or to suggest to the honourable
committee that an excursion in time back to Dr. Codd's papers would be
more than adequate.
After we get back the relational database ideas that have been hijacked
and perverted by the "standard", as to the point where it makes users
life miserable, we will humbly look upon the SQL standard as nothing but
a nuissance that has to be circumvented in order to engineer solid
information systems, and a pretext for Joe Celko to boast about the
usefulness of standards.
SQL is a false standard, it always has been. It's been implemented only
fractionally and SQL 92 has still yet to be implemented so people would
better focus very carefully on their product SQL reference and not on
the SQL standard. I could understand a call for standards if the SQL
standard was some ideal to dream for, and we could only blame the
vendors for failing to live up to the dream. The problem is that now
most students learns at Databases 101 how SQL is broken. Which brings up
to the only de facto standard there is for relational databases: Dr.
Codd's relational algebra and relational calculus.
We're all for standards, but not at all costs. The costs of SQL
standardization seems to begin to outweigh the benefits. Like for
example users will have to spend money and trees will need to be cut for
Joe Celko's book on ... trees. I imagine you'll later want to write a
follow-up on directed acyclic graphs.
Going back to the problem at hand, it would be a much better use of
everybody's time and a much better use of the "lungs of the planet", if
Joe Celko's would write up a nice letter to the SQL committee
explaining that the set-oriented transitive closure is an *absolutely
essential* feature for database users, that with all his knowledge of
SQL he can't solve trivial problem.And a standard that doesn't meet the
needs of its users becomes slowly but surely irrelevant.
Costin
--CELKO--
useless
for a very basic and common task. If I understand you correctly WITH
RECURSIVE will not work decently for anything but trees. <<
No, the WITH operator is quite powerful and general in Standard
SQL-99. Look up the details SQL-99 COMPLETE, REALLY by Gulutzan &
Pelzer or in SQL-99 by Melton & Simon. The best examples of actual
use are in Chamberlain's DB2 book. Yes, you can do a parts explosion
in one SELECT with SQL-99 -- and a lot more.
>> Would you be willing to shortly present here the semantics of WITH
RECURSIVE? My understanding of it (and I'm sorry that I can't really
spend time and money on the standard) is that it adds successive
generations (levels) of bags of rows, until no longer possible (for
example in case of trees) or until the equivalent of Stack Overflow
Error happens. <<
That is the most basic form. You also have SEARCH [DEPTH FIRST BY
|BREADTH FIRST BY], CYCLE, etc. etc. You are hiding a pretty general
and complex program inside one statement. (That complexity is why I
don't like it and vendors don't implement it)
>> SQL is a false standard, it always has been. It's been implemented
only fractionally and SQL 92 has still yet to be implemented ... <<
It is a real standard; ISO approved it. Most SQL vendors are
(finally!) at intermediate or full SQL-92. They are slowly making
SQL-92 syntax an option when they already had a proprietary syntax
(i.e. SQL Server uses both getdate() and CURRENT_TIMESTAMP now, etc.).
>> so people would better focus very carefully on their product SQL
reference and not on the SQL standard. <<
I write very Standard SQL and have very little trouble translating my
Standard SQL into a dialect. I can also get products that will do
this for me. Otherwise, ODBC and JDBC would not work.
>> Like for example users will have to spend money and trees will need
to be cut for Joe Celko's book on ... trees. I imagine you'll later
want to write a
follow-up on directed acyclic graphs. <<
Actually, I was thinking about doing book six on either data quality
or on how to write bad SQL. We have poor data quality in database, so
this is a good topic. We also have new SQL programers who are
determined to write bad code, so perhaps a book that shows them the
common errors would help.
The only way I have found to model a graph in SQL is with an adjacency
list model. The algorithms from procedural languages adapt fairly
easily.
>> ...the set-oriented transitive closure is an *absolutely essential*
feature for database users, that with all his knowledge of SQL he
can't solve trivial problem.And a standard that doesn't meet the needs
of its users becomes slowly but surely irrelevant. <<
I can do a transitive closure for a tree in the nested set model. My
problem is that I want to be able to extract and insert sub-trees
easily. I would prefer a declarative way, so I can hide the insertion
in non-procedural code.
This might not be possible. For example, the nested set model cannot
handle a general graph because it is a partial ordering on a set. And
you cannot color a map with less than four colors, but life goes on.
David Cressey
> or on how to write bad SQL. We have poor data quality in database, so
> this is a good topic. We also have new SQL programers who are
> determined to write bad code, so perhaps a book that shows them the
> common errors would help.
Damn, that's a good topic!
When I think of the number of bad databases I've seen, and the number of
bad queries I've seen against pretty good databases, I think there's a gold
mine there. And the thing is, the same errors seem to keep on cropping up.
People have these fixed ideas about how they can improve on the relational
model, and reduce the number of joins, without ever really getting a clear
idea of how the engine really works. And they don't know how to map reality
into relations!
I suppose, if you called it something like "SQL from Dummies", you'd get
sued. Good luck, Joe!
--
Regards,
David Cressey
www.dcressey.com
Mikito Harakiri
Arguably, #1 on list might be forgetting join condition, so that Cartesian
Product is returned. But can we really tell by looking into the query only,
without knowing the data? Hardly. For example the intention might be two
queies combined into a single one.
#2 is extracting data from a complex join view, when a single table query is
needed. This is solely an optimization issue -- smart optimizer would reduce
the execution path to scanning the relevant table only.
#3: "1=1" predicate in the query. Again, this might serve some purpose: for
example, application programmer have trouble counting poles and spaces
between poles, so that when generating SQL he simply concateneates "and
predicate" conjuncts.
In short, SQL is a high abstraction language. It is difficult to do stupid
things in the high level language. Counter examples please.
"David Cressey" <da...@dcressey.com> wrote in message
news:pG7M9.348$0I3....@petpeeve.ziplink.net...
--CELKO--
stupid things in the high level language. <<
Difficult, not impossible. I have more faith in stupid people than you
do <g>!!
>> Counter examples please. <<
Code with a cursor to update a table that could have been written with
a single SQL statement.
Or go to www.dbdebunk.com and read the some of the quotes.
>> Damn, that's a good topic! <<
I think so too.
>> ... the same errors seem to keep on cropping up. <<
which is why a book would work --if they were making new exciting
errors, I could not compile them.
>> I suppose, if you called it something like "SQL from Dummies",
you'd get
sued. <<
The DUMMIES people threaten us when the first edition of SQL FOR
SMARTIES came out. Welcome to America, the country with 1 lawyer for
ecvery 400 citizens!
Mikito Harakiri
> Code with a cursor to update a table that could have been written with
> a single SQL statement.
That's procedural.
It's quite easy to spot a newbie in any programming language, for example
http://mindprod.com/newbie.html
Not in SQL, though.
> Or go to www.dbdebunk.com and read the some of the quotes.
Those are just quotes, not SQL code snippets. People can say stupid things,
but they are very constrained to implement them in a formal language.
> The DUMMIES people threaten us when the first edition of SQL FOR
> SMARTIES came out. Welcome to America, the country with 1 lawyer for
> ecvery 400 citizens!
I haven't been in america long enough, is idiot's movement a phenomenon of
90's?
http://news.messages.yahoo.com/bbs?action=m&board=37138445&tid=nmhealthphili
pmorrisjudgmentdc&sid=37138445&mid=67
Steve Kass
Don't be so sure no one would multiply polynomials with the
representation your brain likes. It's the representation I would use,
and I got the coding right on the first try, which I might well not have
if I'd tried to do this in C++. I'm a little rusty on FFTs, but this and
other linear algebra problems are quite well-suited to SQL.
As for the current thread, there are some research papers
(which I haven't read) on efficient algorithms for maintaining
the transitive closure of a DAG in SQL - it's definitely an important
and interesting problem.
-- Code written in SQL Server's T-SQL dialect
create table Polynomials (
polyID int not null,
expo int not null,
coeff float,
primary key (polyID,expo)
)
insert into Polynomials values (1,0,3.4)
insert into Polynomials values (1,1,5.30)
insert into Polynomials values (1,3,-2.5)
insert into Polynomials values (1,4,4.3)
insert into Polynomials values (2,1,-1.1)
insert into Polynomials values (2,2,-3.1)
go
create procedure poly_mult(
@id_1 int,
@id_2 int,
@id_result int
) as
insert into Polynomials
select
@id_result,
p1.expo + p2.expo,
sum(p1.coeff*p2.coeff)
from Polynomials p1, Polynomials p2
where p1.polyID = @id_1
and p2.polyID = @id_2
group by p1.expo + p2.expo
having sum(p1.coeff*p2.coeff) <> 0
go
exec poly_mult 1,2,3
go
select * from Polynomials
go
drop proc poly_mult
drop table Polynomials
Steve Kass
Drew University
--CELKO--
on the first try, which I might well not have if I'd tried to do this
Poly_mult(...) <<
I thought I was over the top when I put matrix math in SQL FOR
SMARTIES!!
If you have some time to kill, write up a polynominal library and
you're got a section in the third edition of SQL FOR SMARTIES with
credit.
I gues this proves one of Codd's contentions; namely, that you can
represent almost any kind of data in a set oriented model.