Allen Van Gelder
Abstract
Not all queries in relational calculus can be answered sensibly when disjunction, negation, and universal quantification are allowed. The class of relation calculus queries or formulas that have sensible answers is called the domain independent class which is known to be undecidable. Subsequent research has focused on identifying large decidable subclasses of domain independent formulas. In this paper we investigate the properties of two such classes: the evaluable formulas and the allowed formulas. Although both classes have been defined before, we give simplified definitions, present short proofs of their main properties, and describe a method to incorporate equality.
Although evaluable queries have sensible answers, it is not straightforward to compute them efficiently or correctly. We introduce relational algebra normal form for formulas from which form the correct translation into relational algebra is trivial. We give algorithms to transform an evaluable formula into an equivalent allowed formula and from there into relational algebra normal form. Our algorithms avoid use of the so-called Dom relation, consisting of all constants appearing in the database or the query.
Finally, we describe a restriction under which every domain independent formula is evaluable and argue that the class of evaluable formulas is the largest decidable subclass of the domain independent formulas that can be efficiently recognized.
- 1 ACKERMANN, W. Solvable Cases of the Decision Problem. North-Holland, Amsterdam, 1968.Google Scholar
- 2 AYLAMAZAN, A. K., GIC~ULA, M. M., S'roLBusHKIN, A. P., AND SCHWARTZ, G.F. Reduction of the relational model with infinite domains to the finite domain case. In Proceedings of USSR Academy of Science. 286, 2 (1986).Google Scholar
- 3 BEERI, C., NAQVI, S , RAMAKRISHNAN, R., SHMUELI, O., AND TSUR, S. Sets and negation m a logic database language (LDL1). In 6th ACM Symposium on Principles of Database Systems. 1987, 21-37. Google ScholarDigital Library
- 4 CODD, E. F Relational completeness of data base sublanguages In Data Base Systems. R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972, 65-98.Google Scholar
- 5 DECKER H Integrity enforcement in deductive databases. In 1st International Conference on Expert Database Systems. 1986, 271 285.Google Scholar
- 6 DEMOLOMBE, R. Syntactical characterization of a subset of domain independent formulas. Tech. Rep. ONERA-CERT, 1982.Google Scholar
- 7 DERSHOW~TZ, N AND MANNA Z. Proving termination with multiset orderings Commun. ACM. 22, 8 (1979), 465-476. Google ScholarDigital Library
- 8 DIPAOLA, R.A. The recurs~ve unsolvability of the decision problem for the class of definite formulas. J. ACM. 16, 2 (1969), 324 324. Google ScholarDigital Library
- 9 FAGIN, R. Horn clauses and database dependencies J. ACM 29, 4 (1982), 952-985 Google ScholarDigital Library
- 10 HALL, P., HITCHCOCK, P, AND TODD, S An algebra of relations for machine computation. In ACM Symposium on Principles of Programming Languages 1975, 225 232. Google ScholarDigital Library
- 11 KIFER, M. On safety, domain independence, and capturability of database queries. In Third International Conference on Data and Knowledge Bases (Jerusalem, 1988).Google ScholarCross Ref
- 12 KU~NS, J L. Answering questions by computer: A logical study. Tech. Rep. RM-5428-PR, Rand Corp., 1967.Google Scholar
- 13 KUPER, G M Logic programming with sets. In 6th ACM Symposium on Pnnaples of Database Systems 1987, 11-20 Google ScholarDigital Library
- 14 LLOYD, J W., AND TOPOR, R. W Making Prolog more expressive. J. Logzc Program. 1, 3 (1984), 225-240.Google ScholarCross Ref
- 15 MAIER, D The Them'y of Relatzonal Databases Computer Science Press, Rockville, Md., 1983. Google ScholarDigital Library
- 16 MAKOWS~Y, J. A. Characterizing data base dependencies. In 8th Colloquium on Automata, Languages and Programmzng Springer Verlag, New York, 1981 Google ScholarDigital Library
- 17 MANNA, Z. Mathematical Theory of Computation. McGraw-Hill, New York, 1974. Google ScholarDigital Library
- 18 MORRIS, K., ULLMAN, J. D, AND VAN GELDER, A. Design overwew of the Nail! system. In Third Internatmnal Conference on Logic Programming. 1986, 554-568. Google ScholarDigital Library
- 19 NAQVI, S., AND TSUR, S. A Logic Language for Data and Knowledge Bases. Computer Science Press, Rockville Md., 1988. Google ScholarDigital Library
- 20 NICOLAS, J. M Logic for improving integrity checking in relational databases Acta Inf. 18, 3 (1982), 227-253Google Scholar
- 21 NICOLAS, J M., AND DEMOLOMBE, R. On the stability of relational queries. Tech. Rep. ONERA-CERT, 1982.Google Scholar
- 22 OZSO~OGLU, G, AND WAN% H. On set comparison operators, safety, and QBE. Tech. Rep Case Western Reserve Umv., Cleveland, Oh., 1987.Google Scholar
- 23 ToPoR, R Domain independent formulas and databases. Theor. Comput. Scz. 52, 3 (1987), 281-307. Google ScholarDigital Library
- 24 TsuR, S., AND ZANIOLO, C LDL: a logic-based data-language. In Proceedings of the 12th Internatzonal Conference on Very Large Data Bases. 1986, 33 41. See also MCC rep DB-150-85. Google ScholarDigital Library
- 25 ULLMAN, J. D Prtnciples of Database and Knowledge-Base Systems. Vol. 1. Computer Science Press, Rockville, Md, 1988. Google ScholarDigital Library
- 26 ULLMAN, J.D. Principles of Database Systems. Computer Science Press, Rockville, Md., 1980. (Revised ed. 1982). Google ScholarDigital Library
- 27 VAN GELDER, A, AND TOPOR, R W. Safety and correct translation of relational calculus formulas. In 6th ACM Symposium on Principles of Database Systems. 1987, 313-327. Google ScholarDigital Library
- 28 VARm, M. The decision problem for database dependencies. Inf. Process. Lett. 12, 5 (1981), 251-254.Google Scholar
Index Terms
- Safety and translation of relational calculus
Recommendations
Safe Database Queries with External Functions
IDEAS '99: Proceedings of the 1999 International Symposium on Database Engineering & ApplicationsWe consider the theory of database queries with functions on the complex value data model. The notion of a syntactic criteria, called `embedded allowed', for queries which guarantee embedded domain independence, is generalized for this model. We show ...
A Relational Calculus with Set Operators, Its Safety, and Equivalent Graphical Languages
The authors propose a relational calculus (RC/S) which uses set comparison and set manipulation operators to replace universal quantifiers and negations. It is argued that compared to the Codd relational calculus (RC), RC/S queries are easier to ...
Safety and correct translation of relational calculus formulas
PODS '87: Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsNot all queries in relational calculus can be answered “sensibly” once disjunction, negation, and universal quantification are allowed. The class of relational calculus queries, or formulas, that have “sensible” answers is called the domain independent ...
Reviews
Charles William Bash
“Not all queries in relational calculus can be answered sensibly when disjunction, negation and universal quantification are allowed.” Given the growing number of intermediate query generators on the market, more and more problems will not be stated in simple terms, and methods are needed to simplify those statements so that they can be correctly solved. Even apparently simple queries such as “SELECT P.name FROM P,Q,R WHERE P.name = Q.name OR P.name = R.name ” may yield counterintuitive results using current methods. The authors state that if R is empty, both SQL and QUEL return nothing, even if matches exist between P and Q . The importance of this can be seen if we translate the request into English: “Give me a list of the parts that I have in inventory, or that are currently on order.” This paper is for those deeply involved in the process of relational calculus, not for the lay reader. The calculus is long and involved, and will not be obvious without careful study. The work is important to the evolution of database system, however, and I strongly urge those involved in this area to read the document.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments