Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/11849
Title: Relational completeness of query languages for annotated databases
Authors: GEERTS, Floris 
VAN DEN BUSSCHE, Jan 
Issue Date: 2011
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Source: JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 77(3). p. 491-504
Abstract: Annotated relational databases can be queried either by simply making the annotations explicitly available along the ordinary data, or by adapting the standard query operators so that they have an implicit effect also on the annotations. We compare the expressive power of these two approaches. As a formal model for the implicit approach we propose the color algebra, an adaptation of the relational algebra to deal with the annotations. We show that the color algebra is relationally complete: it is equivalent to the relational algebra on the explicit annotations. Our result extends a similar completeness result established for the query algebra of the MONDRIAN annotation system, from unions of conjunctive queries to the full relational algebra. We also show that the color algebra is nonredundant: no operator can be expressed in terms of the other operators. We also present a generalization of the color algebra that is relationally complete in the presence of built-in predicates on the annotations. (C) 2010 Elsevier Inc. All rights reserved.
Notes: [Geerts, Floris] Univ Edinburgh, Edinburgh EH8 9YL, Midlothian, Scotland. [Van den Bussche, Jan] Transnct Univ Limburg, Hasselt Univ, Hasselt, Belgium.
Keywords: Annotated relational databases; Expressive power; Query languages
Document URI: http://hdl.handle.net/1942/11849
ISSN: 0022-0000
e-ISSN: 1090-2724
DOI: 10.1016/j.jcss.2010.04.007
ISI #: 000288474800004
Category: A1
Type: Journal Contribution
Validations: ecoom 2012
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
color-journal.pdfPreprint299.38 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

3
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

2
checked on May 21, 2022

Page view(s)

132
checked on May 20, 2022

Download(s)

246
checked on May 20, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.