Evaluation of queries in independent database schemes
Yehoshua Sagiv · Journal of the ACM · 1991
A simple characterization of independent database schemes is proved. An algorithm is given for translating a tableau T , posed as a query on a representative instance, to a union of tableaux that is equivalent to T , but can be applied directly to database relations. The algorithm may take exponential time (in the size of T and the database scheme), and it is applicable only to independent database schemes. If T is a just a projection of a representative instance, then the algorithm has a simpler form (which is still exponential in the worst case) and is polynomial in some cases.