Using Semi-Joins to Solve Relational Queries.

@article{DBLP:journals/jacm/BernsteinC81,
  author    = {Philip A. Bernstein and
               Dah-Ming W. Chiu},
  title     = {Using Semi-Joins to Solve Relational Queries},
  journal   = {J. ACM},
  volume    = {28},
  number    = {1},
  year      = {1981},
  pages     = {25-40},
  ee        = {db/journals/jacm/BernsteinC81.html, http://doi.acm.org/10.1145/322234.322238},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An5-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition

Referenced by

1. Z. Meral Özsoyoglu: Review - Using Semi-Joins to Solve Relational Queries. ACM SIGMOD Digital Review 1: (1999)
2. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
3. Jia Liang Han: Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations. VLDB J. 7(1): 1-11(1998)
4. Richard T. Snodgrass, Laura M. Haas, Alberto O. Mendelzon, Z. Meral Özsoyoglu, Jan Paredaens, Krithi Ramamritham, Nick Roussopoulos, Jennifer Widom, Philip S. Yu: Reminiscences on Influential Papers. SIGMOD Record 27(4): 81-85(1998)
5. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: On Applying Hash Filters to Improving the Execution of Multi-Join Queries. VLDB J. 6(2): 121-131(1997)
6. Chihping Wang, Ming-Syan Chen: On the Complexity of Distributed Query Optimization. IEEE Trans. Knowl. Data Eng. 8(4): 650-662(1996)
7. Chengwen Liu, Hao Chen: A Hash Partition Strategy for Distributed Query Processing. EDBT 1996: 373-387
8. Bojan Groselj, Qutaibah M. Malluhi: Combinatorial Optimization of Distributed Queries. IEEE Trans. Knowl. Data Eng. 7(6): 915-927(1995)
9. Zhe Li, Kenneth A. Ross: PERF Join: An Alternative to Two-way Semijoin and Bloomjoin. CIKM 1995: 137-144
10. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
11. Ming-Syan Chen, Philip S. Yu: A Graph Theoretical Approach to Determine a Join Reducer Sequence in Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 6(1): 152-165(1994)
12. Peter Scheuermann, Eugene Inseok Chong: Role-based Query Processing in Multidatabase Systems. EDBT 1994: 95-108
13. Yehoshua Sagiv, Oded Shmueli: Solving Queries by Tree Projections. ACM Trans. Database Syst. 18(3): 487-511(1993)
14. P. E. Drenick, E. J. Smith: Stochastic Query Optimization in Distributed Databases. ACM Trans. Database Syst. 18(2): 262-288(1993)
15. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
16. Ming-Syan Chen, Philip S. Yu: Combining Join and Semi-Join Operations for Distributed Query Processing. IEEE Trans. Knowl. Data Eng. 5(3): 534-542(1993)
17. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: Applying Hash Filters to Improving the Execution of Bushy Trees. VLDB 1993: 505-516
18. Rafael Alonso, Henry F. Korth: Database System Issues in Nomadic Computing. SIGMOD Conference 1993: 388-392
19. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
20. Nick Roussopoulos, Hyunchul Kang: A Pipeline N-way Join Algorithm Based on the 2-way Semijoin Program. IEEE Trans. Knowl. Data Eng. 3(4): 486-495(1991)
21. Chihping Wang, Victor O. K. Li, Arbee L. P. Chen: Distributed Query Optimization by One-Shot Fixed-Precision Semi-Join Execution. ICDE 1991: 756-763
22. Ming-Syan Chen, Philip S. Yu: Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing. ICDE 1991: 50-58
23. Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459
24. M. Seetha Lakshmi, Philip S. Yu: Effectiveness of Parallel Joins. IEEE Trans. Knowl. Data Eng. 2(4): 410-424(1990)
25. Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
26. Dan E. Willard: Quasilinear Algorithms for Processing Relational Calculus Expressions. PODS 1990: 243-257
27. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
28. Hyuck Yoo, Stéphane Lafortune: An Intelligent Search Method for Query Optimization by Semijoins. IEEE Trans. Knowl. Data Eng. 1(2): 226-237(1989)
29. William Perrizo, Jonathan Y. Y. Lin, Wherly Hoffman: Algorithms for Distributed Query Processing in Broadcast Local Area Networks. IEEE Trans. Knowl. Data Eng. 1(2): 215-225(1989)
30. Y. C. Tay: Attribute Agreement. PODS 1989: 110-119
31. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
32. Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27
33. Don S. Batory: Concepts for a Database System Compiler. PODS 1988: 184-192
34. M. Driouche, Y. Gicquel, Brigitte Kerhervé, G. Le Gac, Yann Lepetit, G. Nicaud: Sabrina-RT, A Distributed DBMS for Telecommunications. EDBT 1988: 594-599
35. Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
36. Weining Zhang, Clement T. Yu: A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule. SIGMOD Conference 1987: 345-356
37. Hyunchul Kang, Nick Roussopoulos: Using 2-way Semijoins in Distributed Query Processing. ICDE 1987: 644-651
38. Arie Segev: Optimization of Join Operations in Horizontally Partitioned Database Systems. ACM Trans. Database Syst. 11(1): 48-80(1986)
39. Stéphane Lafortune, Eugene Wong: A State Transition Model for Distributed Query Processing. ACM Trans. Database Syst. 11(3): 294-322(1986)
40. Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159
41. Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186
42. Yehoshua Sagiv, Oded Shmueli: On Finite FD-Acyclicity. PODS 1986: 173-182
43. Yehoshua Sagiv, Oded Shmueli: The Equivalence of Solving Queries and Production Tree Projections. PODS 1986: 160-172
44. Clement T. Yu, Leszek Lilien, Keh-Chang Guh, Marjorie Templeton, David Brill, Arbee L. P. Chen: Adaptive Techniques for Distributed Query Optimization. ICDE 1986: 86-93
45. C. P. Wang, Victor O. K. Li: The Relation-Partitioning Approach to Processing Star Queries in Distributed Databases. ICDE 1986: 21-28
46. Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304
47. Joseph A. Wald, Paul G. Sorenson: Resolving the Query Inference Problem Using Steiner Trees. ACM Trans. Database Syst. 9(3): 348-368(1984)
48. Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)
49. Hirofumi Katsuno: An Extension of Conflict-Free Multivalued Dependency Sets. ACM Trans. Database Syst. 9(2): 309-326(1984)
50. Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984)
51. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
52. Clement T. Yu, C. C. Chang: Distributed Query Processing. ACM Comput. Surv. 16(4): 399-433(1984)
53. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
54. Masatoshi Yoshikawa, Yahiko Kambayashi: Processing Inequality Queries Based on Generalized Semi-Joins. VLDB 1984: 416-428
55. Ravi Krishnamurthy, Stephen P. Morgan: Query Processing on Personal Computers: A Pragmatic Approach (Extended Abstract). VLDB 1984: 26-29
56. Arbee L. P. Chen, Victor O. K. Li: Optimizing Star Queries in a Distributed Database System. VLDB 1984: 429-438
57. Dan E. Willard: Efficient Processing of Relational Calculus Expressions Using Range Query Theory. SIGMOD Conference 1984: 164-175
58. Oded Shmueli, Alon Itai: Maintenance of Views. SIGMOD Conference 1984: 240-255
59. Z. Meral Özsoyoglu, Elarbi Choukhmane: On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries. PODS 1984: 133-142
60. Hai-Yann Hwang, Umeshwar Dayal, Mohamed G. Gouda: Using Semiouterjoins to Process Queries in Multidatabase Systems. PODS 1984: 153-162
61. Benjamin W. Wah, Yao-Nan Lien: The File-Assignment and Query-Processing Problems in Local Multiaccess Networks. ICDE 1984: 228-235
62. Giovanni Maria Sacco: Distributed Query Evaluation in Local Area Networks. ICDE 1984: 510-516
63. Ravi Krishnamurthy, Stephen P. Morgan: Distributed Query Optimization: An Engineering Approach. ICDE 1984: 220-227
64. Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983)
65. Clement T. Yu, M. K. Siu, K. Lam, C. H. Chen: File Allocation in Distributed Databases with Interaction between Files. VLDB 1983: 248-259
66. Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353
67. Clement T. Yu, C. C. Chang: On the Design of a Query Processing Strategy in a Distributed Database Environment. SIGMOD Conference 1983: 30-39
68. Yahiko Kambayashi, Masatoshi Yoshikawa: Query Processing Utilizing Dependencies and Horizontal Decomposition. SIGMOD Conference 1983: 55-67
69. Matthias Jarke, Jürgen Koch: Range Nesting: A Fast Method to Evaluate Quantified Queries. SIGMOD Conference 1983: 196-206
70. Nathan Goodman, Oded Shmueli, Y. C. Tay: GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections. PODS 1983: 267-278
71. Umeshwar Dayal: Processing Queries with Quantifiers: A Horticultural Approach. PODS 1983: 125-136
72. David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
    Contents
