|
 ABSTRACT
In relational databases a view definition is a query against the database, and a view materialization is the result of applying the view definition to the current database A view materialization over a database may change as relations in the database undergo modificationsIn this paper a mechanism is proposed in which the view is materialized at all times The problem which this mechanism addresses is how to quickly update the view in response to database changes A structure is maintained which provides information useful in minimizing the amount of work caused by updatesMethods are presented for handling both general databases and the much simpler tree databases (also called acyclic database) In both cases adding or deleting a tuple can be performed in polynomial time For tree databases the degree of the polynomial is independent of the schema structure while for cyclic databases the degree depends on the schema structure The cost of a sequence of tuple additions (deletions) is also analyzed
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
|
|
 |
2
|
|
| |
3
|
Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, May 11-13, 1981, Milwaukee, Wisconsin, United States
[doi> 10.1145/800076.802489]
|
| |
4
|
|
| |
5
|
{BG} Bernstein, P A, and N Goodman, "The Power of Natural Semijoins", SIAM J of Comput, 10 (4), November 1981
|
| |
6
|
{Fag} Fagin, R, "Types of Acyclicity for Hypergraphs and Relational Database Systems", Research Report RJ3330, IBM Research Laboratory, San Jose, CA, November 1981
|
| |
7
|
{FMU} Fagin, R, A O Mendelzon, and J D Ullman, "A Simplified Universal Relation Assumption and Its Properties", Technical Report RJ2900, IBM, San Jose, CA, 1980
|
| |
8
|
{Gra} Graham, M H, On the Universal Relation, Technical Report, University of Toronto, September 1979
|
| |
9
|
|
| |
10
|
{GS2} Goodman, N, and O Shmueli, "The Structure of Database Schemas" To appear in J ACM
|
| |
11
|
|
| |
12
|
|
| |
13
|
{GS5} Goodman, N, and O Shmueli, "NP-Complete Problems Simplified on Tree Schemas", To appear in Acta Informatica
|
| |
14
|
Nathan Goodman , Oded Shmueli , Y. C. Tay, GYO reductions, canonical connections, tree and cyclic schemas and tree projections, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia
[doi> 10.1145/588058.588089]
|
| |
15
|
{Hul} Hull, R, "Acyclic Join Dependencies and Database Projections", in Proc XP2, State College, PA, June 1981
|
| |
16
|
|
| |
17
|
{MU2} Maier, D, and J D Ullman, "Maximal Objects and the Semantics of Universal Relation Databases", Technical Report #80-016, Dept of Comp Science, SUNY at Stonybrook, November 1980
|
| |
18
|
|
| |
19
|
{TY} Tarjan, R E, and M Yannakakis, "Simple Linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs", unpublished manuscript, March 1982
|
| |
20
|
{Yan} Yannakakis, M, "Algorithms for Acyclic Database Schemes", in Proc VLDB, 82--94, Cannes, France, September 1981
|
| |
21
|
{YO} Yu, C T, and M.Z Ozsoyoglu, "An Algorithm for Tree-Query Membership of a Distributed Query," in Proc COMP-SAC79, IEEE Comp Society, November 1979
|
CITED BY 30
|
|
K. Selçuk Candan , Divyakant Agrawal , Wen-Syan Li , Oliver Po , Wang-Pin Hsiung, View invalidation for dynamic content caching in multitiered architectures, Proceedings of the 28th international conference on Very Large Data Bases, p.562-573, August 20-23, 2002, Hong Kong, China
|
|
|
Eugene Inseok Chong , Jagannathan Srinivasan , Souripriya Das , Chuck Freiwald , Aravind Yalamanchi , Mahesh Jagannath , Anh-Tuan Tran , Ramkumar Krishnan , Richard Jiang, A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
|
|
|
Eugene Inseok Chong , Jagannathan Srinivasan , Souripriya Das , Chuck Freiwald , Aravind Yalamanchi , Mahesh Jagannath , Anh-Tuan Tran , Ramkumar Krishnan , Richard Jiang, A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B+-trees, ACM SIGMOD Record, v.32 n.2, June 2003
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sanjeev Khanna , Rajeev Motwani , Randall H. Wilson, On certificates and lookahead in dynamic graph problems, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.222-231, January 28-30, 1996, Atlanta, Georgia, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S. B. Davidson , J. Crabtree , B. P. Brunk , J. Schug , V. Tannen , G. C. Overton , C. J. Stoeckert, Jr., K2/Kleisli and GUS: experiments in integrated access to genomic data sources, IBM Systems Journal, v.40 n.2, p.512-531, February 2001
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf