Open AccessOptimal detection of query injectivity
Author(s) -
Michael I. Schwartzbach,
Kim S. Larsen
Publication year - 2002
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v19i311.6702
Subject(s) - unary operation , tuple , mathematics , characterization (materials science) , infimum and supremum , relation (database) , discrete mathematics , relational database , function (biology) , computer science , algorithm , data mining , materials science , nanotechnology , evolutionary biology , biology
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.