Re: formal (theoretical) treatment of database indices

falcon wrote:
> Almost everytime I see indices (indexes?) mentioned in text books or
> papers, it seems they are relagated to the query optimization section.
> Algebra/Calculus level primitives never take an index into account.
> I'm wondering if there has been any work done on making indices more
> important at a theoretical level. I'll appreciate any pointers.

The reason why indexes are marginalized in the theory books is that they are primarily a way of speeding up access when reading data (at the cost of slowing update activity). The same answer could be obtained for a given query even if the indexes were absent - albeit usually a lot more slowly. Since the same answer is obtained whether indexes are present or not, they are theoretically unncessary. In practice, they are important - but only as an optimization, not as a fundamental data structure.

-- 
Jonathan Leffler                   #include <disclaimer.h>
Email: jleffler_at_earthlink.net, jleffler_at_us.ibm.com
Guardian of DBD::Informix v2005.02 -- http://dbi.perl.org/