Re: formal (theoretical) treatment of database indices

falcon schrieb:
> 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.

Yes, there is a huge gap between the currently dominating data models and how data is operated in practice. Unfortunately, indexes are not considered an important element in the existing data models. Moreover, there is a dominating (wrong, IMHO) opinion that they must be treated as a secondary mechanism or implementation details at the physical level of the database, i.e., a good data model should not include them. This is why you hardly can find anything concerning this issue. In order to consider indexes theoretically as a part of the model you need to develop a new data model where they will have some new treatment different from a convenience or access optimization mechanism. (However, proposing data models is a polytical issue so you will be punished for doing that without officical permission.)

My opinition is that indexes are not simply access optimization technique but play more important role and should be an integral part of a data model. Indexes in such a model is a bridge between layers. In other words, an index allows us to convert higher level coordinate system (references) into a lower level coordinate system. It is an access indirection mechanism. Of course, normally we want to ignore indexes treating them as implementation details when working at higher levels. However, frequently we might want to consider how layers are connected and this is precisely where we need indexes to be a part of our data model. In other words, if our model has many layers then indexes are intended to implement a link between them. If two layers are developed by a data modeller then he is also responsible for maintaining an index between them. In this case we cannot ignore indexes anymore because they are as important as other elements of the model.

--
http://conceptoriented.com