Re: lightweight database

Raymond Wiker wrote:
"vanekl" <vanek@xxxxxxx> writes:

Yikes. You're way off. The worst-case scenario is O(m.n),
where:
m is the number of records in the database, and
n is the number of joins.
I'm sure that if I gave this some thought I could do better.

O(m^n), surely?

God no, not if ^ represents the exponential operator. Why did you add an
exponent? To be clear, I guess I should have explicitly added a multiply
sign: O(m*n).


Good luck getting that to scale linearly.

The analysis is linear, not exponential, not even polynomial. I also gave an
upper bound based on a minute and a half of thinking. Surely somebody can do
better when they sit down and apply themselves for more than that.


map/reduce works because you don't have joins... the "table" is
effectively a completely de-normalized view of your data.

I take issue with your presumption that the data must be completely
denormalized. It doesn't. Joins can be simulated if the full denormalized
record is not incorporated within one atomic record. That's why I said that
the analysis required (an upper bound of) O(m*_n_) time, because a
brute-force algorithm would have to search the entire db for each join. If
the db was completely denormalized, as you suggest, the time analysis
reduces to O(m).


Also (and this should have been mentioned earlier): quoting
Moore's law is fine as long as you are talking about sequential
processing. When you switch to parallel processing, you should also
consider Amdahl's law.

The debate on that would take me on a tangent I'm not willing to spend time
on at the moment. It's an interesting point you raise, but, like I said, a
tangent, especially considering you dispute the main points of my position.


.

Relevant Pages

  • Re: 0^0=1
    ... exponent, interpreting 0^0 as 1 simplifies formulas and eliminates the ... slope of the tangent line at _any_ x. Replacing r by 1 in the general ...
    (sci.math)
  • Re: 0^0=1
    ... exponent, interpreting 0^0 as 1 simplifies formulas and eliminates the ... slope of the tangent line at _any_ x. Replacing r by 1 in the general ...
    (sci.math)
  • Re: The logarithm function
    ... A logarithm is an exponent. ... 4 is the square root ... You can read more on my page "It's the Law Too - The Laws of ...
    (uk.education.maths)
  • Re: too much information!
    ... Androcles wrote: ... >> And surely you now realize by the law of exponents ... If you want to eat Crow you have to ...
    (sci.math)
  • Re: too much information!
    ... Androcles wrote: ... >> And surely you now realize by the law of exponents ... If you want to eat Crow you have to ...
    (sci.physics)