On the expressive power of semijoin queries
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
The semijoin algebra is the variant of the relational algebra obtained by replacing the join operator by the semijoin operator. We provide an Ehrenfeucht-Fraissé game, characterizing the discerning power of the semijoin algebra. This game gives a method for showing that queries are not expressible in the semijoin algebra.
9 pages, to appear in Information Processing Letters; added results that more clearly delineate the expressive power of SA, added a section that discusses the impact of order on the expressive power of SA, deemphasized the discussion on the relationship with GF
9 pages, to appear in Information Processing Letters; added results that more clearly delineate the expressive power of SA, added a section that discusses the impact of order on the expressive power of SA, deemphasized the discussion on the relationship with GF