Domain-independent queries on databases with external functions.

*(English)*Zbl 0893.68053Summary: We study queries over databases with external functions, from a language-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 databases with external functions, which extends naturally the notion of generic queries on relational databases without external functions. In contrast to previous such notions, ours can also be applied to queries expressed in query languages with iterations. Next, we propose two natural notions of computability for queries over databases with external functions, and prove that they are equivalent, under reasonable assumptions. Thus, our definition of computability is robust. Finally, based on this equivalence result, we give examples of complete query languages with external functions. A byproduct of the equivalence result is the fact that relational machines are complete on nested relations: they are known not to be complete on flat relations.

##### MSC:

68P15 | Database theory |

PDF
BibTeX
XML
Cite

\textit{D. Suciu}, Theor. Comput. Sci. 190, No. 2, 279--315 (1998; Zbl 0893.68053)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Abiteboul, S.; Beeri, C., On the power of languages for the manipulation of complex objects, (), Also available as |

[2] | Abiteboul, S.; Kanellakis, P., Object identity as a query language primitive, (), 159-173 |

[3] | Abiteboul, S.; Papadimitriou, C.H.; Vianu, V., The power of reflective relational machines, (), 230-240 |

[4] | Abiteboul, S.; Vardi, M.; Vianu, V., Fixpoint logics, relational machines, and computational complexity, () · Zbl 0883.68070 |

[5] | Abiteboul, S.; Vianu, V., Generic computation and its complexity, () |

[6] | Bellantoni, S., Comments on two notions of higher type computability, (1994), Manuscript available from sjb@cs.toronto.edu. |

[7] | Breazu-Tannen, V.; Buneman, P.; Wong, L., Naturally embedded query languages, (), 140-154, Available as UPenn Tech. Report MS-CIS-92-47 |

[8] | Breazu-Tannen, V.; Subrahmanyam, R., Logical and computational aspects of programming with sets/bags/lists, (), 60-75 · Zbl 0769.68080 |

[9] | Buneman, P.; Naqvi, S.; Tannen, V.; Wong, L., Principles of programming with collection types, Theoret. comput. sci., 149, 3-48, (1995) · Zbl 0874.68092 |

[10] | Chandra, A.; Harel, D., Computable queries for relational databases, J. comput. system sci., 21, 2, 156-178, (1980) · Zbl 0456.68128 |

[11] | Constable, R.L., Type two computational complexity, (), 108-122 |

[12] | Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), MIT Press Cambridge, MA · Zbl 1158.68538 |

[13] | Curien, P.L., Categorical combinators, sequential algorithms and functional programming, (1986), Pitman London · Zbl 0643.68004 |

[14] | Deux, O., The story of O2, IEEE trans. knowledge and data eng., 2, 1, 91-108, (1990) |

[15] | Digital Equipment Corporation, ISO-ANSI working draft — database language SQL (SQL3), (August 1993) |

[16] | Escobar-Molano, M.; Hull, R.; Jacobs, D., Safety and translation of calculus queries with scalar functions, (), 253-264 |

[17] | Gratzer, G., Universal algebra, (1980), Springer New York · Zbl 0182.34201 |

[18] | Grumbach, S.; Vianu, Victor, Expressiveness and complexity of restricted languages for complex objects, (), 191-202 |

[19] | Gunter, C.A., Semantics of programming languages: structures and techniques. foundations of computing, (1992), MIT Press Cambridge, MA |

[20] | Gyssens, M.; Van Gucht, D., A comparison between algebraic query languages for flat and nested databases, Theoret. comput. sci., 87, 263-286, (1991) · Zbl 0743.68053 |

[21] | Hartley, R., Theory of recursive functions and effective computability, (1987), MIT Press Cambridge, MA |

[22] | Hirst, T.; Harel, D., Completeness results for recursive data bases, (), 244-252 |

[23] | Hull, R.; Su, J., Untyped sets, inventions, and computable queries, (), 347-360 |

[24] | Kapron, B.; Cook, S., A new characteriztion of Mehlhorn’s polynomial time functionals, (), 342-347 |

[25] | Paredaens, J.; Van Gucht, D., Converting nested relational algebra expressions into flat algebra expressions, ACM trans. database systems, 17, 1, 65-93, (1992) |

[26] | Plotkin, G.D., Post-graduate lecture notes in advanced domain theory, (1981), Department of Computer Science, University of Edinburgh, available by email from: kondoh@harl.hitachi.co.jp. |

[27] | Suciu, D., Fixpoints and bounded fixpoints for complex objects, (), 263-281, See also |

[28] | Suciu, D.; Wong, L., On two forms of structural recursion, (January 1995) |

[29] | Suciu, D.; Breazu-Tannen, V., A query language for NC, (), 167-178, See also |

[30] | Topor, R.W., Domain-independent formulas and databases, Theoret. comput. sci., 52, 281-306, (1987) · Zbl 0627.68077 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.