Ronald Fagin
- 1 AHo, A.V., BEERI, C., AND U~lq~ J.D.The theory of joins m relational databases, ACM Trans. Database Syst. 4, 3 (Sept. 1979), 297-314. Google Scholar
- 2 ARMSTRONG, W.W Dependency structures of database relationships. Prec. IFIP 74. North Holland, Amsterdam, 1974, pp. 580-583.Google Scholar
- 3 ARMSTRONG, W.W., ANO DELOBEL, C.Decompositions and functional depomlencies in reIattom. A CM Trans. Database Syst 5, 4 (Dec. 1980), 4(M.-430. Google Scholar
- 4 BE~tu, C. Personal communicauon, 1979.Google Scholar
- 5 BEERI, C, AND BERNSTEIN, P.A. Computational problems related to the design of normal form relational schemas A CM Trans. Database Syst. 4, 1 (Mar. 1979), 30--59. Google Scholar
- 6 BEeRI, C., DOWD, M., FAGIN, R., AND STATMAN, R On the structure of Armstrong relations for functional dependencies. To appear m J. A CM. Google Scholar
- 7 BEERI, C, FAOtN, R., AND HOWARD, J.H.A complete axmmatization for functional and multivalued dependencies in database relaUons. Prec. Int. ACM-SIGMOD Conf. on Management of Data, Toronto, Ont., Can., 1977, pp. 17-61. Google Scholar
- 8 BgEm, C., AND V AgDL M.Y. A proof procedure for data dependencies. Tech. Pep., Hebrew Univ. of Jerusalem, Jerusalem, Israel, Aug. 1980.Google Scholar
- 9 BEERI, C., ^ND Vxgm, M.Y. Formal systems for tuple and equality-generating dependenci~s. Tech. Pep, Hebrew Umv. of Jerusalem, Jerusalem, Israel, Apr. 1981Google Scholar
- 10 BEERI, C., AND "CAROl, M.Y.The maplicadon problem for data dependencies. In Proc. 8th lnt. Conf. on Automata, Languages, and Programming, Lecture Notes m Computer Science 115, Springer-Vedag, New York, 1981, pp. 73-85 Google Scholar
- 11 BROOKS, M.Determining correctness by testing, Ph.D Dissertation, Stanford Univ., Stanford, Calif., 1980. Google Scholar
- 12 CASANOVA, M A., FAGIN, R., AND PAPADIMITRIOU, C Inclusion dependencies and their mteracUon with functional dependencies. Prec. tst ACM SIGACT-SIGMOD Cord', or, Principles of Database Systems, Los Angeles, Calif., 1982, pp. 171--176. Google Scholar
- 13 CHANO, C C., AND KEISLER, H.J Model Theory. North Holland, Amsterdam, 1973.Google Scholar
- 14 CODD, E.F.Further normah~tion of the database relational model. In Data Base Systems, Courant Computer Science Symposia 6, R Rusdn, Ed., Prentice Hall, Englewood Cliffs, N.J., 1971, pp. 33-64.Google Scholar
- 15 CODD, E.F.Relational completeness of data base sub-languages. In Data Base Systems, Courant Computer Science Symposmm, R. Rustm, Ed, Prentice Hall, Englewood Cliffs, N.J. 1971, pp. 65-98Google Scholar
- 16 COOPER, E.C.On the expressive power of query languages. Tech. Rep. TR-14-80, Center for Research in Computing Technology, Harvard Univ., Cambndge, Mass., 1980.Google Scholar
- 17 DEMOLO~E, R. A syntacucal characterizatmn of a subset of def'trnte and safe formulas. Teeh. Pep., ONERA-CERT, Toulouse, France, Sept. 198i.Google Scholar
- 18 DEMOLOMBE, R., AND NICOLAS, J.-M.On the chamctenzaUon of "valid" formulas for database querying. Tech. Rep., ONERA-CERT, Toulouse, France, Sept. 1981.Google Scholar
- 19 DIP^OLA, R. The recursive unsolvabdity of the decision problem for the class of definite formulas J ACM 16, 2 (Apr. 1969), 324-327. Google Scholar
- 20 ENDERTON, H.B. A Mathematical Introduction to Logic. Aeademtc Press, New York, 1972.Google Scholar
- 21 FAGIN, R.Multivalued dependencies and a new normal form for relational database, s. A CM Trans. Database Syst 2, 3 (Sept. 1977), 262-278. Google Scholar
- 22 FAGIN, R.Funettonal dependenctes in a relational database and propositional logic. IBM ~ Res. DeveL 21, 6 (Nov. 1977), 534-544.Google Scholar
- 23 FAGIN, R. Hem dames and database dependencies. Prec. 12th Ann. ACM Symp. on Theory of Computing, Los Angeles, Calif, 1980, pp. 123-134 (extended abstract) Google Scholar
- 24 FAOIN, R. A normal form for relational databases that is based on domains and keys. ACM Trans. Database Syst. 6, 3 (Sept 1981), 387-415 Google Scholar
- 25 FAOtN, R Armstrong databases. Prec, 7th IBM Syrup. on Mathematical Foundations of Computer Science, Kanagawa, Japan, May 1982.Google Scholar
- 26 FAOtN, R., MAmR, D., U~N, J.D., ^ND YAm~AKAK}S, M.Tools for template dependenoes. To appear in SIAM J. Comput.Google Scholar
- 27 FAGIN, R., AND VARD}, M.Y. Armstrong databases for functional and inclusion dependencies. Res. Pep. RJ3500, IBM Research Laboratory, San Jose, Cafi~, June 1982.Google Scholar
- 28 GI~SBUgO, S., ~D ZAIDDXN, S.M. Properties of fenctional-dependency families. J. A CM 29, 3 (July 1982), 678--698. Google Scholar
- 29 GRANT, J., ^~D JACOBS, B.E.On the family of generalized dependency constraints. J. A CM 29, 4 (Oct. 1982), 986-997. Google Scholar
- 30 GR~TZ~R, G. Universal Algebra, 2nd ed. Springer-Vedag, New York, 1979.Google Scholar
- 31 GLamVICH, Y., AND LEwis, H.R.The inference problem for template dependencies. Proc. 1st ACM SIGACT-SIGMOD Syrup. on the Principles of Database Systems, Los Angeles, Cahf., 1982, pp. 221-229. Google Scholar
- 32 Ho~, A.On sentences which are true of direct unions of algebras J. Symbolic Logic 16 (1951), 14--21.Google Scholar
- 33 HULL, R.Implicauonal dependency and t'mite specification. Tech. Pep., Univ. of Southern Californta, Los Angeles, Calif., 198 I.Google Scholar
- 34 KA~s, P.C. On the computational complexity of eardiaality constraints in relational databases. Inf. Proc. Le#t. 11, 2 (Oct. 1980), 98-101.Google Scholar
- 35 K~st~g, H.J.Some appfications of infinitely long formulas. J. Symbolic Logic 30, 3 (Sept. 1965), 339-349.Google Scholar
- 36 Kumqs, LL.Answering questions by computer: A logical study. Tech. Rep RM-5428-PR, Rand Corp., Santa Monica, Cahf., Dec. 1967.Google Scholar
- 37 MAmx, D., M~NDFLZON, A., AND S^Grv, Y.Testing implications of data dependencies. A CM Trans. Database Syst. 4, 4 (Dec. 1979), 455--469. Google Scholar
- 38 MF.tCDt~LZON, A.O., ^~D MAmR, D.Generalized mutual dependencies and the decomposmon of database relations. Pro~. 5th Int. Conf. on Very Large Data Bases, R/o de Janetro, Brazil, 1979, pp. 75-82.Google Scholar
- 39 NICOLAS, J.-M.First-order logic formalization for funcUonal, multivalued, and mutual dependencies. Proc. ACM SIGMOD lm Conf. on Management of Data, Austin, Texas, 1978, pp. 40-46. Google Scholar
- 40 NICOLAS, J.-M.Logic for/reproving integrity checking in relational databases. To appear in ActaGoogle Scholar
- 41 P~.RAOAENS, J. Transitive dependencies in a database scheme. Tech Rep R387, MBLE, Brussels, Belgium, 1979.Google Scholar
- 42 PARADAENS J., ANn JANSSZNS, D.Decomposttions of relations: a comprehensive approach. In Advances m Data Base Theory, Vol. 1, H. Gallaire, J. Mmker, and J-M. Nicolas, Eds., Plenum Publishing, New York, 1981.Google Scholar
- 43 P^~, D.S., ANt> PARSAYE-GHOMI, K.Inference involving embedded muluvalued dependenoes and transitive dependencies Proc. int. ACM-SIGMOD Conf on Management of Data, Los Angeles, Calif., 1980, pp. 52-57. Google Scholar
- 44 RISSANEN, J.Theory of relations for databases--A tutorial survey. Proc. 7th Syrup. on Mathematical Foundations of Computer Science, Lecture Notes m Computer Science 64, J. Winkowski, Ed., Springer- Veflag, New YoA, pp. 537-551.Google Scholar
- 45 SADRI, F.Personal communication.Google Scholar
- 46 SADRI, F, AND ULLMAN, J.D. Template dependenctes: A large class of dependencies in relational databases and its complete axiomatization, d. A CM 29, 2 (Apr. 1982), 363-372. Google Scholar
- 47 SAow, Y., AND WxL~Cr~, S.F.Subset dependencies and a completeness result for a subclass of embedded multivalued dependencies. ~ ACM 29, I (Jan. 1982), 103-117. Google Scholar
- 48 SAGIV, Y., DELOBEL, C., PARma, D.S. $g., ^ND FAOIN, R.An equivalence between relattonal database dependencies and a fragment of propositional logic. ~ ACM 28, 3 (July 1981), 435--453. Google Scholar
- 49 sHOI~NFIELD, J.R.Mathematical Logic. Addison-Wesley, Reading, Mass., 1967.Google Scholar
- 50 StLVA, A.M., AND M~liLKANOI~F, M.A. A method for helping discover the dependencies of a relation. In Advances In Data Base Theory, Vol. 1, H. Gallair~, J. Minker, and J.-M. Nicolas, Eds., Plenum Publishing, New York, 1981.Google Scholar
- 51 SLAGLE, J.R., AND KONIVI~, D. Finding resolution proofs using duplicate goals m AND/OR trees. Inf. Sct. 4 (1971), 313-342.Google Scholar
- 52 STATMAN, R. Private commumcation.Google Scholar
- 53 TaasYd, A.Contributions to the theory of Models I. Nederl. Akad Wetensch. Proc. Ser. A 57 (1954), 572-588 (Indag. Math., vol 16).Google Scholar
- 54 U~, J.D.Principles of Database Syaems. Computer Science Press, Woodland Hills, Calif., 1980.Google Scholar
- 55 VXgD}, M.Y.The decision problem for database dependencies. Inf. Proc. Left. 12, 5 (Oct 1981), 251-254.Google Scholar
- 56 VAgDI, M.Y. Private commumcauonGoogle Scholar
- 57 VARDI, M.Y.The maplication and finite implication problems for typed template dependencies. Proc 1st ACM SIGACT-SIGMOD Conf. on Principles of Database Systems, Los Angeles, Calif, 1982, pp. 230-238. Google Scholar
- 58 YA.~rO.gAKIS, M. Private communication.Google Scholar
- 59 YANNAKAKIS, M., AND PAPADIMITRIOU, C.Algebraic dependencies. Proe. 21st IEEE Syrup. on Foundations of Computer Science, Syracuse, N.Y., 1980, pp. 328-332. To appear in J. Comp. Syst. SciGoogle Scholar
- 60 ZLOOF, M.M. Query-by-example. Proc. 1975 AFIPS NCC, V01. 44 AFIPS Press, Arlington, Va., 1975, pp 431--438.Google Scholar
Index Terms
- Horn clauses and database dependencies
Recommendations
Higher-order Horn clauses
A generalization of Horn clauses to a higher-order logic is described and examined as a basis for logic programming. In qualitative terms, these higher-order Horn clauses are obtained from the first-order ones by replacing first-order terms with simply ...
Comments