An Iterative Approach for Rules and Data Allocation in Distributed Deductive Database Systems

In a distributed deductive database system, queries which invoke rules executing at different sites and access different data need to be executed rather efficiently. Therefore, the rules invoked and relations accessed by the queries need to be allocated to sites so as to reduce the data transfer cost in processing a given set of queries. The rules and data allocation problem needs to take into consideration complex interdependencies among queries, rules and data. In this paper, we develop a comprehensive cost model for total data transfer incurred in processing a given set of queries by incorporating the dependencies among queries, rules and data. Furthermore, we develop an iterative approach to generate near-optimal solution for the combined rules and data allocation problem by using our cost model. In this approach, we start with an initial data allocation which is used for rule allocation, which in turn is used for data allocation, and so on. We stop this iterative rules and data allocation procedure when there is no further reduction in total data transfer cost incurred in processing the given set of queries. We also present the results of experiments conducted to evaluate the effectiveness of our approach by comparing the results with the exhaustive enumeration solution (which guarantees the optimal solution).