Reducing Multidatabase Query Response Time By Tree Balancing

Summary: Two-phase optimization for multidatabase queries: build an optimal left-deep join tree, then balance with simple transformations for lower latency. Balancing lowers response time and resource use for sort-merge/hash-join plans, with low overhead. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h57c19aef9f25e29e
Venue: SIGMOD
Year: 1995
Pagerank: 6.316759e-05
Overall Rank: 5,008 | 66.33%
DOI: 10.1145/223784.223846

Incoming Non-self Citations Over Time

Authors

1. Weimin Du (Hewlett Packard Enterprise)
2. Ming-Chien Shan (Hewlett Packard Enterprise)
3. Umeshwar Dayal (Hewlett Packard Enterprise)

BibTeX Citation

@inproceedings{du_sigmod95,
        title = {{Reducing Multidatabase Query Response Time By Tree Balancing}},
        author = {Du, Weimin and Shan, Ming-Chien and Dayal, Umeshwar},
        series = {{SIGMOD} '95},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/223784.223846},
        url = {https://dl.acm.org/doi/10.1145/223784.223846},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
424	Cost-based Query Scrambling for Initial Delays	1998	SIGMOD	0.0001848836
4,052	Of Snowstorms and Bushy Trees	2014	VLDB	6.8283077e-05
4,773	Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System	1999	VLDB	6.4212044e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023947656
186	Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases	1991	VLDB	0.00025951043
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
844	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013533208
1,623	Query Optimization in Heterogeneous DBMS	1992	VLDB	0.00010045919
2,623	Processing Queries Over Generalization Hierarchies in a Multidatabase System	1983	VLDB	8.2114388e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,015	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
2	3,775	Parallelizing Query Optimization	2008	VLDB
3	143	Optimization of Nonrecursive Queries	1986	VLDB
4	1,736	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB
5	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	13,521	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS
7	446	Query Optimization for Parallel Execution	1992	SIGMOD
8	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
9	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	920	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB