Safe database queries with external functions

Considers the theory of database queries with functions in the complex-value data model. The notion of a syntactic criterion, called “embedded allowed”, for queries which guarantee embedded domain independence, is generalized for this model. We show that all “embedded allowed” calculus (or fixpoint) queries are external function domain-independent and continuous. We also develop an algorithm for translating “embedded allowed” queries into equivalent algebraic expressions as a basis for evaluating safe queries in all calculus-based query classes. We then compare the expressive power of various complex-value query languages extended with functions and certain restricted versions of them. If we assume polynomial time (space) complexity of external functions and type usage by the database, such as density, then strongly “embedded allowed” inflationary (partial) fixpoint queries precisely express QPTIME (QPSPACE). Finally, we show the relationship between properties such as embedded domain independence, finiteness and “embedded allowed” in various calculus-based query languages