Box covers and domain orderings for beyond worst-case join processing

DOI10.4230/LIPICS.ICDT.2021.3MaRDI QIDQ7229575zbMATH OpenFDO

Authors Kaleb Alway, Eric Blais, Semih Salihoglu

Publication date 16 April 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICDT.2021.3

zbMATH Keywords

beyond worst-case join algorithmsbox coversdomain orderingsTetris

Mathematics Subject Classification ID

Database theory (68P15)

Cites work

• A note on the NP-hardness of the consecutive block minimization problem
• An algorithm for covering polygons with rectangles
• Close approximations of minimum rectangular coverings
• Complexities of efficient solutions of rectilinear polygon cover problems
• Constraint solving via fractional edge covers
• Covering Polygons Is Hard
• Covering Rectilinear Polygons with Axis-Parallel Rectangles
• Doubly Lexical Orderings of Matrices
• scientific article; zbMATH DE number 431993 (Why is no real title available?)
• Joins via geometric resolutions. Worst case and beyond
• Performance Guarantees on a Sweep-Line Heuristic for Covering Rectilinear Polygons with Rectangles
• Polynomial Complete Consecutive Information Retrieval Problems
• Size and treewidth bounds for conjunctive queries
• Size bounds and query plans for relational joins
• Size bounds for factorised representations of query results
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Using Semi-Joins to Solve Relational Queries
• Worst-case optimal join algorithms

Cited in

(1)

• Any-k algorithms for enumerating ranked answers to conjunctive queries

This page was built for publication: Box covers and domain orderings for beyond worst-case join processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7229575)