Query translation in a heterogeneous distributed database on hypergraph models
Mohammad Mehdi Owrang Ojaboni · 1986
The problem of query translation in a heterogeneous distributed database is examined. The hypergraph model is used as a means of modeling different database models; e.g., relational hierarchical, and network data models. The hypergraph is extended to incorporate the DML operations in order to define a general model for query translation. We assume that we have two database designs over essentially the same attribute set. The designs are not the same, but attempt to support basically the same set of semantics. The two designs are represented in the hypergraph format. The hypergraph representing the design for which the query was written is called the source hypergraph and the second is given as the target hypergraph. To translate the query, we need three operations: (1) Map the source query into the hypergraph space of the source hypergraph. (2) Translate the resulting source query hypergraph into the hypergraph space of the target hypergraph. (3) Map the target query hypergraph to the target data manipulation language. Transformation rules (algorithms) are provided for each step of query translation. The query translation process is evaluated in terms of query equivalence and time complexity. The time complexity of the overall query translation process is shown to be (in the worst case) polynomial in n and m, where n is the number of edges in the target hypergraph and m is the number of statements in the source query.