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)
    58 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
    Houtsma, M.A.W. ; Houtsma, Maurice A.W. ; Apers, Peter M.G. ; Ceri, Stefano. / Complex transitive closure queries on a fragmented graph. ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings. editor / Serge Abiteboul ; Paris C. Kanellakis. Berlin : Springer, 1990. pp. 470-484 (Lecture notes in computer science).
    @inproceedings{7fd81eb6188144cab9f738e115b8b03f,
    title = "Complex transitive closure queries on a fragmented graph",
    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.",
    keywords = "METIS-119724, IR-96072",
    author = "M.A.W. Houtsma and Houtsma, {Maurice A.W.} and Apers, {Peter M.G.} and Stefano Ceri",
    year = "1990",
    month = "12",
    day = "12",
    doi = "10.1007/3-540-53507-1_96",
    language = "English",
    isbn = "9783540535072",
    series = "Lecture notes in computer science",
    publisher = "Springer",
    pages = "470--484",
    editor = "Serge Abiteboul and Kanellakis, {Paris C.}",
    booktitle = "ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings",

    }

    Houtsma, MAW, Houtsma, MAW, Apers, PMG & Ceri, S 1990, Complex transitive closure queries on a fragmented graph. in S Abiteboul & PC Kanellakis (eds), ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings. Lecture notes in computer science, vol. 470, Springer, Berlin, pp. 470-484. https://doi.org/10.1007/3-540-53507-1_96

    Complex transitive closure queries on a fragmented graph. / Houtsma, M.A.W.; Houtsma, Maurice A.W.; Apers, Peter M.G.; Ceri, Stefano.

    ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings. ed. / Serge Abiteboul; Paris C. Kanellakis. Berlin : Springer, 1990. p. 470-484 (Lecture notes in computer science; Vol. 470).

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

    TY - GEN

    T1 - Complex transitive closure queries on a fragmented graph

    AU - Houtsma, M.A.W.

    AU - Houtsma, Maurice A.W.

    AU - Apers, Peter M.G.

    AU - Ceri, Stefano

    PY - 1990/12/12

    Y1 - 1990/12/12

    N2 - 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.

    AB - 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.

    KW - METIS-119724

    KW - IR-96072

    U2 - 10.1007/3-540-53507-1_96

    DO - 10.1007/3-540-53507-1_96

    M3 - Conference contribution

    SN - 9783540535072

    T3 - Lecture notes in computer science

    SP - 470

    EP - 484

    BT - ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings

    A2 - Abiteboul, Serge

    A2 - Kanellakis, Paris C.

    PB - Springer

    CY - Berlin

    ER -

    Houtsma MAW, Houtsma MAW, Apers PMG, Ceri S. Complex transitive closure queries on a fragmented graph. In Abiteboul S, Kanellakis PC, editors, ICDT '90: Third International Conference on Database Theory Paris, France, December 12–14, 1990 : proceedings. Berlin: Springer. 1990. p. 470-484. (Lecture notes in computer science). https://doi.org/10.1007/3-540-53507-1_96