Safety, domain independence and translation of complex value database queries. (English) Zbl 1183.68249

Summary: This paper considers the theory of database queries on the complex value data model with external functions. Motivated by concerns regarding query evaluation, we first identify recursive sets of formulas, called embedded allowed, which is a class with desirable properties of “reasonable” queries.
We then show that all embedded allowed calculus (or fix-point) queries are domain independent and continuous. An algorithm for translating embedded allowed queries into equivalent algebraic expressions as a basis for evaluating safe queries in all calculus-based query classes has been developed.
Finally, we discuss the topic of “domain independent query programs”, compare the expressive power of the various complex value query languages and their embedded allowed versions, and discuss the relationship between safety, embedded allowed, and domain independence in the various calculus-based queries.


68P15 Database theory
Full Text: DOI


[1] Abiteboul, S.; Beeri, C., The power of languages for the manipulation of complex values, The very large data bases journal, 4, 727-794, (1995)
[2] Abiteboul, S.; Grumbach, S., A rule-based language with functions and sets, ACM transactions on database systems, 16, 1, 1-30, (1991)
[3] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of databases, (1995), Addison-Wesley
[4] Almendros-Jimenez, J.M.; Becerra-Teron, A., A safe relational calculus for functional logic deductive databases, Electronic notes on theoretical computer science, 86, 168-204, (2003) · Zbl 1270.68101
[5] Avron, A., Constructibility and decidability versus domain independence and absoluteness, Theoretical computer science, (2008) · Zbl 1134.03025
[6] Avron, A., Safety signatures for first-order languages and their applications, (), 37-58 · Zbl 1092.03015
[7] Badia, A., Safety, domain independence and generalized quantification, Data and knowledge engineering, 38, 147-172, (2001) · Zbl 0969.68056
[8] Beeri, C.; Milo, T., Comparison of functional and predicative query paradigms, Journal of computer and system sciences, 54, 3-33, (1997) · Zbl 0864.68026
[9] C. Beeri, S. Naqvi, R. Ramakrishnan, O. Shmueli, S. Tsur, Sets and negation in a logic database language, in: Proceedings of ACM Symposium on Principles of Database Systems, 1987, pp. 21-37.
[10] V. Breazu-Tannen, P. Buneman, L. Wong, Naturally embedded query languages, in: Proceedings of 4th International Conference on Database Theory, Berlin, Germany, 1992, pp. 140-154.
[11] Codd, E.F., Relational completeness of data base sublanguages, (), 65-98
[12] Demolombe, R., Syntactical characterization of a subset of domain-independent formulas, Journal of ACM, 39, 1, 71-94, (1992) · Zbl 0799.68061
[13] M. Escobar-Molano, R. Hull, D. Jacobs, Safety and translation of calculus queries with scalar functions, in: Proceedings of ACM Symposium on Principles of Database Systems, 1993, pp. 253-264.
[14] S. Grumbach, V. Vianu, Expressiveness and complexity of restricted languages for complex objects, in: Proceedings of 3rd International Workshop on Database Programming Languages, 1991, pp. 111-122.
[15] Grumbach, S.; Vianu, V., Tractable query languages for complex object databases, Journal of computer and system sciences, 51, 2, 149-167, (1995) · Zbl 0831.68038
[16] Hull, R.; Su, J., Domain independence and the relational calculus, Acta informatica, 31, 513-524, (1994) · Zbl 0818.68067
[17] G. Jaeschke, H.-J. Schek, Remarks on the algebra on non-first normal form relations, in: ACM Symposium on Principles of Database Systems, 1982, pp. 124-138.
[18] Kuper, G., Logic programming with sets, Journal of computer and system sciences, 41, 1, 44-64, (1990) · Zbl 0694.68013
[19] H.-C. Liu, J. Yu, Safe database queries with external functions, in: Proceedings of International Database Engineering and Applications Symposium, Montreal, Canada, 1999, pp. 260-269.
[20] Liu, H.-C.; Yu, J., Algebraic equivalences of nested relational operators, Information systems, 30, 3, 167-204, (2005)
[21] Nicolas, J.M., Logic for improving integrity checking in relational data bases, Acta informatica, 18, 227-253, (1982) · Zbl 0478.68096
[22] R. Ramakrishnan, F. Bancilhon, A. Silberschatz, Safety of recursive horn clauses with infinite relations (extended abstract), in: Proceedings of ACM Symposium on Principles of Database Systems, 1987, pp. 328-339.
[23] D. Suciu, Domain-independent queries on databases with external functions, in: Proceedings of International Conference on Database Theory, Prague, Czech Republic, 1995, pp. 177-190.
[24] Suciu, D., Domain-independent queries on databases with external functions, Theoretical computer science, 190, 2, 279-315, (1998) · Zbl 0893.68053
[25] Taniar, D.; Khaw, H.Y.; Tjioe, H.C.; Pardede, E., The use of hints in sql-nested query optimization, Information sciences, 177, 12, 2493-2521, (2007)
[26] Topor, R., Domain independent formulas and databases, Theoretical computer science, 52, 3, 281-307, (1987) · Zbl 0627.68077
[27] R. Topor, Safe database queries with arithmetic relations, in: Proceedings of 14th Australian Computer Science Conference, Sydney, Australia, 1991, pp. 1-13.
[28] Ullman, J., Principles of database and knowledge-base systems, vol. 1, (1988), Computer Science Press
[29] Van Gelder, A.; Topor, R., Safety and translation of relational calculus queries, ACM transactions on database systems, 16, 2, 235-278, (1991)
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.