73. Larry Kerschberg, Peter D. Ting, S. Bing Yao: Query Optimization in Star Computer Networks. ACM Trans. Database Syst. 7(4): 678-711(1982)
74. Nathan Goodman, Oded Shmueli: Tree Queries: A Simple Class of Relational Queries. ACM Trans. Database Syst. 7(4): 653-677(1982)
75. Jo-Mei Chang: A Heuristic Approach to Distributed Query Processing. VLDB 1982: 54-61
76. Patrick Valduriez: Semi-Join Algorithms for Multiprocessor Systems. SIGMOD Conference 1982: 225-233
77. Yahiko Kambayashi, Masatoshi Yoshikawa, Shuzo Yajima: Query Processing for Distributed Databases Using Generalized Semi-Joins. SIGMOD Conference 1982: 151-160
78. Matthias Jarke, Joachim W. Schmidt: Query Processing Strategies in the PASCAL/R Relational Database Management System. SIGMOD Conference 1982: 256-264
79. Umeshwar Dayal, Nathan Goodman: Query Optimization for CODASYL Database Systems. SIGMOD Conference 1982: 138-150
80. Philip A. Bernstein, Barbara T. Blaustein: Fast Methods for Testing Quantified Relational Calculus Assertions. SIGMOD Conference 1982: 39-50
81. Nathan Goodman, Oded Shmueli: Transforming Cyclic Schemas into Trees. PODS 1982: 49-54
82. Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48
83. Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)
84. Mohamed G. Gouda, Umeshwar Dayal: Optimal Semijoin Schedules For Query Processing in Local Distributed Database Systems. SIGMOD Conference 1981: 164-175
85. Robert S. Epstein, Michael Stonebraker: Analysis of Distributed Data Base Processing Strategies. VLDB 1980: 92-101
86. D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178