Testing satisfaction of functional dependencies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Testing satisfaction of functional dependencies

Full text

Pdf (518 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 3 (July 1982) table of contents

Pages: 668 - 677

Year of Publication: 1982

ISSN:0004-5411

Author

Peter Honeyman

Bell Laboratories, Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 35, Citation Count: 49

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322326.322330 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
	2	BEERI, C., AND HONEYMAN, P Preserving functional dependencies SIAM J Comput. 10 (Aug. 1981), 647-656
	3	E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
	4	CODD, E.F. Further normalization of the data base relational model In Data Base Systems, R Rusttn, Ed., PrenUce Hall, Englewood Cliffs, N.J, 1972, pp 33-64
	5	Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
	6	Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
	7	HONEYMAN, P., LADNER, R E, AND YANNAKAKIS, M Testing the universal instance assumption Inf. Proc. Lett 20, 1 (1980), 14-19
	8	David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
	9	RISSANEN, J Theory of relations for databases-A tutorial survey Proc 7th Syrup. on Mathematical Foundatzons of Computer Science, Lecture Notes in Computer Science 64, G GoDs and J Hartmanis, Eds., Springer-Verlag, Berlin, 1978, pp 536-551
	10	Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
	11	ZANIOLO, C Analysis and design of relational schemata for database systems Tech. Pep UCLA- ENG-7669, Dep. of Computer Science, Univ. of Cahfornla, Los Angeles, Calif., 1976.

CITED BY 49

	Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983
	E P F Chan , Paolo Atzeni, On the properties and characterization of connection-trap-free schemes, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.140-147, March 24-26, 1986, Cambridge, Massachusetts, United States
	Paola Atzeni , Riccardo Torlone, Updating relational databases through weak instance interfaces, ACM Transactions on Database Systems (TODS), v.17 n.4, p.718-745, Dec. 1992
	Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984
	Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM (JACM), v.30 n.3, p.514-550, July 1983
	Ke Wang , Marc H. Graham, Constant-time maintainability: a generalization of independence, ACM Transactions on Database Systems (TODS), v.17 n.2, p.201-246, June 1992
	E. P. F. Chan , H. J. Hernandez, On designing database schemes bounded or constant-time maintainable with respect to functional dependencies, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.48-57, March 23-25, 1987, San Diego, California, United States
	Moshe Vardi, On the integrity of databases with incomplete information, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.252-266, March 24-26, 1986, Cambridge, Massachusetts, United States
	Yehoshua Sagiv, Evaluation of queries in independent database schemes, Journal of the ACM (JACM), v.38 n.1, p.120-161, Jan. 1991
	David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984
	Mark Levene , George Loizou, Semantics for null extended nested relations, ACM Transactions on Database Systems (TODS), v.18 n.3, p.414-459, Sept. 1993
	Ke Wang, Polynomial time designs toward both BCNF and efficient data manipulation, ACM SIGMOD Record, v.19 n.2, p.74-83, Jun. 1990
	Paolo Atzeni , Riccardo Torlone, Efficient updates to independent schemes in the weak instance model, ACM SIGMOD Record, v.19 n.2, p.84-93, Jun. 1990
	Edward P. F. Chan , Hector J. Hernandez, Independence-reducible database schemes, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.163-173, March 1988, Austin, Texas, United States
	P. Atzeni , R. Torlone, Updating databases in the weak instance model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.101-109, March 1989, Philadelphia, Pennsylvania, United States
	Edward P. F. Chan , Alberto O. Mendelzon, Independent and separable database schemes, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Wilfred Ng, An extension of the relational data model to incorporate ordered domains, ACM Transactions on Database Systems (TODS), v.26 n.3, p.344-383, September 2001
	Yehoshua Sagiv, Sagiv,Y-On finite FD-acyclicity, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.173-182, March 24-26, 1986, Cambridge, Massachusetts, United States
	Paolo Atzeni , Edward P. F. Chan, Efficient optimization of simple chase join expressions, ACM Transactions on Database Systems (TODS), v.14 n.2, p.212-230, June 1989
	P. Atzeni , M. C. De Bernardis, A new basis for the weak instance model, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.79-86, March 23-25, 1987, San Diego, California, United States
	Marc H. Graham , Alberto O. Mendelzon , Moshe Y. Vardi, Notions of dependency satisfaction, Journal of the ACM (JACM), v.33 n.1, p.105-129, Jan. 1986
	K. Wang, Can constant-time-maintainability be more practical?, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.120-127, March 1989, Philadelphia, Pennsylvania, United States
	Jeffrey D. Ullman, The U. R. strikes back, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California
	Héctor J. Hernández , Edward P. F. Chan, A characterization of constant-time maintainability for BCNF database schemes, ACM SIGMOD Record, v.17 n.3, p.209-217, June 1988
	Edward P. F. Chan , Héctor J. Hernández, Independence-reducible database schemes, Journal of the ACM (JACM), v.38 n.4, p.854-886, Oct. 1991
	Jeffrey D. Ullman, On Kent's “Consequences of assuming a universal relation” (Technical correspondance), ACM Transactions on Database Systems (TODS), v.8 n.4, p.637-643, Dec. 1983
	Kent Laver , Alberto O. Mendelzon , Marc H. Graham, Functional dependencies on cyclic database schemes, ACM SIGMOD Record, v.13 n.4, May 1983
	Edward P. F. Chan , Alberto O. Mendelzon, Answering queries on embedded-complete database schemes, Journal of the ACM (JACM), v.34 n.2, p.349-375, April 1987
	Marc H. Graham , Moshe Y. Vardi, On the complexity and axiomatizability of consistent database states, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada
	Jorma Rissanen, On equivalences of database schemes, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California
	Marc H. Graham , Mihalis Yannakakis, Independent database schemas, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California
	David Maier , David Rozenshtein , David S. Warren, Windows on the world, ACM SIGMOD Record, v.13 n.4, May 1983
	Mark Levene , George Loizou, Why is the snowflake schema a good data warehouse design?, Information Systems, v.28 n.3, p.225-240, May 2003
	D. Sacca , F. Maufredi , A. Mecchia, Properties of database schemata with functional dependencies, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada
	David Maier , David S. Warren, Specifying connections for a universal relation scheme database, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida
	Marc H. Graham, Path expressions in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Marc H. Graham, Functions in databases, ACM Transactions on Database Systems (TODS), v.8 n.1, p.81-109, March 1983
	T. C. Ting , Lee A. Becker , Z. Q. Tan, U²RS: an upgradable universal relation system, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.188-196, February 1988, Atlanta, Georgia, United States
	David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, The revenge of the JD, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Peter Honeyman , Edward Sciore, A new characterization of independence, ACM SIGMOD Record, v.13 n.4, May 1983
	Mihalis Yannakakis, Querying weak instances, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada
	Edward P. F. Chan, Optimal computation of total projections with unions of simple chase join expressions, ACM SIGMOD Record, v.14 n.2, June 1984
	Yaron Kanza , Yehoshua Sagiv, Computing full disjunctions, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.78-89, June 09-11, 2003, San Diego, California
	Sharon M. Kuck , Yehoshua Sagiv, Designing globally consistent network schemas, ACM SIGMOD Record, v.13 n.4, May 1983
	Riccardo Torlone, Two approaches to the integration of heterogeneous data warehouses, Distributed and Parallel Databases, v.23 n.1, p.69-97, February 2008
	Héctor J. Hernández , Edward P. F. Chan, Constant-time-maintainable BCNF database schemes, ACM Transactions on Database Systems (TODS), v.16 n.4, p.571-599, Dec. 1991
	Mihalis Yannakakis, Algorithms for acyclic database schemes, Proceedings of the seventh international conference on Very Large Data Bases, p.82-94, September 09-11, 1981, Cannes, France
	Paolo Atzeni , Edward P. F. Chan, Independent Database Schemes under Functional and Inclusion Dependencies, Proceedings of the 13th International Conference on Very Large Data Bases, p.159-166, September 01-04, 1987
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996