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.

• 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)

create procedure poly_mult(

  _at_id_1 int,
  _at_id_2 int,
  _at_id_result int

  insert into Polynomials
  select
    _at_id_result,
    p1.expo + p2.expo,
    sum(p1.coeff*p2.coeff)
  from Polynomials p1, Polynomials p2
  where p1.polyID = _at_id_1
  and p2.polyID = _at_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 - 09:35:00 CET