The semijoin algebra and the guarded fragment

Thumbnail Image

Date

Authors

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 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.
11 pages, 2 figures

Keywords

Databases, Logic in Computer Science, H.2.3;F.4.1

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32228

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0407007
 http://arxiv.org/abs/cs/0407007

Collections

arXiv