Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems

Summary: Extends semijoin planning to bus/loop networks with broadcast, accounting for local processing costs and capacity in a minimum response-time schedule. Shows NP-hardness for general tree queries even on 1-bus and many m-bus cases; polynomial-time only for simple 1-bus queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2217
Venue: SIGMOD
Year: 1981
Pagerank: 5.183257e-05
Overall Rank: 9,987 | 31.49%
DOI: 10.1145/582318.582344

Incoming Non-self Citations Over Time

Authors

1. Mohamed G. Gouda (University of Texas)
2. Umeshwar Dayal (University of Texas)

BibTeX Citation

@inproceedings{gouda_sigmod81,
        title = {{OPTIMAL SEMIJOIN SCHEDULES FOR QUERY PROCESSING IN LOCAL DISTRIBUTED DATABASE SYSTEMS}},
        author = {Gouda, Mohamed G. and Dayal, Umeshwar},
        series = {{SIGMOD} '81},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582318.582344},
        url = {https://dl.acm.org/doi/10.1145/582318.582344},
        year = {1981}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,577	Processing Queries Over Generalization Hierarchies in a Multidatabase System	1983	VLDB	8.3947293e-05
8,721	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3772617e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 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,510	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD	0.00010539169

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,902	Reducing Multidatabase Query Response Time By Tree Balancing	1995	SIGMOD
2	1,998	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS
3	1,207	Communication Steps for Parallel Query Processing	2013	PODS
4	7,857	Semi-Join Algorithms For Multiprocessor Systems	1982	SIGMOD
5	7,995	Optimizing Star Queries in a Distributed Database System	1984	VLDB
6	1,510	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD
7	13,231	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS
8	1,651	On the Design of a Query Processing Strategy in a Distributed Database Environment	1983	SIGMOD
9	5,069	Query Processing For Distributed Databases Using Generalized Semi-Joins	1982	SIGMOD
10	1,772	A Heuristic Approach to Distributed Query Processing	1982	VLDB