An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic

Full text

Pdf (1.34 MB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 3 (July 1981) table of contents

Pages: 435 - 453

Year of Publication: 1981

ISSN:0004-5411

Authors

Yehoshua Sagiv	Department of Computer Science, 222 Digital Computer Laboratory, University of Illinois at Urbana-Champaign, Urbana, Illinois
Claude Delobel	Computer Laboratory, University of Grenoble, Boite Postale 53, 38041 Grenoble Cedex, Grenoble, France
D. Scott Parker, Jr.	Computer Science Department, School of Engineering and Applied Science, University of California at Los Angeles, Los Angeles, California
Ronald Fagin	IBM Research Laboratory, K52/282, 5600 Cottle Road, San Jose, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 37, Citation Count: 31

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/322261.322263 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	ARMSTRONG, W W Dependency structures of database relationships Proc. IFIP 74, North-Holland, Amsterdam, 1974, pp. 580--583
	2	W. W. Armstrong , C. Deobel, Decompositions and functional dependencies in relations, ACM Transactions on Database Systems (TODS), v.5 n.4, p.404-430, Dec. 1980 [doi>10.1145/320610.320620]
	3	BEERI, C. On the role of data dependencies m the construction of relauonal database schemas. Tech Rep. No 43, Dep. of Computer Science, The Hebrew Univ of Jerusalem, Jerusalem, Israel, Jan 1979
	4	Catriel Beeri, On the menbership problem for functional and multivalued dependencies in relational databases, ACM Transactions on Database Systems (TODS), v.5 n.3, p.241-259, Sept. 1980 [doi>10.1145/320613.320614]
	5	Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
	6	BISKUP, J On the complementaUon rule for multivalued dependenoes m database relattons A cta Inform 10, 3 (1978), 297-305.
	7	BISKUP, J Inferences of multwalued dependencms m fixed and undetermined umverses Theoret. Comput. Sci 10, 1 (Jan 1980), 93-105
	8	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]
	9	DELOBEL, C., AND CASEY, R.G Decomposmon of a data base and the theory of Boolean switching funcUons IBM Z Res Dev. 17, 5 (Sept 1973), 374-386 Also "Comment," IBM ~ Res and Dev 21, 5 (Sept. 1977), 484-485.
	10	DELOBEL, C., AND PARKER, D.S.FuncUonal and multlvalued dependencies in a relational database and the theory of Boolean switching functmons Tech Rep, Univ of Grenoble, Grenoble, France, Nov. 1978
	11	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]
	12	FAGIN, R. Funcuonal dependencies m a relational database and proposmonal logic. IBM J. Res. Dev 21, 6 (Nov. 1977), 534-544.
	13	Ronald Fagin, Normal forms and relational database operators, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582120]
	14	HAGIHARA, K, ITO, M, TANIGUCHI, K, AND KASAMI, T Decision problems for multwalued dependencies in relaUonal databases. SIAM J. Comput 8, 2 (May 1979), 247-264.
	15	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]
	16	MAKINOUCHI, AA constderation on normal form of not-necessarily-normalized relauon m the relational database model Proc 3rd lnt Conf. on Very Large Data Bases, Tokyo, Japan, Oct. 1977, pp. 447-453
	17	Alberto O. Mendelzon, On Axiomatizing Multivalued Dependencies in Relational Databases, Journal of the ACM (JACM), v.26 n.1, p.37-44, Jan. 1979 [doi>10.1145/322108.322112]
	18	J. M. Nicolas, First order logic formalization for functional, multivalued and mutual dependencies, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509269]
	19	NICOLAS, J.M Mutual dependencies and some results on undecomposable relations. Proc. 4th Int Conf on Very Large Data Bases, West Berlin, Sept 1978, pp. 360-367.
	20	PARKER, D.S., AND DELOBEL, C Algorithmic appllcauons for a new result on multivalued dependencles. Proc 5th lnt Conf on Very Large Data Bases, Rio de Janelro, Brazil, Oct. 1979, pp. 67-74.
	21	RISSANEN, J.Theory ofrelanons for databases--a tutorial survey In Proc. 7th Symp. on Mathemattcal Foundattons of Computer Scwnce, Lecture Notes m Computer Science 64, Springer-Verlag, Berlin and Heidelberg, 1978, pp. 536-551.
	22	Yehoshua Sagiv, An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic, Journal of the ACM (JACM), v.27 n.2, p.250-262, April 1980 [doi>10.1145/322186.322190]
	23	SAGIV, Y, AND FAGIN, R An eqmvalence between relational database dependencies and a subset of proposmonal logic. Res Rep RJ2500, IBM Research Lab, San Jose, Calif., March 1979.
	24	Yehoshua Sagiv , Scott F. Walecka, Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies, Journal of the ACM (JACM), v.29 n.1, p.103-117, Jan. 1982 [doi>10.1145/322290.322297]
	25	TANAKA, K, KAMBAYASHI, Y., AND YAJIMA, S.Properties of embedded multivalued dependencies m relational databases Trans. IECE Japan E62, 8 (Aug. 1979), 536-543
	26	ZANIOLO, C. Analysts and destgn of relational schemata for database systems Tech Rep UCLA- ENG-7669, Dep of Computer Science, Umverslty of Cahfornla, Los Angeles, Calif, July 1976

