Updates of Relational Views

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Updates of Relational Views

Full text

Pdf (1.24 MB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 4 (October 1984) table of contents

Pages: 742 - 760

Year of Publication: 1984

ISSN:0004-5411

Authors

Stavros S. Cosmadakis	Massachusetts Institute of Technology, Cambidge, Massachusetts
Christos H. Papadimitriou	Massachusetts Institute of Technology, Cambridge Massachusetts and National Techntcal University of Athens, Athens, Greece

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 39, Citation Count: 33

Additional Information:

references cited by index terms review 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/1634.1887 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. In Proceedings oflFIP 74. North-Holland, Amsterdam, 1974, pp. 580-583.
	2	M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
	3	F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
	4	Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
	5	BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database norrealization theory. In Proceedings of the 4th VLDB Conference (West Berlin, Germany, Sept. 13- 15). ACM, New York, 1978, pp. 113-124.
	6	BEEm, C., AND V^RDI, M. Y.On the complexity of testing implications of data dependencies. Res. Rep., Depl. of Computer Science, Hebrew Univ. of Jerusalem, Jerusalem, Israel, Dec. 1980.
	7	BEERI, C., AND VARDI, M. Y.On acyclic database decompositions. Inf. Control, to be pubfished.
	8	CARLSON, C.R., AND ARORA, A.K.The updatability of relational views based on functional dependencies. In 3rd International Computer Software and Applications Conference (Nov.). IEEE Computer Society, Chicago, I11., 1979.
	9	CHAMBERLIN, D. D., GRAY, J. N., AND TRAINER, I. L. Views, authorization and locking in a relational data base system. In Proceedings of 1975 Nauonal Computer Conference. AFIPS Press, Reston, Va., 1975, pp. 425.-430.
	10	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]
	11	CODD, E. F. Relational completeness of database sublanguages. In Data Base Systems, R. Rustin, Ed. Prentice Hall, Englewood Cliffs, N.J., 1972, pp. 65-98.
	12	CODD, E. F.Further normahzation of the database relational model. In Data Base Systems, R. Rustin, F_xt. Prentice Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.
	13	E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
	14	CODASYL Data Base Task Group, April 71 Report. ACM, New York, 1971.
	15	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	16	C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	17	DAYAL, U., AND BERNSTEIN, P, A.On the updatability of relational views. In Proceedings of the 4th VLDB Conference (West Berlin, Germany, Sept. 13-15). ACM, New York, 1978, 368-377.
	18	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]
	19	Ronald Fagin , Jeffrey D. Ullman , Moshe Y. Vardi, On the semantics of updates in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588100]
	20	FUgTADO, A. L., SI~VClK, K. C., AND DOS SANTOS, C. S.Permitting updates through views of data bases. Inform. Syst. 4, 4 (t979), 269-283.
	21	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	22	IMS/VS publications GH20-1260, SH20-9025, SH20-9026, SH20-9027. IBM, White Plmns, New York, 1978.
	23	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 [doi>10.1145/800061.808756]
	24	KAed', R.M.Reducibihty among combinatorial problems. In Complexity of Computer Compurations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 1972, pp. 85-104.
	25	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]
	26	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 [doi>10.1145/322276.322280]
	27	Jorma Rissanen, Independent components of relations, ACM Transactions on Database Systems (TODS), v.2 n.4, p.317-325, Dec. 1977 [doi>10.1145/320576.320580]
	28	RlSSANEN, J.Theory of relations for databases--A tutorial survey. In Proceedings of the 7th Sympostum on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 64. Spnnger-Vedag, New York, 1978, pp. 536-551.
	29	ROWE, L., AND STONEBRAKER, M.Manuscript. Univ. Cal., Berkeley, Berkeley, Calif., 1979.
	30	Yehoshua Sagiv , Claude Delobel , D. Scott Parker, Jr. , Ronald Fagin, An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic, Journal of the ACM (JACM), v.28 n.3, p.435-453, July 1981 [doi>10.1145/322261.322263]
	31	SPYRATOS, N.Translation structures of relational views. In Proceedings of the 6th VLDB Confer. ence (Montreal, Canada, Oct. 1-3). ACM, New York, ! 980, pp. 411--416.
	32	STOCKMEYER, L. J.The polynomial time hierarchy. Theor. Comput. Sci. 3, 1 (1976), 1-22.
	33	Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
	34	TODD, S. J. P.The Peterlee relational test vehicle--A system overview. IBM SFst. J. 15, 4 (1976), 285-308.
	35	Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
	36	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 [doi>10.1145/588111.588114]
	37	VARDI, M. Y. On decomposition of relational databases. In Proceedings of the 23rd Sympostum on Foundattons of Computer Science (Chicago, I11., Nov.), IEEE, New York, 1982.
	38	VARDI, M. Y.Inferring muhlvalued dependencies from funcuonal and join dependencies. Res. Rep., Dept. of Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, March 1980.
	39	WRATHALL, C.Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci. 3, 1 (1976), 23-33.
	40	ZANIOLO, C.Analysts and design of relational schemata for database systems. Tech. Pep. UCLA- ENG-7669, Dept. of Computer Science, Univ. of California, Los Angeles, Calif., July 1976.
	41	Carlo Zaniolo, Database relations with null values, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588117]
	42	ZLOOF, M. M.Query-by-Example: A data base language. IBM Syst. J. 16, 4 (1977), 324-343.

