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.