Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: Parts explosion with repeated subtrees
Damjan,
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.
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
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
Damjan S. Vujnovic wrote:
>Suppose we have to design a database that will be able to:
>
> - 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.
>
>
>
>
Received on Fri Dec 20 2002 - 02:35:00 CST