Review - Using Semi-Joins to Solve Relational Queries.

Z. Meral Özsoyoglu: Review - Using Semi-Joins to Solve Relational Queries. ACM SIGMOD Digital Review 1: (1999) BibTeX

Review

This paper had a major impact on my research. When I first read Bernstein and Chiu's paper as a technical report in 1979, I was a graduate student at the University of Alberta, and my research advisor had just moved to Chicago. At the time, I was trying to find a thesis topic in query optimization, and had read several papers in query processing and distributed databases. I had noticed that some queries are inherently more costly to process than some others, but didn't quite figure out how to formalize. Unlike other papers that were based on heuristics, Bernstein and Chiu used a very novel approach: they classified queries as tree and cyclic queries, introduced the semijoin operator, and showed that while tree queries can always be answered by semijoins, cyclic queries may not be. They also gave an algorithm to determine whether a query is a tree query or not. I was surprised to see that this algorithm was not applicable to some example queries that I had identified earlier as ``typical'' while trying to come up with a query optimization scheme. This motivated me to start working on a generalized tree query membership algorithm and I ended up doing my thesis on distibuted query optimization using semi-joins. Our tree query membership algorithm (co-authored by my PhD advisor C. Yu) was published in the same year in IEEE COMPSAC'79 conference. (Bernstein and Chiu's algorithm was limited to at most one join attribute between any two relations, i.e. semijoins involving single domains). This was my first paper as a graduate student and was a starting point for my research. This tree query membership algorithm was later called the ``GYO Reduction'' in the literature. Bernstein and Chiu's novel approach to query processing and semijoin reductions influenced my research, and the research of many others in the area of query optimization. Both semijoins and the classification of tree and cyclic queries are still used today in query optimization almost 20 years after they have been introduced by Bernstein and Chiu.

References

[1]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX

BibTeX

Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]