Abstract
Previous research on materialized views has primarily been in the context of flat relational databases—materialized views defined in terms of one or more flat relations. This paper discusses a broader class of view definitions-materialized views defined over a nested data model such as the nested relational model or an object-oriented data model. An attribute of a tuple deriving the view can be a reference (i.e., a pointer) to a nested relation, with arbitrary levels of nesting possible. The extended capability of this nested data model, together with materialized views, simplifies data modeling and gives more flexibility.
Simple extensions of standard view maintenance techniques to the nested model would do too much work for maintenance: a change in a nested set would re-process the entire nested set, not just the changed parts. We show how existing incremental maintenance algorithms can be extended to maintain the views without performing this additional work.
We describe the implementation of these techniques in the SWORD interface to the Ode database system. The implementation is based on the representation of nested structures by classes and the use of an SQL-like language to define materialized views. We outline the data structures and algorithms used in the implementation and examine performance. This is one of the first pieces of work to explore the applicability of materialized views over complex objects.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul and N. Bidoit. Non first normal form relations to represent hierarchically organized data. In Proc. PODS, 1984.
M. E. Adiba and Bruce Lindsay. Database snapshots. In Proc. VLDB, 1980.
R. Agrawal and N. Gehani. Ode (object database and environment): the language and the data model. In Proc. SIGMOD, 1989.
H. Arisawa, K. Moriya, and T. Miura. Properties on non-first-normal-form relational databases. In Proc. VLDB, 1983.
F. Bancilhon, P. Richard, and M. Scholl. On line processing of compacted relations. In Proc. VLDB, 1982.
E. Bertino. Query Processing for Advanced Database Systems, chapter A survey of indexing techniques for object-oriented databases. Morgan Kaufmann, 1994.
E. Bertino and W. Kim. Indexing techniques for queries on nested objects. IEEE TKDE, pages 196–214, June 1989.
J. A. Blakeley, P. Larson, and F. W. Tompa. Efficiently Updating Materialized Views. In Proc. SIGMOD, May 1986.
Peter O. Buneman and Eric K. Clemons.Efficiently monitoring relational databases. ACM TODS, 4(3):368–382, September 1979.
S. Ceri and J. Widom. Deriving production rules for incremental view maintenance. In Proc. VLDB, pages 108–119, 1991.
W. Chen, M. Kifer, and D. Warren. HiLog: A first order semantics for higher-order logic programming constructs. In Proc. N. American Logic Prog. Conf., June 1989.
L. Colby, T. Griffin, L. Libkin, I. Mumick, and H. Trickey. Algorithms for deferred view maintenance. In Proc. SIGMOD, 1996.
L. Colby, A. Kawaguchi, D. Lieuwen, I. Mumick, and K. Ross. Implementing materialized views, 1996. Unpublished manuscript.
L. Colby, A. Kawaguchi, D. Lieuwen, I. Mumick, and K. Ross. Supporting multiple view maintenance policies. In Proc. SIGMOD, May 1997.
P. Dadam, K. Kuespert, F. Andersen, H. Blanken, R. Erbe, J. Guenauer, V. Lum, P. Pistor, and G. Walch. A DBMS prototype to support extended NF2 relations: An integrated view on flat tables and hierarchies. In Proc. VLDB, 1986.
T. Griffin and L. Libkin. Incremental maintenance of views with duplicates. In Proc. SIGMOD, 1995.
A. Gupta, I. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proc. SIGMOD, 1993.
R. Haskin and R. Lorie. On extending the functions of a relational database system. In Proc. SIGMOD, 1982.
G. Jaeshke and H. Sheck. Remarks on the algebra of non-first-normal-form relational database. In Proc. PODS, 1982.
B. Kähler and O. Risnes. Extended logging for database snapshots. In Proc. VLDB, pages 389–398, 1987.
A. Kawaguchi, D. Lieuwen, I. Mumick, D. Quass, and K. Ross. Concurrency control theory for deferred materialized views. In Proc. ICDT, January 1997.
A. Kawaguchi, D. Lieuwen, I. Mumick, and K. Ross. View maintenance in nested data models. In Proc. Worshop on Materialized Views: Techniques and Applications (associated with SIGMOD96), June 1996.
B. Lindsay, L. Haas, C. Mohan, H. Pirahesh, and P. Wilms. A snapshot differential refresh algorithm. In Proc. SIGMOD, 1986.
V. Linnemann. Non first normal relations and recursive queries: An SQL-based approach. In Proc. Data. Eng., 1987.
J. Lu, G. Moerkotte, J. Schu, and V. S. Subrahmanian. Efficient maintenance of materialized mediated views. In Proc. SIGMOD, 1995.
D. Maier and J. Stein. Indexing in an object-oriented DBMS. In Workshop on OODB Sys., 1986.
A. Makinouch. A consideration of normal form of non-necessarily normalized relations in the relational data model. In Proc. VLDB, 1977.
I. Mumick and K. Ross. Noodle: A language for declarative querying in an object-oriented database. In Proc. DOOD, 1993.
I. Mumick, K. Ross, and S. Sudarshan. Design and implementation of the SWORD declarative object-oriented database system, 1993. Unpublished Manuscript.
P. Pistor and F. Andersen. Designing a generalized NF2 model with an SQL-type language interface. In Proc. VLDB, 1986.
Xiaolei Qian and Gio Wiederhold. Incremental recomputation of active relational expressions. IEEE TKDE, 3(3):337–341, 1991.
K. Ross. Relations with relation names as arguments: Algebra and calculus. In Proc. PODS, 1992.
M. Roth, H. Korth, and D Batory. SQL/NF: A query language for-1NF relational databases. Information Systems, 12(1):99–114, 1987.
M. Scholl, H. Paul, and H. Schek. Supporting flat relations by a nested relational kernel. In Proc. VLDB, 1987.
A. Segev and J. Park. Updating distributed materialized views. IEEE TKDE, 1(2):173–184, June 1989.
E. Shekita and M. Carey. Performance enhancement through replication in an object-oriented DBMS. In Proc. SIGMOD, 1989.
Oded Shmueli and A. Itai. Maintenance of Views. In Proc. SIGMOD, 1984.
L. Sterling and E. Shapiro. The Art of Prolog. Advanced Programming Techniques. MIT Press, Cambridge, MA, 1986.
S. Thomas and P. Fischer. Nested relational structures. In P. Kanellakis, editor, The Theory of Databases. JAI Press, 1986.
Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom. View maintenance in a warehousing environment. In Proc. SIGMOD, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kawaguchi, A., Lieuwen, D., Mumick, I., Ross, K. (1998). Implementing incremental view maintenance in nested data models. In: Cluet, S., Hull, R. (eds) Database Programming Languages. DBPL 1997. Lecture Notes in Computer Science, vol 1369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-64823-2_12
Download citation
DOI: https://doi.org/10.1007/3-540-64823-2_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64823-9
Online ISBN: 978-3-540-68534-0
eBook Packages: Springer Book Archive