On generating database schemes bounded or constant-time-maintainable by extensibility | Acta Informatica Skip to main content
Springer Nature Link
Log in

On generating database schemes bounded or constant-time-maintainable by extensibility

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

Under the weak instance model, determining whether a class of database schemes is bounded (with respect to dependencies or with respect to consistency) is fundamental for the analysis of the behavior of the class of database schemes with respect to query processing and updates. However, proving that a class of database schemes is bounded seems to be very difficult even for restricted cases. To resolve this problem, we need to develop techniques or to explore other ideas for characterizing bounded database schemes. In particular, the idea of generating bounded database schemes is completely unexplored. In this paper, we give a formal methodology for the generation of bounded database schemes using a new technique called extensibility. This methodology can also be used to generate constant-time-maintainable database schemes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho, A.V., Beeri, C., Ullman, J.D.: The theory of joins in relational databases. ACM TODS 4, 297–314 (1979)

    Google Scholar 

  2. Aho, A.V., Sagiv, Y., Ullman, J.D.: Equivalence of relational expressions. SIAM J. Comput. 8, 435–454 (1979)

    Google Scholar 

  3. Atzeni, P., Chan, E.P.F.: Efficient query answering in the representative instance approach. Proc. ACM PODS 1985. pp. 181–188. New York: ACM 1984

    Google Scholar 

  4. Beeri, C., Vardi, M.Y.: A proof procedure for data dependencies. J Assoc. Comput. Mach. 31, 718–741 (1984)

    Google Scholar 

  5. Chan, E.P.F.: Optimal computation of total projections with unions of simple chase join expressions. Proc. ACM SIGMOD 1984. pp. 149–163. New York: ACM 1984

    Google Scholar 

  6. Chan, E.P.F., Hernández, H.J.: On the desirability of γ-acyclic BCNF database schemes. ICDT'86: International Conference on Database Theory. Lecture Notes in Computer Science. Vol. 243, pp. 105–122. Berlin Heidelberg New York: Springer 1986

    Google Scholar 

  7. Chan, E.P.F., Hernández, H.J.: Testing unboundedness of database schemes and functional dependencies. Inform. Proc. Lett. (1988, to appear)

  8. D'Atri, A., Moscarini, M.: Recognition algorithms and design methodologies for acyclic database schemes. Advances in Computing Research. Vol. 3, pp. 43–67. New Haven: JAI Press Inc. 1986

    Google Scholar 

  9. Fagin, R.: Horn clauses and database dependencies. J. Assoc. Comput. Mach. 29, 952–983 (1982)

    Google Scholar 

  10. Graham, M.H., Mendelzon, A.O.: The power of canonical queries. Unpublished manuscript, September 1983.

  11. Graham, M.H., Mendelzon, A.O., Vardi, M.Y.: Notions of dependency satisfaction. J. Assoc. Comput. Mach. 33, 105–129 (1986)

    Google Scholar 

  12. Graham, M.H., Vardi, M.Y.: On the complexity and axiomatizability of consistent database states. Proc. ACM PODS 1984. pp. 281–289. New York: ACM 1984

    Google Scholar 

  13. Graham, M.H., Wang, K.: Constant Time Maintenance or The Triumph of the fd. Proc. ACM PODS 1986. pp. 202–216. New York: ACM 1986

    Google Scholar 

  14. Graham, M.H., Yannakakis, M.: Independent database schemas. J. Comput. Syst. Sci. 28, 121–141 (1984)

    Google Scholar 

  15. Honeyman, P.: Testing satisfaction of functional dependencies. J. Assoc. Comput. Mach. 29, 668–677(1982)

    Google Scholar 

  16. Ito, M., Iwasaki, M., Kasami, T.: Some results on the representative instance in relational databases. SIAM J. Comput. 14, 334–354 (1985)

    Google Scholar 

  17. Mendelzon, A.O.: Database states and their tableaux. ACM TODS 9, 264–282 (1984)

    Google Scholar 

  18. Maier, D., Mendelzon, A.O., Sagiv, Y.: Testing implications of data dependencies. ACM TODS 4, 455–469 (1979)

    Google Scholar 

  19. Maier, D., Rozenshtein, D., Warren, D.S.: Window functions. In: Advances in computing research. Vol. 3, pp. 213–246. New Haven: JAI Press Inc. 1986

    Google Scholar 

  20. Maier, D., Ullman, J.D., Vardi, M.Y.: On the foundations of the universal relation model. ACM TODS 9, 283–308 (1984)

    Google Scholar 

  21. Sagiv, Y.: Can we use the universal instance assumption without using nulls? Proc. ACM SIGMOD 1981. pp. 108–120. New York: ACM 1981

    Google Scholar 

  22. Sagiv, Y.: A characterization of globally consistent databases and their correct access paths. ACM TODS 8, 266–286 (1983)

    Google Scholar 

  23. Sagiv, Y.: Evaluation of queries in independent database schemes. Unpublished manuscript, 1984

  24. Ullman, J.D.: Principles of database systems. 2nd Edn. Rockville: Computer Science Press 1982

    Google Scholar 

  25. Yannakakis, M.: Algorithms for acyclic database schemes. Proc. VLDB 1981. pp. 82–94. Los Altos: Morgan Kaufmann 1981

    Google Scholar 

  26. Yannakakis, M., Papadimitriou, C.H.: Algebraic dependencies. J. Comput. Syst. Sci. 25, 2–41 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada

    Edward P. F. Chan

  2. Department of Computer Science, Texas A&M University, 77843-3112, College Station, Texas, USA

    Héctor J. Hernández

Authors
  1. Edward P. F. Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Héctor J. Hernández
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

An extended abstract of a preliminary version of this paper appears as “On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies” in Proc. Sixth ACM SIGACT-S1GMOD-SIGART Symposium on Principles of Database Systems, 1987, pp. 48–57. Part of the work was done while the authors were at the University of Alberta

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chan, E.P.F., Hernández, H.J. On generating database schemes bounded or constant-time-maintainable by extensibility. Acta Informatica 25, 475–496 (1988). https://doi.org/10.1007/BF00279950

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00279950

Keywords

Search

Navigation