Some Issues in Design of Distributed Deductive Databases.
Mukesh K. Mohania, Nandlal L. Sarda:
Some Issues in Design of Distributed Deductive Databases.
VLDB 1994: 60-71@inproceedings{DBLP:conf/vldb/MohaniaS94,
author = {Mukesh K. Mohania and
Nandlal L. Sarda},
editor = {Jorge B. Bocca and
Matthias Jarke and
Carlo Zaniolo},
title = {Some Issues in Design of Distributed Deductive Databases},
booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
publisher = {Morgan Kaufmann},
year = {1994},
isbn = {1-55860-153-8},
pages = {60-71},
ee = {db/conf/vldb/vldb94-60.html},
crossref = {DBLP:conf/vldb/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
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 allocation. Our results show that the
heuristic produces acceptable allocations. We also extend our heuristic
for partially replicated allocation.
Copyright © 1994 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.):
VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile.
Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX
References
- [Ape88]
- Peter M. G. Apers:
Data Allocation in Distributed Database Systems.
ACM Trans. Database Syst. 13(3): 263-304(1988) BibTeX
- [Bre77]
- ...
- [CGT90]
- Stefano Ceri, Georg Gottlob, Letizia Tanca:
Logic Programming and Databases.
Springer 1990, ISBN 3-540-51728-6
BibTeX
- [CNW83]
- Stefano Ceri, Shamkant B. Navathe, Gio Wiederhold:
Distribution Design of Logical Database Schemas.
IEEE Trans. Software Eng. 9(4): 487-504(1983) BibTeX
- [CP86]
- ...
- [CR91]
- ...
- [DJP+92]
- Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis:
The Complexity of Multiway Cuts (Extended Abstract).
STOC 1992: 241-251 BibTeX
- [GJ79]
- M. R. Garey, David S. Johnson:
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
- [HBH94]
- ...
- [JF90]
- Robert J. K. Jacob, Judith N. Froscher:
A Software Engineering Methodology for Rule-Based Systems.
IEEE Trans. Knowl. Data Eng. 2(2): 173-189(1990) BibTeX
- [Kri84]
- Balakrishnan Krishnamurthy:
An Improved Min-Cut Algorithm for Partitioning VLSI Networks.
IEEE Trans. Computers 33(5): 438-446(1984) BibTeX
- [Li88]
- Yingnan Philip Li:
DKM - A Distributed Knowledge Representation Framework.
Expert Database Conf. 1988: 313-331 BibTeX
- [Mos92]
- Chris Moss:
Commercial Applications of Large Prolog Knowledge Bases.
PDK 1991: 32-40 BibTeX
- [MS93a]
- ...
- [MS93b]
- ...
- [MS93c]
- ...
- [PS82]
- ...
- [RB92]
- Tzvi Raz, Nancy A. Botten:
The knowledge base partitioning problem: Mathematical formulation and heuristic clustering.
Data Knowl. Eng. 8: 329-337(1992) BibTeX
- [RW79]
- ...
- [San89]
- Laura A. Sanchis:
Multiple-Way Network Partitioning.
IEEE Trans. Computers 38(1): 62-81(1989) BibTeX
- [SRN90]
- ...
- [SV91]
- Huzur Saran, Vijay V. Vazirani:
Finding k-cuts within Twice the Optimal.
FOCS 1991: 743-751 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:02 2009