skip to main content
article
Free Access

Updates of Relational Views

Authors Info & Claims
Published:20 September 1984Publication History
First page image

References

  1. 1 ARMSTRONG, W. W.Dependency structures of database relationships. In Proceedings oflFIP 74. North-Holland, Amsterdam, 1974, pp. 580-583.Google ScholarGoogle Scholar
  2. 2 ASTRAHAN, M. M., BLASGEN, M. W., CHAMBERLIN, D. D., EswA~rq, K. P., GgxY, J. N., Grurrnms, P.P., KING, W. F., Lomb, R. A., MC_.JoNgs, P. R., M~HL, J. W., PtrrZOLU, G. R., TIO.IG~R, 1. L., WAD~, B. W., ^r~D WATSON, V. System R: Relational approach to database management. ACM Trans. Database Syst. 1, 2 (June 1976), 97-t37. Google ScholarGoogle Scholar
  3. 3 BANCILHON, F., AND SPYRATOS, N. Update semantics of relational views. ACM Trans. Database Syst 6, 4 (Dec. 1981), 557-575. Google ScholarGoogle Scholar
  4. 4 BEFatl, C., AND BERNSTEIN, P. A. Computational problems related to the design of normal form relational schemas. ACM Trans Database Syst. 4, 1 (Mar. 1979), 30-59. Google ScholarGoogle Scholar
  5. 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.Google ScholarGoogle Scholar
  6. 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.Google ScholarGoogle Scholar
  7. 7 BEERI, C., AND VARDI, M. Y.On acyclic database decompositions. Inf. Control, to be pubfished.Google ScholarGoogle Scholar
  8. 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.Google ScholarGoogle Scholar
  9. 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.Google ScholarGoogle Scholar
  10. 10 CODD, E. 17. A relational model for large shared data banks. Commun. ACM 13, 6 (June 1970) 377-387. Google ScholarGoogle Scholar
  11. 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.Google ScholarGoogle Scholar
  12. 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.Google ScholarGoogle Scholar
  13. 13 CODD, E. F.Extending the database relational model to capture more meaning, ACM Trans. Database Spst. 4, 4 (Dec. 1979), 397-434. Google ScholarGoogle Scholar
  14. 14 CODASYL Data Base Task Group, April 71 Report. ACM, New York, 1971.Google ScholarGoogle Scholar
  15. 15 COOK, S.A.The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACMSymposium on the Theory of Computing (Shaker Heights, Ohio, May 3-5). ACM, New York, 1971, pp. 151-158. Google ScholarGoogle Scholar
  16. 16 DATE, C.L An Introduction to Database @stems. Addison Wesley, Reading, Mass., 1977. Google ScholarGoogle Scholar
  17. 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.Google ScholarGoogle Scholar
  18. 18 FAGIN, R.Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 262--278. Google ScholarGoogle Scholar
  19. 19 FAoN, R., ULLMAN, J.D., AND VARDI, M.Y. On the semantics of updates in databases. In Proceedings of the 2nd ACM SIGACT.SIGMOD Symposium on Prmciples of Database Systems, 1983. Google ScholarGoogle Scholar
  20. 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.Google ScholarGoogle Scholar
  21. 21 GAREY, M. R. AND JOHNSON, D. S.Computers and lntractabditF, A Gutde to the Theory of NP- Completeness. Freeman, San Francisco, Calif. 1979. Google ScholarGoogle Scholar
  22. 22 IMS/VS publications GH20-1260, SH20-9025, SH20-9026, SH20-9027. IBM, White Plmns, New York, 1978.Google ScholarGoogle Scholar
  23. 23 KANELLAK|S, P. C., COSMADAKIS~ S.S., AND VARDI, M.Y. Unary inclusion dependencies have polynomial time inference problems. In Proceedings of the 15th .4CM Symposium on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp. 264-277. Google ScholarGoogle Scholar
  24. 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.Google ScholarGoogle Scholar
  25. 25 blAlER, D., MENDELT_DN, A. O., aND SAGIV, Y.TEsting implications of data dependencies. ACM Trans. Database Syst. 4, 4 (Dec. 1979), 455-469. Google ScholarGoogle Scholar
  26. 26 MAER, D., SaG)v, Y., ariD YANNAKAKI$, M.On the complexity of testing implicanons of funeUonal and join dependencies. J. ACM 28, 4 (Oct. 1981), 680-695. Google ScholarGoogle Scholar
  27. 27 RISSAN~N, J.Independent components of relations. ACM Trans. Database Syst. 2, 4 {Dee. 1977), 3i7-325. Google ScholarGoogle Scholar
  28. 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.Google ScholarGoogle Scholar
  29. 29 ROWE, L., AND STONEBRAKER, M.Manuscript. Univ. Cal., Berkeley, Berkeley, Calif., 1979.Google ScholarGoogle Scholar
  30. 30 SAOW, Y., DELOBEL, C., STOrr PARKER, D., JR, AND FAGIN, R.An equivalence between relational database de~ndenoes and a fragment of propositional logic. Z ACM 28, 3 (Jiffy 1981), 435-453. Google ScholarGoogle Scholar
  31. 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. Google ScholarGoogle Scholar
  32. 32 STOCKMEYER, L. J.The polynomial time hierarchy. Theor. Comput. Sci. 3, 1 (1976), 1-22.Google ScholarGoogle Scholar
  33. 33 STONEBRAKER, M., WONt:;, E., KREpS, E, AND HELD, G.The design and implementation of INGRES. ACM Trans. Database Syst. I, 3 (Sept. 1976), 189-222. Google ScholarGoogle Scholar
  34. 34 TODD, S. J. P.The Peterlee relational test vehicle--A system overview. IBM SFst. J. 15, 4 (1976), 285-308.Google ScholarGoogle Scholar
  35. 35 ULLMAN, J. D.Princtples of Database Systems. Computer Science Press, Rockville, Md., 1980. Google ScholarGoogle Scholar
  36. 36 ULLMAN, J. D.The U.R. strikes back. In Proceedings of the ACM Symposium on Prmciples of Database Systems, (Los Angeles, Calif. Mar. 29.-30). ACM, New York, 1982, pp. 10--22. Google ScholarGoogle Scholar
  37. 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.Google ScholarGoogle Scholar
  38. 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.Google ScholarGoogle Scholar
  39. 39 WRATHALL, C.Complete sets and the polynomial-time hierarchy. Theor. Comput. Sci. 3, 1 (1976), 23-33.Google ScholarGoogle Scholar
  40. 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.Google ScholarGoogle Scholar
  41. 41 ZANIOLO, C.Database relations with null values. In Proceedings of the ACM Sympostum on Principles of Database Systems (Los Angeles, Calif., Mar. 29-31). ACM, New York, 1982, pp. 27- 33. Google ScholarGoogle Scholar
  42. 42 ZLOOF, M. M.Query-by-Example: A data base language. IBM Syst. J. 16, 4 (1977), 324-343.Google ScholarGoogle Scholar

Index Terms

  1. Updates of Relational Views

            Recommendations

            Reviews

            Udo Walter Lipeck

            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 ambiguous translations are avoided. They give conditions for the translatability of updates and analyze the complexity of tests for these conditions. Here, views are only projections of a single base relation; as integrity constraints, only functional dependencies are considered. Complementary projections of a relation turn out to be a decomposition with lossless join. On this basis, translatability of an insertion into a view is characterized. The central consistency condition can be tested by chasing algorithms [2] in time cubic in the number of view tuples; this result is improved by two stronger tests for only sufficient conditions. An analysis of the inherent complexity shows that running time cannot be reduced substantially. In addition, the problem of determining suitable complements dynamically is proved to be NP-hard. Finally, the main results are extended to deletions and replacements in a straightforward way. Thus, the general idea in [1] has been elaborated for a very simple application case. The rather severe conditions and high complexities obtained, however, do not give any hint at a practical methodology.

            Access critical reviews of Computing literature here

            Become a reviewer for Computing Reviews.

            Comments

            Login options

            Check if you have access through your login credentials or your institution to get full access on this article.

            Sign in

            Full Access

            • Published in

              cover image Journal of the ACM
              Journal of the ACM  Volume 31, Issue 4
              Oct. 1984
              238 pages
              ISSN:0004-5411
              EISSN:1557-735X
              DOI:10.1145/1634
              Issue’s Table of Contents

              Copyright © 1984 ACM

              Publisher

              Association for Computing Machinery

              New York, NY, United States

              Publication History

              • Published: 20 September 1984
              Published in jacm Volume 31, Issue 4

              Permissions

              Request permissions about this article.

              Request Permissions

              Check for updates

              Qualifiers

              • article

            PDF Format

            View or Download as a PDF file.

            PDF

            eReader

            View online with eReader.

            eReader