Errata for "Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products"

Summary: Erratum corrects Line 5 of EnumerateCmp, which over-prunes recursive complement enumeration. The bug omits connected-subgraph/complement pairs and can miss optimal bushy join trees; an example exposes the failure and corrected behavior. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11788
Venue: VLDB
Year: 2018
Pagerank: 5.093636e-05
Overall Rank: 11,930 | 18.15%
DOI: 10.14778/3231751.3231756

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Andreas Meister (University of Magdeburg)
2. Guido Moerkotte (University of Mannheim)
3. Gunter Saake (University of Magdeburg)

BibTeX Citation

@article{meister_vldb18,
        title = {{Errata for "Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products"}},
        author = {Meister, Andreas and Moerkotte, Guido and Saake, Gunter},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {10},
        pages = {1069},
        doi = {10.14778/3231751.3231756},
        url = {https://doi.org/10.14778/3231751.3231756},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,014	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB
2	13,379	Errata for "SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model"	2024	VLDB
3	12,352	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB
4	9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS
5	11,826	Hunting Multiple Bumps in Graphs	2020	VLDB
6	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
7	1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD
8	7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS
9	6,164	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS
10	1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB