Re: formal (theoretical) treatment of database indices

"falcon" <shahbazc_at_gmail.com> wrote in message news:1128574013.545837.163640_at_z14g2000cwz.googlegroups.com...
> 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.
>

It's not clear to me why you consider query optimization unimportant from a theoretical viewpoint. It seems to me that optimization theory is just as "important" in its own right, as data modeling theory. And indexes are bound to be discussed along with optimization for reasons that other replies have already dealt with.

From a purely practical viewpoint, the optimizer in DEC Rdb/VMS was a very important part of the infrastucture I relied on when building tables, indexes, and queries, back in 1994. Not that I understood it terribly well. I only knew enough about it to get it to tell me which indexes were used for which queries. But a solid infrastructure allowed me to keep the design simple and sound, without worrying too much about performance. By comparison the "rule based optimizer" in Oracle RDBMS version 7.1 was lame.

The Oracle optimizer looked only at the query. The Rdb optimizer looked at both the query and the (approximate) sizes of the tables. Big difference. Received on Wed Oct 12 2005 - 14:38:53 CEST