Complex transitive closure queries on a fragmented graph

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

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

    8 Citations (Scopus)
    150 Downloads (Pure)


    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
    Subtitle of host publicationThird International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings
    EditorsSerge Abiteboul, Paris C. Kanellakis
    Place of PublicationBerlin, Heidelberg
    Number of pages15
    ISBN (Electronic)978-3-540-46682-6
    ISBN (Print)978-3-540-53507-2
    Publication statusPublished - 12 Dec 1990
    EventThird International Conference on Database Theory, ICDT 1990 - Paris, France
    Duration: 12 Dec 199014 Dec 1990

    Publication series

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


    ConferenceThird International Conference on Database Theory, ICDT 1990
    OtherDecember 12-14, 1990

    Cite this