Complex transitive closure queries on a fragmented graph

M.A.W. Houtsma, Maurice A.W. Houtsma, Peter M.G. Apers, Stefano Ceri

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    7 Citations (Scopus)
    77 Downloads (Pure)

    Abstract

    In this paper we study the reformulation of transitive closure queries on a fragmented graph. We split a query into several subqueries, each requiring only a fragment of the graph. We prove this reformulation to be correct for shortest path and bill of material queries. Here we describe the reformulation for an abstract graph, elsewhere we have described an actual implementation of our approach and some promising simulation results. We view the study of distributed computation of transitive closure queries as a result of the trend towards distributed computation. First selections were distributed to fragments of a relation, then fragmentation was used to compute joins in a distributed way, and now we are studying distributed computation of transitive closure queries. This should result in a deeper insight into the use and possible benefit of parallelism. Our work may be used in ordinary distributed databases as well as advanced multiprocessor database machines, such as PRISMA. Although this research was started to efficiently use distributed computation, it turns out to be beneficiary in a central environment as well. This is due to the introduction of extra selections, stemming from an appropriate fragmentation. This leads to extra focus on relevant data.
    Original languageEnglish
    Title of host publicationICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings
    EditorsSerge Abiteboul, Paris C. Kanellakis
    Place of PublicationBerlin
    PublisherSpringer
    Pages470-484
    Number of pages15
    ISBN (Print)9783540535072
    DOIs
    Publication statusPublished - 12 Dec 1990

    Publication series

    NameLecture notes in computer science
    PublisherSpringer
    Volume470
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Keywords

    • METIS-119724
    • IR-96072

    Cite this

    Houtsma, M. A. W., Houtsma, M. A. W., Apers, P. M. G., & Ceri, S. (1990). Complex transitive closure queries on a fragmented graph. In S. Abiteboul, & P. C. Kanellakis (Eds.), ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings (pp. 470-484). (Lecture notes in computer science; Vol. 470). Berlin: Springer. https://doi.org/10.1007/3-540-53507-1_96