vldb_1996_elementary.txt

利用lwp：：get写的

but unrealistic,
uniformity assumption.

In this paper, we focus on the estimation of the number of number
of quadtree blocks that a real, spatial dataset will require.
Using the the well-known Hausdorff fractal dimension,
we derive some closed formulas which allow us to predict the number of 
quadtree blocks, given some few parameters.
Using our formulas,
it is possible to predict the space overhead and the response time of linear
quadtrees/z-orderings [OM88], which are widely used in practice.
In order to verify our analytical model, we performed an 
extensive experimental investigation using several real datasets coming from 
different domains. In these experiments,
we found that our analytical model agrees well with 
our experiments as well as with older empirical observations on 2-d
[Gae95b] and 3-d [ACF+94] data.</abstract></paper><paper><title>WATCHMAN : A Data Warehouse Intelligent Cache Manager.</title><author><AuthorName>Peter Scheuermann</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Junho Shim</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Radek Vingralek</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Data Placement In Bubba.</name><name>Operating Systems Theory.
 Prentice-Hall 1973</name><name>An Evaluation of Buffer Management Strategies for Relational Database Systems.</name><name>The Implementation and Performance Evaluation of the ADMS Query Optimizer: Integrating Query Result Caching and Matching.</name><name>Principles of Database  Buffer Management.</name><name>Flexible and Adaptable Buffer Management Techniques for Database Management Systems.</name><name>``One Size Fits All'' Database Architectures Do Not Work for DDS.</name><name>Aggregate-Query Processing in Data Warehousing Environments.</name><name>Computer and Intractability: A Guide to the Theory of NP-Completeness.
 W. H. Freeman 1979, ISBN 0-7167-1044-7</name><name>Maintenance of Materialized Views: Problems, Techniques, and Applications.</name><name>The 5 Minute Rule for Trading Memory for Disk Accesses and The 10 Byte Rule for Trading Memory for CPU Time.</name><name>Practical Predicate Placement.</name><name>Implementing Data Cubes Efficiently.</name><name>Rdb/VMS: Developing the Data Warehouse.
 QED Publishing Group/John Wiley 1993, ISBN 0-471-56920-8</name><name>A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures.</name><name>A Predicate-based Caching Scheme for Client-Server Database Architectures.</name><name>Function Materialization in Object Bases: Design, Realization, and Evaluation.</name><name>Database Buffer Paging in Virtual Storage Systems.</name><name>The LRU-K Page Replacement Algorithm For Database Disk Buffering.</name><name>The ADMS Project: View R Us.</name><name>Intelligent caching and indexing techniques for relational database systems.</name><name>Solving Implication Problems in Database Applications.</name><name>Virtual Memory Transaction Management.</name><name>``Disk Cooling'' in Parallel Disk Systems.</name><name>Snowball: Scalable Storage on Networks of Workstations with Balanced Load.</name><name>Research Problems in Data Warehousing.</name></citation><abstract>Data warehouses store large volumes of data that are being used
frequently by decision support applications which involve complex
queries. Since data warehouses are updated infrequently, it becomes
desirable to cache not only query execution plans, but also the
retrieved sets of queries. In this paper we report on the design of an
intelligent cache manager for retrieved sets in a data warehousing
environment, called WATCHMAN. Our cache manager employs two novel,
complementary algorithms for cache replacement and for cache
admission. WATCHMAN aims at minimizing query response time and its
cache replacement policy swaps out entire retrieved sets of queries
instead of individual pages. The cache replacement and admission
algorithms make use of a profit metric, which considers for each
retrieved set its average rate of reference, its size, and execution
cost of the associated query. We report on a performance evaluation
based on the TPC-D and Set Query benchmarks.  These experiments show
that WATCHMAN achieves a substantial performance improvement in
decision support environment as compared to a traditional LRU
replacement algorithm.</abstract></paper><paper><title>Efficient Snapshot Differential Algorithms for Data Warehousing.</title><author><AuthorName>Wilburt Labio</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Hector Garcia-Molina</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Database Snapshots.</name><name>Copy Detection Mechanisms for Digital Documents.</name><name>Exploiting Symmetries for Low-Cost Comparison of File Copies.</name><name>Change Detection in Hierarchically Structured Information.</name><name>Seeking the Truth About ad hoc Join Costs.</name><name>The Stanford Data Warehousing Project.</name><name>A Fast Algorithm for Computing Longest Subsequences.</name><name>Extending Logging for Database Snapshot Refresh.</name><name>A Snapshot Differential Refresh Algorithm.</name><name>Query Processing in R*.</name><name>Join Processing in Relational Databases.</name><name>GLIMPSE: A Tool to Search Through Entire File Systems.</name><name>SCAM: A Copy Detection Mechanism for Digital Documents.</name><name>Join Processing in Database Systems with Large Main Memories.</name><name>Data Extraction and Transformation for the Data Warehouse.</name><name>Principles of Database  and Knowledge-Base Systems, Volume II.
 Computer Science Press 1989, ISBN 0-7167-8162-X</name><name>View Maintenance in a Warehousing Environment.</name></citation><abstract>Detecting and extracting modifications from information sources
