ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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}
}

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Ape88]
Peter M. G. Apers: Data Allocation in Distributed Database Systems. ACM Trans. Database Syst. 13(3): 263-304(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bre77]
...
[CGT90]
Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CNW83]
Stefano Ceri, Shamkant B. Navathe, Gio Wiederhold: Distribution Design of Logical Database Schemas. IEEE Trans. Software Eng. 9(4): 487-504(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kri84]
Balakrishnan Krishnamurthy: An Improved Min-Cut Algorithm for Partitioning VLSI Networks. IEEE Trans. Computers 33(5): 438-446(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Li88]
Yingnan Philip Li: DKM - A Distributed Knowledge Representation Framework. Expert Database Conf. 1988: 313-331 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mos92]
Chris Moss: Commercial Applications of Large Prolog Knowledge Bases. PDK 1991: 32-40 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RW79]
...
[San89]
Laura A. Sanchis: Multiple-Way Network Partitioning. IEEE Trans. Computers 38(1): 62-81(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRN90]
...
[SV91]
Huzur Saran, Vijay V. Vazirani: Finding k-cuts within Twice the Optimal. FOCS 1991: 743-751 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:04 2010 by Michael Ley (ley@uni-trier.de)