It is well known that the complexity of testing the correctness of an arbitrary update to a database view can be far greater than the complexity of testing a corresponding update to the main schema. However, views are generally managed according to some protocol which limits the admissible updates to a subset of all possible changes. The question thus arises as to whether there is a more tractable relationship between these two complexities in the presence of such a protocol. In this paper, this question is addressed for closed update strategies, which are based upon the constant-complement approach of Bancilhon and Spyratos. The approach is to address a more general question – that of characterizing the complexity of axiomatization of views, relative to the complexity of axiomatization of the main schema. For schemata constrained by denial or consistency constraints, that is, statements which rule out certain situations, such as the equality-generating dependencies (EGDs) or, more specifically, the functional dependencies (FDs) of the relational model, a broad and comprehensive result is obtained in a very general framework which is not tied to the relational model in any way. It states that every such schema is governed by an equivalent set of constraints which embed into the component views, and which are no more complex than the original set. For schemata constrained by generating dependencies, of which tuple-generating dependencies (TGDs) in general and, more specifically, both join dependencies (JDs) and inclusion dependencies (INDs) are examples within the relational model, a similar result is obtained, but only within a context known as meet-uniform decompositions, which fails to recapture some important situations. To address the all-important case of relational schemata constrained by both FDs and INDs, a hybrid approach is also developed, in which the general theory regarding denial constraints is blended with a focused analysis of a special but very practical subset of the INDs known as fanout-free unary inclusion dependencies (fanout-free UINDs), to obtain results parallel to the above-mentioned cases: every such schema is governed by an equivalent set of constraints which embed into the component views, and which are no more complex than the original set. In all cases, the question of view update complexity is then answered via a corollary to this main result.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases (Addison-Wesley, 1995).
J. Adámek, H. Herrlich and G. Strecker, Abstract and Concrete Categories (Wiley-Interscience, 1990).
F. Bancilhon and N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems 6 (1981) 557–575.
C. Beeri and M.Y. Vardi, Formal systems for tuple and equality generating dependencies, SIAM Journal on Computing 13(1) (1984) 76–98.
C. Beeri and M.Y. Vardi, A proof procedure for data dependencies, Journal of the Association for Computing Machinery 31(4) (1984) 718–741.
A.K. Chandra and M.Y. Vardi, The implication problem for functional and inclusion dependencies is undedidable, SIAM Journal on Computing 14 (1985) 671–677.
S. Cosmadakis, P.C. Kannelakis and M.Y. Vardi, Polynomial-time implication problems for unary inclusion dependencies, Journal of the Association for Computing Machinery 37(1) (1990) 15–46.
S. Cosmadakis and C. Papadimitriou, Updates of relational views, Journal of the Association for Computing Machinery 31 (1984) 742–760.
B.A. Davey and H.A. Priestly, Introduction to Lattices and Order, 2nd edition (Cambridge University Press, 2002).
R. Elmasri and S.B. Navathe, Fundamentals of Database Systems, 4th edition (Pearson Education, 2004).
R. Fagin, Horn clauses and database dependencies, Journal of the Association for Computing Machinery 29(4) (1982) 952–985.
R. Fagin and M.Y. Vardi, Armstrong databases for functional and inclusion dependencies, Information Processing Letters 16 (1983) 13–19.
J.N., Foster, M.B. Greenwald, J.T. Moore, B.C. Pierce and A. Schmitt, Combinators for Bi-Directional Tree Transformations: A Linguistic Approach to the View Update Problem, Technical Report MS-CIS-04-15, Department of Computer Science, University of Pennsylvania, 2004. to appear in POPL 2005.
J. Grant and B.E. Jacobs, On the family of generalized dependency constraints, JACM 29(4) (1982) 986–997.
S.J. Hegner, 1990, Foundations of canonical update support for closed database views, in: ICDT'90, Third International Conference on Database Theory, eds. S. Abiteboul and P.C. Kanellakis (Paris, France), pp. 422–436, December.
S.J. Hegner, Some open problems on view axiomatization, Bulletin of the EATCS 40 (1990) 496–498.
S.J. Hegner, Characterization of desirable properties of general database decompositions, Annals of Mathematics and Artificial Intelligence 7 (1993) 129–195.
S.J. Hegner, Unique complements and decompositions of database schemata, Journal of Computer and System Sciences 48(1) (1994) 9–57.
S.J. Hegner, 2002, Uniqueness of update strategies for database views, in: Foundations of Information and Knowledge Systems: Second International Symposium, FoIKS 2002, Salzau Castle, Germany, February 2002, Proceedings, pp. 230–249.
S.J. Hegner, An order-based theory of updates for database views, Annals of Mathematics and Artificial Intelligence 40 (2004) 63–125.
S.J. Hegner, The relative complexity of updates for a class of database views, in: Foundations of Information and Knowledge Systems: Third International Symposium, FoIKS 2004, Wilehminenberg Castle, Austria, February 17–20, 2004, Proceedings, Vol. 2942 of Lecture Notes in Computer Science, eds. D. Seipel and J.M. Turull–Torres, (2004) pp. 155–175.
E. Horowitz, S. Sahni and S. Rajasekaran, Computer Algorithms (Computer Science, 1998).
R. Hull, Finitely specifiable implicational dependency families, Journal of the Association for Computing Machinery 31(2) (1984) 210–226.
B.E. Jacobs, A.R. Aronson and A.C. Klug, On interpretations of relational languages and solutions to the implied constraint problem, ACM Transactions on Database Systems 7(2) (1982) 291–315.
J. Lechtenbörger and G. Vossen, On the computation of relational view components, ACM Transactions on Database Systems 28 (2003) 175–208.
J. Paredaens, P. De Bra, M. Gyssens and D. Van Gucht, The Structure of the Relational Database Model (Springer, 1989).
B. Thalheim, Dependencies in Relational Databases, Vol. 126 of Teubner-Texte zur Mathematik (Teubner, 1991).
K. Wang and M.H. Graham, Constant-time maintainability: A generalization of independence, ACM Transactions on Database Systems 17(2) (1992) 201–246.
Author information
Authors and Affiliations
Corresponding author
Additional information
Parts of this paper are based upon work reported in [21].
Rights and permissions
About this article
Cite this article
Hegner, S.J. The complexity of embedded axiomatization for a class of closed database views. Ann Math Artif Intell 46, 38–97 (2006). https://doi.org/10.1007/s10472-005-9013-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-005-9013-y