DOMAIN-INDEPENDENT QUERIES ON DATABASES WITH EXTERNAL FUNCTIONS

We study queries over databases with external functions, from a langua ge-independent perspective. The input and output types of the external functions can be atomic values, flat relations, nested relations, etc . We propose a new notion of data-independence for queries on database s with external functions, which extends naturally the notion of gener ic queries on relational databases without external functions. In cont rast to previous such notions, ours can also be applied to queries exp ressed in query languages with iterations. Next, we propose two natura l notions of computability for queries over databases with external fu nctions, and prove that they are equivalent, under reasonable assumpti ons. Thus, our definition of computability is robust. Finally, based o n this equivalence result, we give examples of complete query language s with external functions. A byproduct of the equivalence result is th e fact that Relational Machines (Abiteboul and V. Vianu, 1991; Abitebo ul et al., 1992) are complete on nested relations: they are known not to be complete on flat relations.