Re: Relational Algorithms

Hi Martin,

Martin Sutton schrieb in Nachricht
<8ensb8$rnm$1_at_seagoon.newcastle.edu.au>...
>Database algorithms are not my area at all but I need to get
>some idea of the time complexity of the algorithms used to manipulate
>relational database tables. For example, when performing a JOIN, is a
>cartesian product actually taken first and then the 'live' rows selected or
>is(are) there algorithms for this task with a better performance?

considerable optimizations can be done when you are using equi-joins and indexes:

It is basic knowledge that sorting a set takes n * log(n) steps, so does creating an index. Searching in an ordered set takes log(n) steps.

If you combine two tables with an equi-join, it is at least necessary to step through one table and to find the key value in the other, so this would require normally n * log(m) operations (you may define n as the minimum count of records, so n * log(n)  would be appropriate).

Another idea would be to use a hash table as an index for a database table. In a hash table, any key can be found in approximately 1 step, so a join would only require n steps.

Greetings from the antipodes,
Joachim

--
There is damezumari at the bamboo joint.