Re: formal (theoretical) treatment of database indices

I understand that indexes are just for optimization, but it seems that their evaluation from a different perspective could be very helpful. For one thing, better formal reasoning would allow easier query optimization. For example, materialized viewes are also basically just a utility for optimization, yet the query re-write systems usually know about them. We don't have to have special, mat. view specific operators.

Actually the main reason I even thought of this was because Torsten Grust, in his PhD thesis "Comprehending Queries," mentions that something called Paramorphs could be used to allow better reasoning of indexes (rest of the thesis mainly talks about catamorphs which, as far as I can tell, are similar to foldr in functional programming).

Clearly I am very confused about this issue. I'm a new comer to database theory, but even more so to functional programming...I'm hoping someone can shed some light on this issue. Received on Wed Oct 05 2005 - 23:46:53 CDT