CITED BY 33

	Serge Abiteboul , Sophie Cluet , Tova Milo, A database interface for file update, ACM SIGMOD Record, v.24 n.2, p.386-397, May 1995
	Nicholas Roussopoulos, An incremental access method for ViewCache: concept, algorithms, and cost analysis, ACM Transactions on Database Systems (TODS), v.16 n.3, p.535-563, Sept. 1991
	Jens Lechtenbörger , Gottfried Vossen, On the computation of relational view complements, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Weidong Chen, Declarative updates of relational databases, ACM Transactions on Database Systems (TODS), v.20 n.1, p.42-70, March 1995
	Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987
	David W. Embley, NFQL: the natural forms query language, ACM Transactions on Database Systems (TODS), v.14 n.2, p.168-211, June 1989
	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
	Rom Langerak, View updates in relational databases with an independent scheme, ACM Transactions on Database Systems (TODS), v.15 n.1, p.40-66, March 1990
	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
	A. Basu, A Knowledge Representation Model for Multiuser Knowledge-Based Systems, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.177-189, April 1993
	Georg Gottlob , Paolo Paolini , Roberto Zicari, Properties and update semantics of consistent views, ACM Transactions on Database Systems (TODS), v.13 n.4, p.486-524, Dec. 1988
	Ernest Teniente , Antoni Olivé, Updating knowledge bases while maintaining their consistency, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.2, p.193-241, April 1995
	Andrea Neufeld , Guido Moerkotte , Peter C. Lockemann, Generating consistent test data: restricting the search space by a generator formula, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.2, April 1993
	Vânia M. P. Vidal , Marianne Winslett, Preserving update semantics in schema integration, Proceedings of the third international conference on Information and knowledge management, p.263-271, November 29-December 02, 1994, Gaithersburg, Maryland, United States
	M. A. Ketabchi , V. Berzins, Mathemtical Model of Composite Objects and Its Application for Organizing Engineering Databases, IEEE Transactions on Software Engineering, v.14 n.1, p.71-84, January 1988
	Hua Shu, Using Constraint Satisfaction for View Update, Journal of Intelligent Information Systems, v.15 n.2, p.147-173, Sept./Oct. 2000
	J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bi-directional tree transformations: a linguistic approach to the view update problem, ACM SIGPLAN Notices, v.40 n.1, p.233-246, January 2005
	Elisa Bertino , Pierangela Samarati , Sushil Jajodia, An Extended Authorization Model for Relational Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.1, p.85-101, January 1997
	Jens Lechtenbörger , Gottfried Vossen, On the computation of relational view complements, ACM Transactions on Database Systems (TODS), v.28 n.2, p.175-208, June 2003
	Stijn Dekeyser , Jan Hidders , Richard Watson , Ron Addie, Peer-to-peer form based web information systems, Proceedings of the 17th Australasian Database Conference, p.79-88, January 16-19, 2006, Hobart, Australia
	David Willmor , Suzanne M. Embury, An intensional approach to the specification of test cases for database applications, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Ling Wang , Elke A. Rundensteiner , Murali Mani, Updating XML views published over relational databases: towards the existence of a correct update mapping, Data & Knowledge Engineering, v.58 n.3, p.263-298, September 2006
	Ling Wang , Elke A. Rundensteiner , Murali Mani , Ming Jiang, HUX: handling updates in XML, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	J. Nathan Foster , Michael B. Greenwald , Jonathan T. Moore , Benjamin C. Pierce , Alan Schmitt, Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.3, p.17-es, May 2007
	Serge Abiteboul , Sophie Cluet , Tova Milo, A logical view of structured files, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.2, p.96-114, May 1998
	D. Laurent , J. Lechtenbörger , N. Spyratos , G. Vossen, Monotonic complements for independent data warehouses, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.295-315, December 2001
	Stephen J. Hegner, The complexity of embedded axiomatization for a class of closed database views, Annals of Mathematics and Artificial Intelligence, v.46 n.1-2, p.38-97, February 2006
	Weidong Chen , Julie Yu-Chih Liu, A procedural semantics for stratified database updates, Annals of Mathematics and Artificial Intelligence, v.21 n.2-4, p.187-220, 1997
	Arthur M. Keller, Choosing a View Update Translator by Dialog at View Definition Time, Proceedings of the 12th International Conference on Very Large Data Bases, p.467-474, August 25-28, 1986
	Antonis C. Kakas , Paolo Mancarella, Database Updates through Abduction, Proceedings of the 16th International Conference on Very Large Data Bases, p.650-661, August 13-16, 1990
	Kazutaka Matsuda , Zhenjiang Hu , Keisuke Nakano , Makoto Hamana , Masato Takeichi, Bidirectionalization transformation based on automatic derivation of view complement functions, ACM SIGPLAN Notices, v.42 n.9, September 2007
	Byron Choi , Gao Cong , Wenfei Fan , Stratis D. Viglas, Updating recursive XML views of relations, Journal of Computer Science and Technology, v.23 n.4, p.516-537, July 2008
	James Cheney , Laura Chiticariu , Wang-Chiew Tan, Provenance in Databases: Why, How, and Where, Foundations and Trends in Databases, v.1 n.4, p.379-474, April 2009

INDEX TERMS

Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.1 Logical Design
Subjects: Data models; Schema and subschema

General Terms:
Algorithms, Theory

REVIEW

"Udo Walter Lipeck : Reviewer"

This article contributes to the subject of how to translate updates of relational database views to updates of the underlying database. Following the approach in [1], the authors assume a specified view complement to remain constant so that ambi more...

Collaborative Colleagues:

Stavros S. Cosmadakis: colleagues

Christos H. Papadimitriou: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player