article · Zurich Open Repository and Archive (University of Zurich) · 2022

The Complexity of Boolean Conjunctive Queries with Intersection Joins

Abo Khamis, Mahmoud, Chichirim, George, Kormpa, Antonia, Olteanu, Dan

Cited by 0Open access

Abstract

Intersection joins over interval data are relevant in spatial and temporal data settings. A set of intervals join if their intersection is non-empty. In case of point intervals, the intersection join becomes the standard equality join. We establish the complexity of Boolean conjunctive queries with intersection joins by a many-one equivalence to disjunctions of Boolean conjunctive queries with equality joins. The complexity of any query with intersection joins is that of the hardest query with equality joins in the disjunction exhibited by our equivalence. This is captured by a new width measure called the IJ-width. We also introduce a new syntactic notion of acyclicity called iota-acyclicity to characterise the class of Boolean queries with intersection joins that admit linear time computation modulo a poly-logarithmic factor in the data size. Iota-acyclicity is for intersection joins what alpha-acyclicity is for equality joins. It strictly sits between gamma-acyclicity and Berge-acyclicity. The intersection join queries that are not iota-acyclic are at least as hard as the Boolean triangle query with equality joins, which is widely considered not computable in linear time.

Cite this paper

APA 7

Abo Khamis, M., Chichirim, G., Kormpa, A., & Olteanu, D. (2022). The Complexity of Boolean Conjunctive Queries with Intersection Joins. Zurich Open Repository and Archive (University of Zurich). https://doi.org/10.5167/uzh-255538

MLA 9

Abo Khamis, Mahmoud, et al. “The Complexity of Boolean Conjunctive Queries with Intersection Joins.” Zurich Open Repository and Archive (University of Zurich), 2022, https://doi.org/10.5167/uzh-255538.

Chicago

Abo Khamis, Mahmoud, George Chichirim, Antonia Kormpa, and Dan Olteanu. 2022. “The Complexity of Boolean Conjunctive Queries with Intersection Joins.” Zurich Open Repository and Archive (University of Zurich). https://doi.org/10.5167/uzh-255538.

Harvard

Abo Khamis, M. et al. (2022) ‘The Complexity of Boolean Conjunctive Queries with Intersection Joins’, Zurich Open Repository and Archive (University of Zurich). Available at: https://doi.org/10.5167/uzh-255538.

BibTeX

@article{abokhamis2022complexity,
  title = {{The Complexity of Boolean Conjunctive Queries with Intersection Joins}},
  author = {Abo Khamis, Mahmoud and Chichirim, George and Kormpa, Antonia and Olteanu, Dan},
  journal = {Zurich Open Repository and Archive (University of Zurich)},
  year = {2022},
  doi = {10.5167/uzh-255538}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.