Searching Proper Replications in Mapping XML into Relations

摘要

In this paper, we introduce two efficient search methods that heuris-tically find proper replications close to the optimal value. These searched replications can notably reduce the overall query cost in mapping XML into relations. The necessity of such an automatic tool arises from the complexity of XML, i.e., the fact that it is difficult to search the optimal replication set to enhance query performance because of mass complex XML data and queries. Moreover, it was observed that the search problem requires exponential time of the number of given queries. Another important problem in implementing them is that exact query cost can not be measured within reasonable time. That is, actually executing an XML query over actual relational schema costs much time whenever a replication is evaluated in the algorithms, and effective estimation technique is needed. To overcome the obstacle, we considered the histogram-based estimation in commercial RDBMS. It is very simple and can support exact estimation. In addition, it can resolve the trait of highly skewed structure in XML very well. Finally, the effect of two search methods and the estimation are analyzed through some experiments.