Computing queries from derived relations

Assume that a set of derived relations are available in stored form. Given a query (or subquery), can it be computed from the derived rela- tions and, if so, how? Variants of this problem arise in several areas of query processing. Relation fragments stored at a site in a distributed database system, data- base snapshots, and intermediate results obtained dur- ing the processing of a query are all examples of stored, derived relations. In this paper we give neces- sary and sufficient conditions for when a query is com- putable from a single derived relation. It is assumed that both the query and the derived relation are defined by PSJ-expressions, that is, relational algebra expressions involving only projections, selections, and joins, in any combination. The solution is constructive: not only does it tell whether the query is computable or not, but it also shows how to compute it.