Optimal detection of query injectivity

  • Michael I. Schwartzbach
  • Kim Skak Larsen


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.

How to Cite
Schwartzbach, M., & Larsen, K. (2002). Optimal detection of query injectivity. DAIMI Report Series, 19(311). https://doi.org/10.7146/dpb.v19i311.6702