is an integral part of data warehousing.  For unsophisticated
sources, in practice it is often necessary to infer modifications
by periodically comparing snapshots of data from the source.
Although this snapshot differential problem is closely related
to traditional joins and outerjoins, there are significant differences,
which lead to simple new algorithms.  In particular, we present algorithms
that perform (possibly lossy) compression of records.
We also present a window algorithm that works very well
if the snapshots are not ``very different.''
The algorithms are studied via analysis and an implementation of two of them;
the results illustrate the potential gains achievable with the new
algorithms.</abstract></paper><paper><title>Incremental Maintenance of Externally Materialized Views.</title><author><AuthorName>Martin Staudt</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Matthias Jarke</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Efficient Monitoring Relational Databases.</name><name>Deriving Production Rules for Incremental View Maintenance.</name><name>Improving Performance in Replicated Databases through Relaxed Coherency.</name><name>Data Integration using Self-Maintainable Views.</name><name>Maintenance of Materialized Views: Problems, Techniques, and Applications.</name><name>Maintaining Views Incrementally.</name><name>ConceptBase - A Deductive Object Base for Meta Data Management.</name><name>A Predicate-based Caching Scheme for Client-Server Database Architectures.</name><name>On the Efficient Computation of the Difference Between Concecutive Database States.</name><name>Efficient Maintenance of Materialized Mediated Views.</name><name>The Magic of Duplicates and Aggregates.</name><name>Telos: Representing Knowledge About Information Systems.</name><name>An Outline of BDGEN: A Deductive DBMS.</name><name>Managing Multiple Requirements Perspectives with Metamodels.</name><name>Principles and Techniques in the Design of ADMS&amp;#177;.</name><name>Conception et Realisation d'un sous Systeme d'Intgerite dans un SGBD Relationnel.
Ph.D. thesis,  Univerite de Paris VI 1986</name><name>Query by Class, Rule and Concept.</name><name>Implementation of Integrity Constraints and Views by Query Modification.</name><name>Principles of Database  and Knowledge-Base Systems, Volume I.
 Computer Science Press 1988, ISBN 0-7167-8158-1</name><name>Principles of Database  and Knowledge-Base Systems, Volume II.
 Computer Science Press 1989, ISBN 0-7167-8162-X</name><name>The Basis for Mediation.</name><name>View Maintenance in a Warehousing Environment.</name></citation><abstract>With the advent of the Internet, access to
database servers from autonomous clients will become
more and more popular. In this paper, we propose a
monitoring service that could be offered by such
database servers, and present algorithms for its
implementation. In contrast to published 
view maintenance algorithms, we do not assume
that the server has access to the original materialization
when computing differential view changes to be notified.
We also do not assume any
database capabilities on the client side and therefore
compute precisely the required differentials rather than
just an approximation, as is done by cache coherence
techniques in homogeneous client-server databases.
The method has been implemented in ConceptBase,
a meta data management system supporting an Internet-based
client-server architecture, and tried out in some
cooperative design applications.</abstract></paper><paper><title>Optimization of Queries with User-defined Predicates.</title><author><AuthorName>Surajit Chaudhuri</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Kyuseok Shim</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Towards on Open Architecture for LDL.</name><name>Query Optimization in the Presence of Foreign Functions.</name><name>Including Group-By in Query Optimization.</name><name>Query Optimization for Parallel Execution.</name><name>Practical Predicate Placement.</name><name>Predicate Migration: Optimizing Queries with Expensive Predicates.</name><name>Randomized Algorithms for Optimizing Large Join Queries.</name><name>Optimization of Nonrecursive Queries.</name><name>Optimizing Boolean Expressions in Object-Bases.</name><name>Extensible/Rule Based Query Rewrite Optimization in Starburst.</name><name>Access Path Selection in a Relational Database Management System.</name><name>Query Optimization in a Memory-Resident Domain Relational Calculus Database System.</name></citation><abstract>Relational databases provide the ability to
store user-defined functions and predicates
which can be invoked in SQL queries.
When evaluation of a user-defined predicate is relatively expensive,
the traditional methods of evaluating predicates as
early as possible is no longer a sound heuristic.
There are two previous approaches for optimizing such queries.
However, none of these approaches is able to guarantee
the optimal plan over the desired execution space.
We present an efficient technique that is able to
guarantee the choice of an optimal plan over the desired
execution space.
The optimization algorithm that we present has the desirable properties that
(a) it is an extension of the algorithm used by commercial
optimizers and never requires exhaustive enumeration of join ordering,