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
Date 2002-04-01
Type info:eu-repo/semantics/article
Peer-reviewed Article
Format application/pdf
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/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
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


Copyright © 2015-2018 Simon Fraser University Library