Optimal detection of query injectivity

DAIMI Report Series

View Publication Info
 
 
Field Value
 
Title Optimal detection of query injectivity
 
Creator Schwartzbach, Michael I.
Larsen, Kim Skak
 
Description Most unary relational database operators can be described through functions from tuples to tuples. Injectivity of the specified function ensures that no duplicates are created in the relational result. This normally reduces the complexity of the query from O(r log r) to O(r), where r is the number of tuples in the argument relation. We consider functions obtained as terms over a general signature. The semantic properties of the operators are specified by Horn clauses generalizing functional dependencies. Relative to such specifications, we present an optimal algorithm for detecting injectivity of unary queries. The complexity of this algorithm is linear in the size of the query. It turns out that relational functional dependencies are very easily incorporated into this framework. As a further result, we provide a Horn clause characterization of the functional dependencies that can be propagated to the result relation.
 
Publisher Aarhus University
 
Contributor
 
Date 2002-04-01
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Peer-reviewed Article
 
Format application/pdf
 
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6702
10.7146/dpb.v19i311.6702
 
Source DAIMI Report Series; No 311 (1990): PB-311 Optimal detection of query injectivity
DAIMI Report Series; No 311 (1990): PB-311 Optimal detection of query injectivity
2245-9316
0105-8517
 
Language eng
 
Relation http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6702/5819
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library