Catriel Beeri
Moshe Y. Vardi
- 1 ABITEBOUL, S., AND VARDI, M. Y.Formal systems for untyped data dependencacs, To appear.Google Scholar
- 2 AHO, A.V., BEERI, C., AND ULLMAN, J. D.The theory of joins in relattonal databases. ACM Trans Database Syst 4, 3 (Sept. 1979), 297-314. Google Scholar
- 3 Av~o, A. V., SAGIV, Y., AND ULLMAN, J. D.Euivalence among relational expressions. SIAM d Comput. 8 ( 1979), 218-246.Google Scholar
- 4 ARMSTRONG, W. W.Dependency structure in data base relationships. In Proceedings of lFIP 74, Elsevier North-Holland, New York, 1974, pp. 580-583.Google Scholar
- 5 ARMSTRONG, W. W., AND DELOBEL, C.Decompositions and functional dependencies in relations. ACM Trans. Database Syst. 5, 4 (Dee. 1980), 404--430. Google Scholar
- 6 BEERI, C. On the membership problem for functional and multivalued dependencies in relational databases. ACM Trans Database Syst 5, 3 (Sept. 1980), 241-259. Google Scholar
- 7 BEERI, C., AND BERNSTEIN, P. A.Computauonal problems related to the design of normal form relational schemas. ACM Trans Database Syst 4, 1 (Mar. 1979), 30-5% Google Scholar
- 8 BEERI, C., BERNSTEIN, P. A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. In Proceedings of the 4th lnternattonaI Conference on Very Large Data Bases (West Berlin, Germany, Sept. 13-15). ACM, New York, 1978, pp. 113-124.Google Scholar
- 9 BEERI, C., FAGIN, R., AND HOWARD, J. H.A complete axiomatization for functional and multivalued dependencies in database relations. In Proceedmgs ofthe 3rd ACM-SIGMOD International Conference on Management of Data (Toronto, Ontario, Canada, Aug. 3-5). ACM, New York, 1977, pp. 47-61. Google Scholar
- 10 BERRI, C., MENDELZON, A. O., SAGIV, Y., AND ULLMAN, J. D. Eqmvalence of relational database schemes. SIAM Y Comput 10 (1981), 647-656.Google Scholar
- 11 BI~ERI, C., AND RISSANEN, J.Fmthful representation of relational database schemes. IBM Res. Rep. IBM, San Jose, 1980.Google Scholar
- 12 BEERI, C., AND VARDI, M. Y.On the complexity of testing implication of data dependencies. Res. Pep. Dept. Computer Science, The Hebrew University of jerusalem, Jerusalem, Israel, 1980.Google Scholar
- 13 Bi~ERI, C., AND VARDI, M. Y.The implication problem for data dependencies, in Proceedings of the 8th lnternattonal Colloquium for Automata Languages and Programming (Acre, israel, July 13-17). Lecture Notes in Computer Science, vol. 115. Springer-Vedag, New York, 1981, pp. 73- 85. Google Scholar
- 14 BEERI, C., AND VARDI, M. Y. On the properties of join dependencies. In Advances in Database Theory, H. GaUatre, J. Mmker, and J. M. Nicolas, Eds. Plenum Press, New York, 1981, pp. 25-72.Google Scholar
- 15 BEERI, C., AND VARDI, M. Y.Formal system for tuple and equality generating dependencies. SIAM J Comput 13 (1984), 76--98.Google Scholar
- 16 BERNSTEIN, P. A. Synthesizing third normal form relauons from functional dependencies. ACM Trans Database S),st I, 4 (Dec. 1976), 277-298. Google Scholar
- 17 BISKUP, J.On the complementation rule for multivalued dependencies in data base relations. Acta lnf 10 (1978), 297-305.Google Scholar
- 18 BISKUP, J Inferences of multivalued dependenctes in fixed and undetermined universe. Theor Comput Set 10 (1980), 93-105.Google Scholar
- 19 CHANDRA, A. K., LEwis, H. R., AND MAKOWSKY, J. A. Embedded implicational dependencies and their inference problem. In Proceedings of the 13th Annual ACM Symposium on the Theory of Computing (Milwaukee, Wise., May 11-13). ACM, New York, 1981, pp. 342--354. Google Scholar
- 20 CHANG, C. L., AND LEE, C. R. T.Symbolic Logtc and Mechamcal Theorem Proving. Academic Press, New York, 1973. Google Scholar
- 21 CODD, E. F.Further normalization of the data base relatlonal model. In Data Base Systems (R. Rustin, Ed.). Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.Google Scholar
- 22 DELOBFL, C. Normalization and hierarchal dependencies in the relational data model. ACM Trans Database Syst 3, 3 (Sept. 1978), 201-222. Google Scholar
- 23 FAGIN, R. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database S.vst 2, 2 (June 1977), 262-278. Google Scholar
- 24 F^GzN, 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 FAGIN, R.Horn clauses and database dependencies, J. ACM 29, 4 (Oct. 1982), 952-985. Google Scholar
- 26 FAGIN, R., MAmR,.D., ULLMAN, J. D., AND YANNAKAKIS, M.Tools for template dependencies. SlAM J. Comput. 12 (1983), 36-59,Google Scholar
- 27 GRAHAM, M. H.A new proof that the chase is a Chureh-Rosser replacement system. In Proceedings of the XPI Workshop on Relational Database Theory (Stony Brook, June) 1980.Google Scholar
- 28 GRANT, J., AND JACOBS, B. E.On the family of generalized dependency constraints. J. ACM 29, 2 (Oct. 1982), 986-997. Google Scholar
- 29 GUREVICH, Y., AND LEwis, H. R.The inference problem for template dependencies. In Proceed. mrs of the ACM Symposium on Principles of Database Systems (Los Angeles). ACM, New York, 1982, pp. 221-229. Google Scholar
- 30 ITO, M., TAN|GUCHI, K., AND KASAMI, T.Membership problem for embedded multivalued dependencies under some restr~ed conditions. Theor. Comput. Sci. 23 (1983), 175--194.Google Scholar
- 31 KANI/LLAKIS, P.C. On the computational complexity of cardinality constraints in relational databases. Inf. Proc. Left. 1I (1980), 98-101.Google Scholar
- 32 M~mR, D., MENDELZON, A. O., SADRI, F., AND ULLMAN, J. D.Adequacy of decompositions of relational databases. In Advances in Database Theory, H. Gallaire, J. Minker, and J. M. Nicolas, Eds. Plenum Press, New York, 1981, pp. 101-114.Google Scholar
- 33 MAIER, D., MENDELZON, A. O., AND SAGIV, Y'.Testing implications of data dependencies. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 455-469. Google Scholar
- 34 M^IER, D., SAG{V, Y., AND YANNAKAKIS, M.On the complexity of testing implications of functional and join dependencies. J. ACM 28, 4 (Oct. 1981), 680-695. Google Scholar
- 35 M~NDELZON, A. O. On axiomatizing multivalued dependencies in relational databases. J. ACM 26, 1 (Jan. 1979), 37-44. Google Scholar
- 36 Ncot~s, J. M.First order logic formalization for functional, multivalued and mutual dependeneies. In Proceedings of the ACM-SIGMOD international Conference on Management of Data (Austin, Tex,, May 3 l-June 2). ACId, New York, 1978, pp. 40-46. Google Scholar
- 37 NICOLAS, J. M.Mutual dependencies and some results on undeeomposable relations. In Proceedings of the 4th International Conference on Very Large Data Bases (West Berlin, Germany, Sept. 13-15). ACM, New York, 1978, pp. 360--367.Google Scholar
- 38 PAREDAEN$, J.Transitive dependencies in a database scheme. RAIRO lnf./Comput Sci 14 (1980), 149-164.Google Scholar
- 39 PAREDAI/NS, J.The interaction of integrity constraints in an information system. J. Comput Syst. Sci. 20 (1980), 310-329,Google Scholar
- 40 PAREDAENS, J.A universal formalism to express decomposition, functional dependencies and other constraints in a relational database. Theor. Comput. Sci. 19 (1982), 143-160.Google Scholar
- 41 PAREDAENS, J., AND JANSSENS, D.Decompositions of relations--A comprehensive approach. In Advances in Database Theory, H. Gallaire, J. Minker, and J. M. Nicolas, Eds. Plenum Press, New York, 1981, pp. 73-I00.Google Scholar
- 42 RISSANEN, J.Theory of relations for databases--A tutorial survey. In Proceedings of the 7th Symposium on Mathematwal Foundattons of Computer Science (Zakopane, Poland, Sept. 4-8) Lecture Notes in Computer Science, vol. 64. Springer-Vedag, New York, 1978, pp, 537-551.Google Scholar
- 43 SADRI, F., AND ULLMAN, J. D.Template dependencies: A large class of dependencies in relaUonal databases and its complete axiomatization. Z ACM 29, 2 (Apr. 1982), 363-372. Google Scholar
- 44 SADRI, F., AND ULLMAN, J.D.The theory of functional and template dependencies. Theor Comput. Sci. 17 (1982), 317-332.Google Scholar
- 45 SAGIV, Y., DeLOaEL, C., PARKEIL D. S., AND FAGIN, R. An equivalence between relational database dependenoes and a fragment of propositional calculus. J. ACM 28, 3 (July 1981), 435-453. Google Scholar
- 46 SAGIV, Y., AND WALECKA, S. F.Subset dependencies and a completeness result for a subclass of embedded multivalued dependencies. J. ACM 29, 1 (Jan. 1982), 103-117. Google Scholar
- 47 SOORE, E. A complete axiomatization of full join dependencies. J. ACM 29, 2 (Apr. 1982), 373- 393. Google Scholar
- 48 VARDi, M. Y.Axiomatization of functional and join dependencies in the relational model. M.Se. Thesis, Dept. Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, 1980.Google Scholar
- 49 VARDI, M.Y. The implication problem for data dependencies in relational databases. Ph.D. Thesis (in Hebrew), The Hebrew University of Jerusalem, Jerusalem, Israel, 1981.Google Scholar
- 50 V ARt)I, M. Y. The implication and the finite implication problems for typed template dependenties. Jr. Comput System Sci. 28, 1 (Feb. 1984), 3-28.Google Scholar
- 51 VARD{, M.Y. On the decomposition of relational databases. In Proceedings of the 23rd, lEEE Symposium on the Foundations of Computer Science, (Chicago, Nov. 3-5). IEEE, New York, 1982, pp. 176-187.Google Scholar
- 52 VA~m, M. Y.Inferring multivalued delx~dencies from functional and join dependencies, Acta Inf. 19 (1983), 305-324.Google Scholar
- 53 VARO~, M. Y.Inferring multivalued dependencies from tuple and equality generating dependencies, To appear.Google Scholar
- 54 YANNAKAKiS, M., AND PAPDIMITRIOU, C. Algebraic dependencies. J. Comput. System ScL 21 (1982), 2-41.Google Scholar
- 55 ZANIOLO, C.Analysis and design of relational schemata for database systems. Tech, Pep. UCLA- ENG-7769, Dept. Computer Science, UCLA, Los Angeles, July 1976.Google Scholar
Index Terms
- A Proof Procedure for Data Dependencies
Recommendations
Testing implications of data dependencies
Presented is a computation method—the chase—for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as ...
Extending dependencies with conditions
VLDB '07: Proceedings of the 33rd international conference on Very large data basesThis paper introduces a class of conditional inclusion dependencies (CINDs), which extends traditional inclusion dependencies (INDs) by enforcing bindings of semantically related data values. We show that CINDs are useful not only in data cleaning, but ...
Reviews
Seymour Ginsburg
During the past decade a host of different dependencies have been introduced into the relational model to capture different semantics. For unification and other purposes, some rather general types of dependencies have been abstracted, such as the generalized dependencies of Grant and Jacobs [1], the template dependencies of Sadri and Ullman [2,3], the algebraic dependencies of Yannakakis and Papadimitriou [4], and the embedded implicational dependencies of Fagin [5]. In the same spirit, the authors present here two new types. The first (the tuple-generating dependency) demands that :9I if some tuples satisfy certain equalities in the database, then some other tuples exist. The second type (the equality generating dependency) requires that under :9I , certain values in the given tuples must be equal. Within the above context, the authors study the implication problem. In particular, the chase is shown to be exponential for total dependencies, but may not halt for nontotal dependencies.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments