Some Issues in Design of Distributed Deductive Databases
Mukesh Mohania, Nandlal L. Sarda · 1994
The design of a distributed deductive database system differs from the design of conventional non-distributed deductive database systems in that it requires design of distribution of both the database and rulebase. In this paper, we address the rule allocation problem. We consider minimization of data communication cost during rule execution as a primary basis for rule allocation. The rule allocation problem can be stated in terms of a directed acyclic graph, where nodes represent rules or relations, and edges represent either dependencies between rules or usage of relations by rules. The arcs are given weights representing volume of data that need to flow between the connected nodes. We show that rule allocation problem is NP-complete. Next, we propose a heuristic for nonreplicated allocation based on successively combining adjacent nodes for placement at same site which are connected by highest weight edge, and study its performance vis-a-vis the enumerative algorithm for optimal all...