vldb_1996_elementary.txt

利用lwp：：get写的

(b) the complexity of the algorithm is bounded by a
polynomial in the number of user-defined functions and
(c) requires no special assumptions on the cost
formulas for join.
We also propose a conservative local heuristic that is
even simpler but produces nearly optimal plans.
We have implemented the algorithms
by extending a System-R style optimizer.</abstract></paper><paper><title>The Design and Implementation of a Sequence Database System.</title><author><AuthorName>Praveen Seshadri</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Miron Livny</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Raghu Ramakrishnan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Building an Object-Oriented Database System, The Story of O2.</name><name>Shoring Up Persistent Applications.</name><name>Managing Temporal Financial Data in an Extensible Database.</name><name>Client-Server Paradise.</name><name>Composite Event Specification in Active Databases: Model &amp; Implementation.</name><name>Supporting Lists in a Data Model (A Timely Approach).</name><name>Management of Sequence Data.
Ph.D. thesis,  Univ. of Wisconsin-Madison, CS Department 1996</name><name>SEQ: A Model for Sequence Databases.</name><name>Sequence Query Processing.</name><name>Logical Modeling of Temporal Data.</name><name>Inclusion of New Types in Relational Data Base Systems.</name><name>Temporal Databases: Theory, Design, and Implementation.
 Benjamin/Cummings 1993, ISBN 0-8053-2413-5</name><name>TSQL2 Language Specification.</name><name>Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance.</name><name>Temporal Modules: An Approach Toward Federated Temporal Databases.</name></citation><abstract>This paper discusses the design and implementation of SEQ,
a database system with support for sequence data. 
SEQ models a sequence as an ordered collection
of records, and supports a declarative sequence query language
based on an algebra of query operators, thereby permitting
algebraic query optimization and evaluation.
SEQ has been built as a component of the PREDATOR database
system that provides support for relational and other
kinds of complex data as well.
 here are three distinct contributions made in this paper.
(1) We describe the specification of sequence queries using
the SEQUIN query language.
(2) We quantitatively demonstrate the importance of various storage and
optimization techniques by studying their effect on performance.
(3) We present a novel nested design paradigm used in PREDATOR to 
combine sequence and relational data.</abstract></paper><paper><title>EROC: A Toolkit for Building NEATO Query Optimizers.</title><author><AuthorName>William J. McKenna</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Louis Burger</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Chi Hoang</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Melissa Truong</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>ODE (Object Database and Environment): The Language and the Data Model.</name><name>Experiences Building the Open OODB Query Optimizer.</name><name>Query Processing in NonStop SQL.</name><name>Introduction to Algorithms.
 The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0</name><name>Advanced C++: Programming Syles and Idioms.
 Addison-Wesley 1992, ISBN 0-201-54855-0</name><name>Including Group-By in Query Optimization.</name><name>Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers.</name><name>The EXODUS Optimizer Generator.</name><name>Aggregate-Query Processing in Data Warehousing Environments.</name><name>Fast, Randomized Join-Order Selection - Why Use Transformations?</name><name>The Volcano Optimizer Generator: Extensibility and Efficient Search.</name><name>Rule-Based Query Optimization in Extensible Database Systems.
Ph.D. thesis,  Univ. of Wisconsin-Madison 1987</name><name>The Cascades Framework for Query Optimization.</name><name>Optimization of Nested SQL Queries Revisited.</name><name>Predicate Migration: Optimizing Queries with Expensive Predicates.</name><name>Randomized Algorithms for Optimizing Large Join Queries.</name><name>On Optimizing an SQL-like Nested Query.</name><name>Query Optimization by Predicate Move-Around.</name><name>Extending the Search Strategy in a Query Optimizer.</name><name>Invited Project Review: Industrial-strength parallel query optimization: issues and lessons.</name><name>Efficient Search in Extensible Query Optimization: The Volcano Optimizer Generator.
Ph.D. thesis,  University of Colorado-Boulder 1993</name><name>Improved Unnesting Algorithms for Join Aggregate SQL Queries.</name><name>Measuring the Complexity of Join Enumeration in Query Optimization.</name><name>Functional Programming and Parallel Graph Rewriting.
 Addison-Wesley 1993, ISBN 0-201-41663-8</name><name>Database Tuning - A Principled Approach.
 Prentice-Hall 1992, ISBN 0-13-205246-6</name><name>Cost-Based Optimization for Magic: Algebra and Implementation.</name><name>The C++ Programming Language, Second Edition.
 Addison-Wesley 1991, ISBN 0-201-53992-6</name></citation><abstract>EROC (Extensible, Reusable Optimization Components) is a toolkit
