Record Details

A SELECTIVE ENUMERATION BASED HEURISTIC FOR RULE ALLOCATION

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A SELECTIVE ENUMERATION BASED HEURISTIC FOR RULE ALLOCATION
 
Creator MOHANIA, MK
SARDA, NL
 
Subject systems
deductive databases
distributed databases
rulebase
dependency graph
clustering
 
Description A distributed deductive database system consists of many autonomous deductive database systems connected by a computer network to facilitate sharing of both database and rules. The design of a distributed deductive database system differs from the design of conventional nondistributed deductive database systems. The former requires design of distribution of both the database and rulebase, whereas the latter requires design of data distribution. The paper addresses the problem of allocating rules in a distributed deductive database system, where rulebase (a collection of rules) and database are shared across autonomous sites. The problem is relevant and challenging in applications involving large rulebases. We have identified communication cost as the primary consideration in allocation of rules. The optimal allocation of rules over a set of sites is an NP-complete problem. It has prohibitive execution time for large rulebases. In this paper, we propose an efficient heuristic algorithm for non-replicated rule allocation and study its performance vis-a-vis the enumerative algorithm for optimal allocation. A heuristic for replicated allocation of rules is also presented which starts from the non-replicated allocation.
 
Publisher BUTTERWORTH-HEINEMANN LTD
 
Date 2011-07-19T07:11:23Z
2011-12-26T12:51:03Z
2011-12-27T05:37:23Z
2011-07-19T07:11:23Z
2011-12-26T12:51:03Z
2011-12-27T05:37:23Z
1994
 
Type Article
 
Identifier INFORMATION AND SOFTWARE TECHNOLOGY, 36(10), 625-636
0950-5849
http://dx.doi.org/10.1016/0950-5849(94)90022-1
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5208
http://hdl.handle.net/10054/5208
 
Language en