  We introduce indexing of tables referencing complex structures such as
digraphs and spatial objects, appearing in genetics and other data intensive
analysis. The indexing is achieved by extracting dimension schemas from the
referenced structures. The schemas and their dimensionality are determined by
proper coloring algorithms and the duality between all such schemas and all
such possible proper colorings is established. This duality, in turn, provides
us with an extensive library of solutions when addressing indexing questions.
It is illustrated how to use the schemas, in connection with additional
relational database technologies, to optimize queries conditioned on the
structural information being referenced. Comparisons using bitmap indexing in
the Oracle 9.2i database, on the one hand, and multidimensional clustering in
DB2 8.1.2, on the other hand, are used to illustrate the applicability of the
indexing to different technology settings. Finally, we illustrate how the
indexing can be used to extract low dimensional schemas from a binary interval
tree in order to resolve efficiently interval and stabbing queries.