for building query optimizers. EROC's components are C++ classes based
on abstractions we have identified
as central to query optimization, not only in relational DBMSs,
but in extended relational and object-oriented DBMSs as well.
EROC's use of C++ classes clarifies the mapping from application
domain (optimization) abstractions to solution domain (EROC) abstractions,
and these classes provide:
(1) complex predicate definition and manipulation;
(2) representations for common operators, such as join and groupby,
and associated property derivation functions, including key derivation;
(3) management of catalog and type information;
(4) implementations of common algebraic equivalence rules,
and (5) System R- and
Volcano-style search strategies.
The classes are designed to
provide optimizer implementors reusability and extensibility
through layering and inheritance. EROC provides much more functionality than
previous optimization tools because all of EROC's optimization classes
are extensible and reusable, not just the search components.
In addition to describing EROC's architecture and software engineering,
we also show how EROC's classes were extended
to build NEATO (New EROC-based Advanced Teradata Optimizer), a join optimizer
for a massively parallel environment.
Based on the extensions required we give an indication of the savings
EROC provided us. To show NEATO's efficiency and effectiveness,
we present results of optimizing complex TPC/D benchmark queries and show
that NEATO easily searches the entire space of query execution plans.
We outline plans for extensions to NEATO and overview how
the flexibility of EROC will enable these extensions.</abstract></paper><paper><title>A New SQL-like Operator for Mining Association Rules.</title><author><AuthorName>Rosa Meo</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Giuseppe Psaila</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Stefano Ceri</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Efficient Similarity Search In Sequence Databases.</name><name>An Interval Classifier for Database Mining Applications.</name><name>Mining Association Rules between Sets of Items in Large Databases.</name><name>Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases.</name><name>Querying Shapes of Histories.</name><name>Fast Algorithms for Mining Association Rules in Large Databases.</name><name>Mining Sequential Patterns.</name><name>Relational Database Theory.
 Benjamin/Cummings 1993, ISBN 0-8053-0249-2</name><name>Fast Subsequence Matching in Time-Series Databases.</name><name>Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total.</name><name>Discovery of Multiple-Level Association Rules from Large Databases.</name><name>Set-Oriented Mining for Association Rules in Relational Databases.</name><name>An Effective Hash Based Algorithm for Mining Association Rules.</name><name>Mining Generalized Association Rules.</name><name>Principles of Database  and Knowledge-Base Systems, Volume I.
 Computer Science Press 1988, ISBN 0-7167-8158-1</name><name>Computer Systems That Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning and Expert Systems.</name></citation><abstract>Data mining evolved as a collection of applicative problems and efficient 
solution algorithms relative to rather peculiar problems, all focused on the 
discovery of relevant information hidden in databases of huge dimensions.
In particular, one of the most investigated topics is the discovery of
association rules.
This work proposes a unifying model that enables a uniform description of the 
problem of discovering association rules.
The model provides SQL-like operator, named {\em MINE RULE}, which is
capable of expressing all the problems presented so far in the literature
concerning the mining of association rules. We demonstrate the expressive 
power of the new operator by means of several examples, some of which are
classical, while some others are fully original and correspond to novel and 
unusual applications. We also present the operational semantics of the 
operator by means of an extended relational algebra.</abstract></paper><paper><title>Sampling Large Databases for Association Rules.</title><author><AuthorName>Hannu Toivonen</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1996</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Mining Association Rules between Sets of Items in Large Databases.</name><name>Fast Discovery of Association Rules.</name><name>The Probabilistic Method.
 John Wiley 1992, ISBN 0-471-53588-5</name><name>Fast Algorithms for Mining Association Rules in Large Databases.</name><name>Advances in Knowledge Discovery and Data Mining.
 AAAI/MIT Press 1996, ISBN 0-262-56097-6</name><name>Discovery of Multiple-Level Association Rules from Large Databases.</name><name>A Perspective on Databases and Data Mining.</name><name>Sequential Sampling Procedures for Query Size Estimation.</name><name>The Power of Sampling in Knowledge Discovery.</name><name>Finding Interesting Rules from Large Sets of Discovered Association Rules.</name><name>NeuroRule: A Connectionist Approach to Data Mining.</name><name>Efficient Algorithms for Discovering Association Rules.</name><name>Random Sampling from B+ Trees.</name><name>An Effective Hash Based Algorithm for Mining Association Rules.</name><name>Knowledge Discovery in Databases.
 AAAI/MIT Press 1991, ISBN 0-262-62080-4</name><name>Mining Generalized Association Rules.</name><name>An Efficient Algorithm for Mining Association Rules in Large Databases.</name><name>Clustering Categorical Data: An Approach Based on Dynamical Systems.</name></citation><abstract>Discovery of association rules is an important database mining problem.
Current algorithms for finding association rules require several passes 
over the analyzed database, and obviously the role of I/O overhead is 
very significant for very large databases. We present new algorithms that 
reduce the database activity considerably. The idea is to pick a random 
sample, to find using this sample all association rules that probably