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: h3e55cfb9c9d84ccf
Venue: SIGMOD
Year: 1981
Pagerank: 5.1677187e-05
Overall Rank: 9,393 | 37.04%
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 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,631	Processing Queries Over Generalization Hierarchies in a Multidatabase System	1983	VLDB	8.1810097e-05
8,291	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3445863e-05
10,391	DQSim: Does the Task Assignment Slow Down Your Distributed Database System?	2027	SIGMOD	4.9605343e-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,536	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD	0.00010297567

Semantically Similar Papers

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