Not logged in.
Quick Search - Contribution
Contribution Details
| Type | Working Paper |
| Scope | Discipline-based scholarship |
| Title | The Complexity of Boolean Conjunctive Queries with Intersection Joins |
| Organization Unit | |
| Authors |
|
| Language |
|
| Institution | Cornell University |
| Series Name | ArXiv.org |
| Number | 13342 |
| ISSN | 2331-8422 |
| Date | 2021 |
| Abstract Text | 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. |
| Free access at | DOI |
| Digital Object Identifier | 10.48550/arXiv.2106.13342 |
| Other Identification Number | merlin-id:22020 |
| PDF File |
Download from ZORA
|
| Export |
BibTeX
EP3 XML (ZORA)
|