Abstract: Chandra and Merlin's work greatly influenced my thinking and research direction long before I ever actually read the paper. They were the first to consider the problem of query equivalence for conjunctive queries (i.e., determining whether two queries return the same set of answers for any state of the database). They aimed to contrast optimizations that considered the global structure of the query with local optimization such as join ordering and access path selection. Their study of query containment and equivalence problems for different classes of queries generated a long and fruitful line of research. Until a few years ago query containment had been mostly a topic of conversation that enhanced bonding among fellow PODS aficionados. More recently, insights and results from query containment have helped solve many practical problems (e.g., semantic data caching, maintenance of physical data independence, integrity constraint violation, data integration and answering queries using views). As more and more applications require that we reason about data and views, query containment and equivalence will play a even more significant role.

Another reason this paper and line of work appealed to me is that they answered questions I felt should have been available in the Artificial Intelligence literature. Query containment algorithms are essentially inference algorithms over finite models for specific forms of logical sentences. As such, they are key to the field of Knowledge Representation, much of which strives to represent the world in some form of logic. However, with the exception of work on Description Logics, AI researchers have overlooked the opportunity to discover these classes of sentences for which sound and complete reasoning is possible. Hence, I believe that query containment algorithms will also play a greater role in AI applications, such as knowledge-base inference, planning and knowledge-base verification.