{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T14:52:41Z","timestamp":1674917561532},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[1991,5]]},"abstract":"\n 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\n domain independent<\/jats:italic>\n 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\n evaluable<\/jats:italic>\n formulas and the\n allowed<\/jats:italic>\n 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.\n <\/jats:p>\n \n Although evaluable queries have sensible answers, it is not straightforward to compute them efficiently or correctly. We introduce\n relational algebra normal form<\/jats:italic>\n for formulas from which form the correct translation into relational algebra is trivial. We give algorithms to transform an evaluable formula into an equivalent\n allowed<\/jats:italic>\n formula and from there into relational algebra normal form. Our algorithms avoid use of the so-called\n Dom<\/jats:italic>\n relation, consisting of all constants appearing in the database or the query.\n <\/jats:p>\n 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.<\/jats:p>","DOI":"10.1145\/114325.103712","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:29:00Z","timestamp":1027769340000},"page":"235-278","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["Safety and translation of relational calculus"],"prefix":"10.1145","volume":"16","author":[{"given":"Allen","family":"Van Gelder","sequence":"first","affiliation":[{"name":"Univ. of California at Santa Cruz, Santa Cruz"}]},{"given":"Rodney W.","family":"Topor","sequence":"additional","affiliation":[{"name":"The Univ. of Melbourne, Melbourne, Vic., Australia"}]}],"member":"320","published-online":{"date-parts":[[1991,5]]},"reference":[{"key":"e_1_2_1_1_2","volume-title":"North-Holland","author":"ACKERMANN W.","year":"1968","unstructured":"ACKERMANN , W. Solvable Cases of the Decision Problem . North-Holland , Amsterdam , 1968 . ACKERMANN, W. Solvable Cases of the Decision Problem. North-Holland, Amsterdam, 1968."},{"key":"e_1_2_1_2_2","first-page":"2","article-title":"Reduction of the relational model with infinite domains to the finite domain case","volume":"286","author":"AYLAMAZAN A. K.","year":"1986","unstructured":"AYLAMAZAN , A. K. , GIC~ULA , M. M. , S' roLBus HKIN , 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 ). 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).","journal-title":"Proceedings of USSR Academy of Science."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28662"},{"key":"e_1_2_1_4_2","article-title":"Relational completeness of data base sublanguages In Data Base Systems. R. Rustin, Ed. Prentice-Hall, Englewood Cliffs","volume":"65","author":"CODD E. F","year":"1972","unstructured":"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 . 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.","journal-title":"N.J."},{"key":"e_1_2_1_5_2","volume-title":"1st International Conference on Expert Database Systems.","author":"DECKER H","year":"1986","unstructured":"DECKER H Integrity enforcement in deductive databases . In 1st International Conference on Expert Database Systems. 1986 , 271 285. DECKER H Integrity enforcement in deductive databases. In 1st International Conference on Expert Database Systems. 1986, 271 285."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/359138.359142"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/321510.321524"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322347"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/512976.512998"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-1313-2.50037-8"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28661"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90011-6"},{"key":"e_1_2_1_15_2","volume-title":"Rockville, Md.","author":"MAIER","year":"1983","unstructured":"MAIER , D The Them'y of Relatzonal Databases Computer Science Press , Rockville, Md. , 1983 . MAIER, D The Them'y of Relatzonal Databases Computer Science Press, Rockville, Md., 1983."},{"key":"e_1_2_1_16_2","volume-title":"8th Colloquium on Automata","author":"MAKOWS~Y J. A.","year":"1981","unstructured":"MAKOWS~Y , J. A. Characterizing data base dependencies . In 8th Colloquium on Automata , Languages and Programmzng Springer Verlag , New York , 1981 MAKOWS~Y, J. A. Characterizing data base dependencies. In 8th Colloquium on Automata, Languages and Programmzng Springer Verlag, New York, 1981"},{"key":"e_1_2_1_17_2","volume-title":"Mathematical Theory of Computation","author":"MANNA Z.","year":"1974","unstructured":"MANNA , Z. Mathematical Theory of Computation . McGraw-Hill , New York , 1974 . MANNA, Z. Mathematical Theory of Computation. McGraw-Hill, New York, 1974."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/12069.12113"},{"key":"e_1_2_1_19_2","volume-title":"A Logic Language for Data and Knowledge Bases","author":"NAQVI S.","year":"1988","unstructured":"NAQVI , S. , AND TSUR , S. A Logic Language for Data and Knowledge Bases . Computer Science Press , Rockville Md ., 1988 . NAQVI, S., AND TSUR, S. A Logic Language for Data and Knowledge Bases. Computer Science Press, Rockville Md., 1988."},{"key":"e_1_2_1_20_2","volume-title":"M Logic for improving integrity checking in relational databases Acta Inf. 18, 3","author":"NICOLAS J.","year":"1982","unstructured":"NICOLAS , J. M Logic for improving integrity checking in relational databases Acta Inf. 18, 3 ( 1982 ), 227-253 NICOLAS, J. M Logic for improving integrity checking in relational databases Acta Inf. 18, 3 (1982), 227-253"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90113-7"},{"key":"e_1_2_1_24_2","volume-title":"Proceedings of the 12th Internatzonal Conference on Very Large Data Bases.","author":"ZANIOLO LDL","year":"1986","unstructured":"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. 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."},{"key":"e_1_2_1_25_2","volume-title":"D Prtnciples of Database and Knowledge-Base Systems","author":"ULLMAN J.","year":"1988","unstructured":"ULLMAN , J. D Prtnciples of Database and Knowledge-Base Systems . Vol. 1 . Computer Science Press , Rockville, Md , 1988 . ULLMAN, J. D Prtnciples of Database and Knowledge-Base Systems. Vol. 1. Computer Science Press, Rockville, Md, 1988."},{"key":"e_1_2_1_26_2","volume-title":"Principles of Database Systems","author":"ULLMAN J.D.","year":"1980","unstructured":"ULLMAN , J.D. Principles of Database Systems . Computer Science Press, Rockville , Md ., 1980 . (Revised ed. 1982). ULLMAN, J.D. Principles of Database Systems. Computer Science Press, Rockville, Md., 1980. (Revised ed. 1982)."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/28659.28693"},{"key":"e_1_2_1_28_2","first-page":"5","article-title":"The decision problem for database dependencies","volume":"12","author":"VAR","year":"1981","unstructured":"VAR m, M . The decision problem for database dependencies . Inf. Process. Lett. 12 , 5 ( 1981 ), 251-254. VARm, M. The decision problem for database dependencies. Inf. Process. Lett. 12, 5 (1981), 251-254.","journal-title":"Inf. Process. Lett."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/114325.103712","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:50:46Z","timestamp":1672264246000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/114325.103712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,5]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,5]]}},"alternative-id":["10.1145\/114325.103712"],"URL":"http:\/\/dx.doi.org\/10.1145\/114325.103712","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":["Information Systems"],"published":{"date-parts":[[1991,5]]},"assertion":[{"value":"1991-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}