CITED BY 31

	Patrick C. Fischer , Dirk Van Gucht, Weak multivalued dependencies, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada
	Marcelo Arenas , Leonid Libkin, A normal form for XML documents, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Yehoshua Sagiv, An Algorithm for Inferring Multivalued Dependencies with an Application to Propositional Logic, Journal of the ACM (JACM), v.27 n.2, p.250-262, April 1980
	Catriel Beeri , Moshe Y. Vardi, A Proof Procedure for Data Dependencies, Journal of the ACM (JACM), v.31 n.4, p.718-741, Oct. 1984
	Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982
	Hirofumi Katsuno, An extension of conflict-free multivalued dependency sets, ACM Transactions on Database Systems (TODS), v.9 n.2, p.309-326, June 1984
	Yehoshua Sagiv , Scott F. Walecka, Subset Dependencies and a Completeness Result for a Subclass of Embedded Multivalued Dependencies, Journal of the ACM (JACM), v.29 n.1, p.103-117, Jan. 1982
	Zvi Galil, An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database, Journal of the ACM (JACM), v.29 n.1, p.96-102, Jan. 1982
	Thomas Lukasiewicz, Efficient global probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, Proceedings of the sixth international conference on Information and knowledge management, p.75-82, November 10-14, 1997, Las Vegas, Nevada, United States
	Stavros S. Cosmadakis , Christos H. Papadimitriou, Updates of Relational Views, Journal of the ACM (JACM), v.31 n.4, p.742-760, Oct. 1984
	Stavros S. Cosmadakis , Paris C. Kanellakis , Moshe Y. Vardi, Polynomial-time implication problems for unary inclusion dependencies, Journal of the ACM (JACM), v.37 n.1, p.15-46, Jan. 1990
	Ronald Fagin, A normal form for relational databases that is based on domains and keys, ACM Transactions on Database Systems (TODS), v.6 n.3, p.387-415, Sept. 1981
	Stavros S. Cosmadakis , Christos H. Papadimitriou, Updaies of relational views, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Allan Shepherd , Larry Kerschberg, Prism: a knowledge based system for semantic integrity specification and enforcement in database systems, ACM SIGMOD Record, v.14 n.2, June 1984
	Catriel Beeri , Martin Dowd , Ronald Fagin , Richard Statman, On the Structure of Armstrong Relations for Functional Dependencies, Journal of the ACM (JACM), v.31 n.1, p.30-46, Jan. 1984
	Paris C. Kanellakis , Stavros S. Cosmadakis , Moshe Y. Vardi, Unary inclusion dependencies have polynomial time inference problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.264-277, December 1983
	L. Li, Fast In-Place Verification of Data Dependencies, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.266-281, April 1993
	C. Beeri , M. Kifer, Elimination of intersection amomalies from database schemes, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
	Marcelo Arenas , Leonid Libkin, A normal form for XML documents, ACM Transactions on Database Systems (TODS), v.29 n.1, p.195-232, March 2004
	Ronald Fagin, Horn clauses and database dependencies (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.123-134, April 28-30, 1980, Los Angeles, California, United States
	David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981
	Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984
	Bassem Sayrafi , Dirk Van Gucht, Differential constraints, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Chao-Chih Yang, Deduction Graphs: An Algorithm and Applications, IEEE Transactions on Software Engineering, v.15 n.1, p.60-67, January 1989
	Sven Hartmann , Sebastian Link, Horn clauses and functional dependencies in complex-value databases, Proceedings of the 17th Australasian Database Conference, p.21-30, January 16-19, 2006, Hobart, Australia
	Hervé Gallaire, Impacts of logic and databases (invited paper), Proceedings of the seventh international conference on Very Large Data Bases, p.248-259, September 09-11, 1981, Cannes, France
	K. K. Nambiar, Some analytic tools for the design of relational database systems, Proceedings of the sixth international conference on Very Large Data Bases, p.417-428, October 01-03, 1980, Montreal, Quebec, Canada
	Sven Hartmann , Sebastian Link , Thu Trinh, Constraint acquisition you can chase but you cannot find, Proceedings of the fifth on Asia-Pacific conference on conceptual modelling, January 01-01, 2008, Wollongong, NSW, Australia
	Hiroshi Arisawa , Takao Miura, On the Properties of Extended Inclusion Dependencies, Proceedings of the 12th International Conference on Very Large Data Bases, p.449-456, August 25-28, 1986
	Carol Helfgott LeDoux , Douglas Stott Parker, Jr., Reflections on Boyce-Codd Normal Form, Proceedings of the 8th International Conference on Very Large Data Bases, p.131-141, September 08-10, 1982
	Sven Hartmann , Sebastian Link , Thu Trinh, Boolean Constraints for XML Modeling, Proceeding of the 2009 conference on Information Modelling and Knowledge Bases XX, p.85-104, July 10, 2009