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.
@cite_0: 1 Introduction 2 A Syntax for Data 3 XML 4 Query Languages 5 Query Languages for XML 6 Interpretation and advanced features 7 Typing semistructured data 8 Query Processing 9 The Lore system 10 Strudel 11 Database products supporting XML
@cite_12: Intervals represent a fundamental data type for temporal, scientific, and spatia l databases where time stamp s and point data are extended to time spans and range data, respectively. For OLTP a nd OLAP applications on large amount s of data, no t only intersection queries have to be processed efficiently but also general interval relationships including before, meets, overlaps, starts, finishes, contains, equals, during, startedBy, finishedBy, overlappedBy, metBy, and after. Our new algorithms use the Relational Interval Tree, a purely SQL-base d and object-relationally wrapped index structure. The technique therefore pre serves the industrial strength of the underlying RDBMS including stability, transactions, and performance. The efficiency of our approach is demonstrated by an experimental evaluation on a real weblog data set containing one million sessions.
@cite_7: 
@cite_6: This invention is directed to an improved stop and loader assembly for use in a sawmill and the like, and more particularly includes an improved combination slapper bar and log turner. The combination slapper bar and log turner preferably includes a rectangular hollow slapper bar section which contains a movable member having a plurality of teeth pivotally attached thereto. A fluid-actuated piston assembly is provided for drawing the movable member and teeth longitudinally in and out of the slapper bar. A slot is further provided in the upper end of the slapper bar and adjacent any sawlog reposing on the carriage next to the slapper bar, whereby the teeth fall out of the slapper bar in an extended position to engage the log when the movable member is thrust upward in the slapper bar, and whereby the teeth fold into the slapper bar whenever the movable member is drawn downward therein.
Indexing techniques for relational databases is a large field of study. An overview of indexing of semistructured data, e.g., acyclic digraphs and XML data, may be found in @cite_0 . A particular indexing technique for digraphs based on encoding paths as strings is introduced in @cite_6 . In @cite_7 the authors, of that paper, describe an analysis framework for tree-structured balanced access methods for evaluating performance, based on performance loss metrics" and assumed optimal tree structures. Stabbing and interval queries may be resolved using various trees and structures and recently the relational interval tree has been introduces, see @cite_12 for the RI-tree and further references.