Dataflow query processing and optimization.

This research presents a novel approach to parallel database processing based on treating database schema graphs as dataflow graphs. The problems addressed here include obtaining lower bounds on adjacency-preserving squashed embeddings of certain schema graphs (viz. ER schema graphs) in hypercube, design of a dataflow processing strategy, estimation of intermediate result sizes, and query optimization, all in the context of dataflow query processing. The dataflow processing strategy proposed here generates the query results in a single pass. Dataflow algorithms proposed in the past generally employ two pass strategy. In the second pass, a central coordinating processor generates the final result by combining the data generated by the various processors in the multicomputer system in the first pass. This strategy may result in the coordinating processor becoming the bottleneck. In the approach taken here, logical schema graphs are used as the physical representational structures. Nodes in the schema graph are mapped to a set of processors in a Shared Nothing multicomputer system to support parallel database processing. Nodes in the schema graph correspond to entity sets or object classes and are assumed to be directly implemented as such. Given a query graph, which is a subgraph of the schema graph, a key problem is determining the optimal dataflow directions in this graph. The problem of determining the optimal dataflow direction is formulated for single queries. The total number of schedules is determined for chain, tree and simple cyclic query graphs. A method is presented which enumerates all possible schedules of a general query graph. However, since the total number of schedules increases exponentially with the number of edges in the query graph, it is not feasible to determine the optimal schedule for a general query graph. Several heuristics are proposed to generate sub-optimal schedules. These include three heuristics for generating an initial schedule and eight heuristics for generating new schedules from a given schedule. Experiments are conducted to compare different heuristic combinations on a wide range of queries. The experiments show that the heuristics that generate chain schedules (or schedules that are "close" to a chain schedule) have the lowest cost.PhDComputer, Information and Control EngineeringUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/105899/1/9226903.pdfDescription of 9226903.pdf : Restricted to UM users only