The semijoin algebra and the guarded fragment

(2) Institute of Informatics; Belgium; Diepenbeek; Dirk Leinders (1); Jan Van den Bussche (1) ((1) Limburgs Universitair Centrum; Jerzy Tyszkiewicz (2); Poland); Warsaw; Warsaw University

arxiv: cs/0407007 · v1 · submitted 2004-07-02 · 💻 cs.DB · cs.LO

The semijoin algebra and the guarded fragment

Dirk Leinders (1) , Jerzy Tyszkiewicz (2) , Jan Van den Bussche (1) ((1) Limburgs Universitair Centrum , Diepenbeek , Belgium , (2) Institute of Informatics , Warsaw University , Warsaw

show 1 more author

Poland)

This is my paper

classification 💻 cs.DB cs.LO

keywords algebrasemijoinfragmentgameguardedoperatorcertaincharacterizing

0 comments

read the original abstract

The semijoin algebra is the variant of the relational algebra obtained by replacing the join operator by the semijoin operator. We discuss some interesting connections between the semijoin algebra and the guarded fragment of first-order logic. We also provide an Ehrenfeucht-Fraisse game, characterizing the discerning power of the semijoin algebra. This game gives a method for showing that certain queries are not expressible in the semijoin algebra.

This paper has not been read by Pith yet.

The semijoin algebra and the guarded fragment

discussion (0)