Efficient processing of containment queries on nested sets

A. Ibrahim, G.H.L. Fletcher

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

2 Citations (Scopus)

Abstract

We study the problem of computing containment queries on sets which can have both atomic and set-valued objects as elements, i.e., nested sets. Containment is a fundamental query pattern with many basic applications. Our study of nested set containment is motivated by the ubiquity of nested data in practice, e.g., in XML and JSON data management, in business and scientific workflow management, and in web analytics. Furthermore, there are to our knowledge no known efficient solutions to computing containment queries on massive collections of nested sets. Our specific contributions in this paper are: (1) we introduce two novel algorithms for efficient evaluation of containment queries on massive collections of nested sets; (2) we study caching and filtering mechanisms to accelerate query processing in the algorithms; (3) we develop extensions to the algorithms to a) compute several related query types and b) accommodate natural variations of the semantics of containment; and, (4) we present analytic and empirical analyses which demonstrate that both algorithms are efficient and scalable.
Original languageEnglish
Title of host publicationProceedings of the 16th International Conference on Extending Database Technology (EDBT'13, Genoa, Italy, May 18-22, 2013)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages227-238
ISBN (Print)978-1-4503-1597-5
DOIs
Publication statusPublished - 2013
Eventconference; 16th International Conference on Extending Database Technology -
Duration: 1 Jan 2013 → …

Conference

Conferenceconference; 16th International Conference on Extending Database Technology
Period1/01/13 → …
Other16th International Conference on Extending Database Technology

Fingerprint Dive into the research topics of 'Efficient processing of containment queries on nested sets'. Together they form a unique fingerprint.

  • Cite this

    Ibrahim, A., & Fletcher, G. H. L. (2013). Efficient processing of containment queries on nested sets. In Proceedings of the 16th International Conference on Extending Database Technology (EDBT'13, Genoa, Italy, May 18-22, 2013) (pp. 227-238). Association for Computing Machinery, Inc. https://doi.org/10.1145/2452376.2452404