Optimal detection of query injectivity
DOI:
https://doi.org/10.7146/dpb.v19i311.6702Resumé
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.
Downloads
Publiceret
Citation/Eksport
Nummer
Sektion
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.