Oracle FAQ Your Portal to the Oracle Knowledge Grid

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

Re: Parts explosion with repeated subtrees

From: Costin Cozianu <>
Date: Sat, 14 Dec 2002 16:34:04 -0800
Message-ID: <atgiip$13qg6l$>

If I were to represent polynomial in a database, I wouldn't use the 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.

Costin Cozianu

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:
> 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
> 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 Sat Dec 14 2002 - 18:34:04 CST

Original text of this message