A. Van Gelder
ABSTRACT
Not 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 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 man 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 evaluable formulas may be the largest decidable subclass of the domain independent formulas that can be efficiently recognized.
- Ack68.W Ackermann. Solvable Cases of the Decision Problem. North-Holland, Amsterdam, 1968Google Scholar
- Dec86.H Decker. lntegrity enforcement in deductive databases. In 1st lnt'l Conference on Expert Dalabase Systems, pages 271-285, 1986Google Scholar
- Dem82.R Demolombe. Syntactscal Characteriation of a Subset of Domain Independent Formulas. Techmcal Report, ONERA- CERT, 1982Google Scholar
- DiP69.R A DIPaola. The recurmve unsolvability of the decision problem for the class of defimte formulas. JACM, 16(2) 324-324, 1969 Google ScholarDigital Library
- Fag80.R Fagin. Horn clauses and database dependencies. In 12th Ann ACM Symp. on Threory of Computing, pages 123-134 1980 Google ScholarDigital Library
- Kuh67.J L Kuhns. Answering Questions by Computer A Logtcal Study. Technlcal Report RM-5428-PR, Rand Corp, 1967Google Scholar
- LT84.J W Lloyd and R W Topor. Making Prolog more expressive. Journal of Logic Programming, 1(3) 225-240, 1984Google ScholarCross Ref
- Mak81.J A Makowsky. Characterizingng data base dependencms In 8th Coll on Automata, Languages and Programming, Springer Verlag, 1981 Google ScholarDigital Library
- Man74.Z Manna. Mathemalzcal Theory of Computatzon. McGraw-Hill, New York, 1974 Google ScholarDigital Library
- MUVG86.K Morns,J D Ullman, and A Van Gelder. Design overview of the Nail syslem. In Third Int'l Conf on Logic Programming, }uly 1986 Google ScholarDigital Library
- ND82.J -M Nicolas and R Demolombe. On the Stability of Relational Queries. Technical Report, ONERA-CERT, 1982Google Scholar
- Nic82.J-M Nicolas. Logic for improving integrity checking in relational databases. Acta Informatica, 18(3) 227-253, 1982Google ScholarDigital Library
- Top86.R Topor. Domain Independent Formulas and Databases. Technical Report 86/11, Unniv of Melbourne, 1986 (To appear in Theoretical Computer Science)Google Scholar
- Ull80.J D Ullman. Principles of Database Systems. Computer Science Press, Rockville, MD, 1980 (Revised Ed 1982) Google ScholarDigital Library
Index Terms
- Safety and correct translation of relational calculus formulas
Recommendations
Safety and translation of relational calculus
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 ...
Relational Semantics of the Lambek Calculus Extended with Classical Propositional Logic
We show that the relational semantics of the Lambek calculus, both nonassociative and associative, is also sound and complete for its extension with classical propositional logic. Then, using filtrations, we obtain the finite model property for the ...
Translation of first order formulas into ground formulas via a completion theory
A translation technique is presented which transforms a class of First Order Logic formulas, called Restricted formulas, into ground formulas. For the formulas in this class the range of quantified variables is restricted by Domain formulas.If we have a ...
Comments