The Expressive Power of Semijoin Queries

Title: The Expressive Power of Semijoin Queries

Research Question: Can semijoin queries be used to express a wide range of complex queries in database systems?

Methodology: The researchers compared the expressive power of semijoin queries with the guarded fragment of first-order logic, a similar but logically distinct system. They used an Ehrenfeucht-Fraiss´ e game, a method for characterizing the discerning power of systems, to compare the two.

Results: The researchers found that when only equalities are allowed in semijoin conditions, the semijoin algebra has essentially the same expressive power as the guarded fragment. However, when nonequalities or other predicates are allowed, the semijoin algebra becomes more powerful. They were able to use the Ehrenfeucht-Fraiss´ e game to show that certain queries are not expressible in the semijoin algebra.

Implications: These findings have implications for the design and implementation of database query processing systems. Understanding the expressive power of semijoin queries can help developers determine when and how to use semijoin operations in their systems. It can also inform the development of more efficient query processing algorithms.

Link to Article: https://arxiv.org/abs/0308014v1 Authors: arXiv ID: 0308014v1