Re: formal (theoretical) treatment of database indices

falcon wrote:
> My curiosity
> regarding the role of indexes is how to develop a (or find an existing)
> theory that is 'orthogonal' to the relational model.

Indeed. Orthogonality is key.

> In some ways, the
> theories of types (and programming language semantics in general) can
> be combined with the relational model to allow formal studies of both
> individually, as well as when combined.

Yes, but this doesn't mean we want to mix implementation and interface. To the greatest extent possible we want the implementation *not* to influence the interface. To do otherwise binds the interface to the implementation, which in turn restricts how the interface can be implemented. (It sounds circular but it's not.)

> We have disk drives, memories, caches, etc.

These are implementation.

> There must be a way to
> create a bridge between the relational model and physical storage.

There are many, many ways. Every DBMS is such a bridge.

> I can imagine that if a formal datamodel were combined with a formal
> storage/disk layout/whatever system, we could develop algorithms which
> could automatically map the data model on to physical storage.

The best implementation for a data model will depend on how that data model is used. It is not enough to know the schema; you also have to know all the queries, and the frequency at which they are executed. In other words, this is not static data, but runtime data. You need to have runtime instrumentation of the query engine to get the info you want.

Of course, the specific application may want to favor one query over another, and this will not be determinable from either the schema or the runtime data. So we also need a way for the humans to specify some quality of service to override the default optimizations. We might be willing to sacrifice some overall throughput of the system to keep query A highperformance.

I think automatic optimization is a great idea, but I also think it comes *after* having a good *declarative* way of just being able to manually specify this sort of thing. Which I think we don't particularly have yet. Once we have a good set of tools we can manually choose from, we have a basis for automatically choosing the right tool.

Marshall Received on Sun Oct 09 2005 - 19:29:54 CEST