vldb_1995_elementary.txt

利用lwp：：get写的

(2) The search space for bypass plans is quite large.
Hence, partial exploration strategies still resulting in sufficiently efficient plans have to be developed.
(3) Since the complement of a join can be very large, those cases where the complement can be restricted to the complement of the semijoin have to be detected.
We attack all three problems.
Especially, we present an algorithm generating the optimal bypass plan andone algorithm producing near optimal plans exploring the search space onlypartially.
As soon as disjunctions occur, bypassing results in savings.
Since the join operator is often more expensive than the selection, the savings for bypassing joins are even higher than those for selections only.
We give a quantitative assessment of these savings on the basis of some example queries.
Further, we evaluate the performance of the two bypass plan generating algorithms.</abstract></paper><paper><title>Coloring Away Communication in Parallel Query Optimization.</title><author><AuthorName>Waqar Hasan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Rajeev Motwani</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Prototyping Bubba, A Highly Parallel Database System.</name><name>Scheduling Problems in Parallel Query Optimization.</name><name>Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins.</name><name>Distributed Databases: Principles and Systems.
 McGraw-Hill Book Company 1984, ISBN 0-07-010829-3</name><name>Parallel Database Systems: The Future of High Performance Database Systems.</name><name>GAMMA - A High Performance Dataflow Database Machine.</name><name>The Complexity of Multiway Cuts (Extended Abstract).</name><name>Parallelism and its Price: A Case Study of NonStop SQL/MP.</name><name>Query Optimization for Parallel Execution.</name><name>The Cost of Messages.</name><name>Including the Load Balancing Issue in the Optimization of Multi-way Join Queries for Shared-Nothing Database Computers.</name><name>Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism.</name><name>Optimization of Parallel Query Execution Plans in XPRS.</name><name>Optimization of Multi-Way Join Queries for Parallel Execution.</name><name>Principles of Distributed Database Systems.
 Prentice-Hall 1991, ISBN 0-13-715681-2</name><name>Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches.</name><name>Access Path Selection in a Relational Database Management System.</name><name>Optimizing Multi-Join Queries in Parallel Relational Databases.</name><name>Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned.</name><name>Multi-Join Optimization for Symmetric Multiprocessors.</name><name>Parallel Database Systems: Open Problems and New Issues.</name><name>Distributed Query Processing.</name><name>Parallel Query Processing in DBS3.</name></citation><abstract>We address the problem of finding parallel plans for SQL queries using thetwo-phase approach of join ordering and query rewrite (JOQR) followed by parallelization.
We focus on the JOQR phase and develop optimization algorithms that account for communication as well as computation costs.
Using a model based on representing the partitioning of data as a color, we devise an efficient algorithm for the problem of choosing the partitioning attributes in a query tree so as to minimize total cost.
We extend our model and algorithm to incorporate the interaction of data partitioning with conventional optimization choices such as access methods and strategies for computing operators.
Our algorithms apply to queries that include operators such as grouping, aggregation, intersection and set difference in addition to joins.</abstract></paper><paper><title>The Fittest Survives: An Adaptive Approach to Query Optimization.</title><author><AuthorName>Hongjun Lu</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Kian-Lee Tan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Son Dao</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Optimization of Dynamic Query Evaluation Plans.</name><name>Implementation Techniques for Main Memory Database Systems.</name><name>The EXODUS Optimizer Generator.</name><name>Randomized Algorithms for Optimizing Large Join Queries.</name><name>Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization.</name><name>Parametric Query Optimization.</name><name>The Optimization of Queries in Relational Databases.
Ph.D. thesis,  Case Western Reserve University 1980</name><name>Extending the Search Strategy in a Query Optimizer.</name><name>Measuring the Complexity of Join Enumeration in Query Optimization.</name><name>An Architecture for Query Optimization.</name><name>Access Path Selection in a Relational Database Management System.</name><name>Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines.</name><name>Optimization of Large Join Queries.</name><name>Join Processing in Database Systems with Large Main Memories.</name><name>Multi-Join Optimization for Symmetric Multiprocessors.</name><name>A Note on the Strategy Space of Multiway Join Query Optimization Problem in Parallel Systems.</name></citation><abstract>Traditionally, optimizers are "programmed" to optimize queries following aset of build- in procedures.
However, optimizers should be robust to its changing environment to generate the fittest query execution plans.
To realize adaptiveness, we propose and design an adaptive optimizer with two features.
First, the search space and search strategy of the optimizer can be tuned by parameters to allow the optimizer to pick the one that fits best duringthe optimization process.
Second, the optimizer features a "learning" capability for canned queries that allows existing plans to be incrementally replaced by "fitter" ones.
An experimental study on large multi- join queries based on an analytical model is used to demonstrate the effectiveness of such an approach.</abstract></paper><paper><title>Type Classification of Semi-Structured Documents.</title><author><AuthorName>Markus Tresch</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Neal Palmer</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Allen Luniewski</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Classification and Regression Trees.
 Wadsworth 1984, ISBN 0-534-98053-8</name><name>From Structured Documents to Novel Query Facilities.</name><name>Optimizing Queries on Files.</name><name>Using IR Techniques for Text Classification in Document Analysis.</name><name>Classification Algorithms.
 John Wiley 1985, ISBN 0-471-84799-2</name><name>A Sequential Algorithm for Training Text Classifiers.</name><name>Internet Resource Discovery Services.</name><name>C4.5: Programs for Machine Learning.</name><name>Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer.
 Addison-Wesley 1989, ISBN 0-201-12227-8</name><name>SPIDER: A Multiuser Information Retrieval System for Semistructured and Dynamic Data.</name><name>Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994.
 ACM Press 1994</name><name>The Rufus System: Information Organization for Semi-Structured Data.</name><name>A Vector Space Model for Automatic Indexing.</name><name>Information Retrieval.
 Butterworth 1979, ISBN 0-408-70929-4</name><name>A Framework for Effective Retrieval.</name></citation><abstract>Semi-structured documents (e.g. journal articles, electronic mail, television programs, mail order catalogs, ...) are often not explicitly typed; the only available type information is the implicit structure. An explicit type, however, is needed in order to apply object- oriented technology, like type-specific methods.
In this paper, we present an experimental vector space classifier for determining the type of semi-structured documents. Our goal was to design a high-performance classifier in terms of accuracy (recall and precision), speed, and extensibility.</abstract></paper><paper><title>L/MRP: A Buffer Management Strategy for Interactive Continuous Data Flows in a Multimedia DBMS.</title><author><AuthorName>Frank Moser</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Achim Kraiss</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Wolfgang Klas</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1995</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Extensible Buffer Management of Indexes.</name><name>A Study of Replacement Algorithms for Virtual-Storage Computer.</name><name>An Evaluation of Buffer Management Strategies for Relational Database Systems.</name><name>A Object Oriented Architecture For Multimedia Information Systems.</name><name>Operating Systems Theory.
 Prentice-Hall 1973</name><name>An Approximate Analysis of the LRU and