Power of Natural Semijoins
Philip A. Bernstein, Nathan Goodman · SIAM Journal on Computing · 1981
A semijoin is a relational operator that is used to reduce the cost of processing queries in the SDD-1 distributed database system, the RAP database machine, and similar systems. Semijoin is used in these systems as part of a query pre-processing phase; its function is to “reduce” the database by delimiting those portions of the database that contain data relevant to the query. For some queries, there exist sequences of semijoins that “fully reduce” the database; those sequences delimit the exact portions of the database needed to answer the query in the sense that if any less data were delimited then the query would produce a different answer. Such sequences are called full reducers. This paper characterizes the queries for which full reducers exist and presents an efficient algorithm for constructing full reducers where they do exist. This paper extends the results of Bernstein and Chiu [J. Assoc. Comput. Mach., 28 (1981), pp. 25–40] by considering a more powerful semijoin operator. We consider “natural” semijoins instead of the “single attribute” semijoins of Bernstein and Chiu. A novel feature of our treatment is an extensive use of the “tableau methodology” of Aho, Sagiv and Ullman [SIAM J. Comput., 8 (1979), pp. 218–246] to prove the nonexistence of full reducers for a broad class of queries.