Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: Parts explosion with repeated subtrees

# Re: Parts explosion with repeated subtrees

From: Steve Kass <skass_at_drew.edu>
Date: Fri, 20 Dec 2002 03:35:00 -0500
Message-ID: <atukji\$2co\$1@slb9.atl.mindspring.net>

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

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

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US