Re: Relational Algorithms

>> 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. <<

Try the ACM publications for pure algorithms. Your real problem is that each SQL product has a different internal way of representing tables (files with indexes, hashing, bit vectors, compressed bit vectors, etc.) so they all use different algorithms internally. For example EXISTS() predicates do well in DB2 and not so well in ACCESS.

>> 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? <<

No, that one is really dumb. There are a few basic ones from relational algebra -- do non-correlated subqueries once, avoid cross joins, etc. David Maier's THEORY OF RELATIONAL DATABASES might help there.

The usual thing is to do the SARGs first (search arguments -- things of the form <column> = <constant>) to dreduce the size of the tables being joined. I have 100 row in A and 100 rows in B; the Cross Join (the SQL term for Cartesian Product) has 10000 rows. But if I only extract 10 rows from each table I have wasted a great deal of resources.

--CELKO--
Joe Celko, SQL and Database Consultant

Sent via Deja.com http://www.deja.com/
Before you buy. Received on Wed May 03 2000 - 00:00:00 CEST