vldb_1994_elementary.txt

利用lwp：：get写的

 W. H. Freeman 1979, ISBN 0-7167-1044-7</name><name>A Software Engineering Methodology for Rule-Based Systems.</name><name>An Improved Min-Cut Algorithm for Partitioning VLSI Networks.</name><name>DKM - A Distributed Knowledge Representation Framework.</name><name>Commercial Applications of Large Prolog Knowledge Bases.</name><name>The knowledge base partitioning problem: Mathematical formulation and heuristic clustering.</name><name>Multiple-Way Network Partitioning.</name><name>Finding k-cuts within Twice the Optimal.</name></citation><abstract>The design of a distributed deductive database system differs from the
design of conventional non-distributed deductive database systems in
that it requires design of distribution of both the database and
rulebase.  In this paper, we address the rule allocation problem. We
consider minimization of data communication cost  during rule execution
as a primary basis for rule allocation. The rule allocation problem can
be stated in terms of a directed acyclic graph, where nodes represent
rules or relations, and edges represent either dependencies between
rules or usage of relations by rules. The arcs are given weights
representing volume of data that need to flow between the connected
nodes. We show that rule allocation problem is NP-complete.  Next, we
propose a heuristic for nonreplicated allocation based on successively
combining adjacent nodes for placement at same site which are connected
by highest weight edge, and study its performance vis-a-vis the
enumerative algorithm for optimal allocation. Our results show that the
heuristic produces acceptable allocations. We also extend our heuristic
for partially replicated allocation.</abstract></paper><paper><title>Towards Automated Performance Tuning for Complex Workloads.</title><author><AuthorName>Kurt P. Brown</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Manish Mehta</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Michael J. Carey</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Miron Livny</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Managing Memory to Meet Multiclass Workload Response Time Goals.</name><name>Towards an Autopilot in the DBMS Performance Cockpit.</name><name>Implementation Techniques for Main Memory Database Systems.</name><name>The Gamma Database Machine Project.</name><name>Parallel Database Systems: The Future of High Performance Database Systems.</name><name>Goal Oriented, Adaptive Transaction Routing for High Performance Transaction Processing Systems.</name><name>Dynamic Memory Allocation for Multiple-Query Workloads.</name><name>Memory-Adaptive External Sorting.</name><name>Accurate Modeling of the Hybrid Hash Join Algorithm.</name><name>Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches.</name><name>The COMFORT Project (Synopsis).</name><name>Buffer Management Based on Return on Consumption in a Multi-Query Environment.</name></citation><abstract>In this paper we explore the problem of automatically adjusting DBMS
multiprogramming levels and memory allocations in order to achieve a
set of per-class response time goals for a complex multiclass
workload.  We start by describing the phenomena that make this a very
challenging problem, the foremost of which is the interdependence
between classes that results from their competition for shared
resources.  We then describe M&amp;M, a feedback-based algorithm for
simultaneously determining the MPL and memory settings for each class
independently, and we evaluate the algorithm's effectiveness using a
detailed simulation model.  We show that our algorithm can successfully
achieve response times that are within a few percent of the goals for
mixed workloads consisting of short transactions and longer-running ad
hoc join queries.</abstract></paper><paper><title>Fast, Randomized Join-Order Selection - Why Use Transformations?</title><author><AuthorName>C{\'e}sar A. Galindo-Legaria</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Arjan Pellenkoft</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Martin L. Kersten</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Very Large Data Bases</conference><citation><name>A Multi-Environment Cost Evaluator for Parallel Database Systems.</name><name>Query Processing for Advanced Database Systems, Selected Contributions from a Workshop on "Query Processing in Object-Oriented, Complex-Object and Nested Relation Databases", Interationales Begegnungs- und Forschungszentrum f&amp;uuml;r Informatik, Schloss Dagstuhl, Germany, June 1991.</name><name>Query Evaluation Techniques for Large Databases.</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>Query Optimization by Simulated Annealing.</name><name>Ranking and Unranking of AVL-Trees.</name><name>On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces.</name><name>Measuring the Complexity of Join Enumeration in Query Optimization.</name><name>Generating Binary Trees Lexicographically.</name><name>Optimization of Large Join Queries.</name><name>Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques.</name><name>OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization.</name></citation><abstract>We study the effectiveness of probabilistic selection of join-query
evaluation plans,  without reliance on tree transformation rules.
Instead, each candidate plan is chosen uniformly at random from the
space of valid evaluation orders.  This leads to a transformation-free
strategy where a sequence of random plans is generated and the plans
are compared on their estimated costs.  The success of this strategy
depends on the ratio of ``good'' evaluation plans in the space of
alternatives, the efficient generation of random candidates, and an
accurate estimation of their cost.  To avoid a biased exploration of
the space, we solved the open problem of efficiently generating random,
uniformly-distributed evaluation orders, for queries with acyclic
graphs.  This benefits any optimization or sampling scheme in which a
random choice of (initial) query plans is required.  A direct
comparison with iterative improvement and simulated annealing, using a
proven cost-evaluator, shows that our transformation-free strategy
converges faster and yields solutions of comparable cost.</abstract></paper><paper><title>Query Optimization by Predicate Move-Around.</title><author><AuthorName>Alon Y. Levy</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Inderpal Singh Mumick</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Yehoshua Sagiv</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Magic Sets and Other Strange Ways to Implement Logic Programs.</name><name>On the Power of Magic.</name><name>Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers.</name><name>Optimization of Nested SQL Queries Revisited.</name><name>Practical Predicate Placement.</name><name>Predicate Migration: Optimizing Queries with Expensive Predicates.</name><name>On Optimizing an SQL-like Nested Query.</name><name>Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions.</name><name>Constraints and Redundancy in Datalog.</name><name>Magic is Relevant.</name><name>Magic Conditions.</name><name>Improved Unnesting Algorithms for Join Aggregate SQL Queries.</name><name>Extensible/Rule Based Query Rewrite Optimization in Starburst.</name><name>Pushing Constraint Selections.</name><name>Foundations of Aggregation Constraints.</name><name>Aggregation and Relevance in Deductive Databases.</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></citation><abstract>A new type of optimization, called Predicate Move-around, is
introduced.  It is shown how this optimization considerably improves
the efficiency of evaluating SQL queries that have query graphs with a
large number of query blocks (which is a typical situation when
queries are defined in terms of multiple views and subqueries).
Predicate move-around works by moving predicates across query blocks
(in the query graph) that cannot be merged into one block.  Predicate
move-around is a generalization of and has many advantages over the
traditional predicate pushdown.  One key advantage arises from the
fact that predicate move-around precedes pushdown by pulling
predicates up the query graph. As a result, predicates that appear in
the query in one part of the graph can be moved around the graph and
applied also in other parts of graph.  Moreover, predicate move-around
optimization can move a wider class of predicates in a wider class of
queries as compared to the standard predicate-pushdown techniques.  In
addition to the usual comparison and arithmetic predicates, other
predicates that can be moved around are the EXISTS and NOT EXISTS
clauses, the EXCEPT clause, and functional dependencies.  The proposed
optimization can also move predicates through aggregation.  Moreover,
the method can also infer new predicates when existing predicates are
moved through aggregation or when certain functional dependencies are
known to hold.  Finally, the predicate move-around algorithm is easy
to implement on top of existing query optimizers.</abstract></paper><paper><title>Supporting Exceptions to Schema Consistency to Ease Schema Evolution in OODBMS.</title><author><AuthorName>Eric Amiel</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Marie-Jo Bellosta</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Eric Dujardin</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Eric Simon</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1994</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Static Type Checking of Multi-Methods.</name><name>Method Schemas.</name><name>CommonLoops: Merging Lisp and Object-Oriented Programming.</name><name>Semantics and Implementation of Schema Evolution in Object-Oriented Databases.</name><name>Modeling Class Hierarchies with Contradictions.</name><name>Type Systems for Querying Class Hierarchies with Non-strict Inheritance.</name><name>Object-Oriented Multi-Methods in Cecil.</name><name>A Proposal for Making Eiffel Type-Safe.</name><name>Updating the Schema of an Object-Oriented Database (Extended Abstract).</name><name>On Understanding Types, Data Abstraction, and Polymorphism.</name><name>Multi-Methods in a Statically-Typed Programming Language.</name><name>Schema Updates and Consistency.</name></citation><abstract>Object-oriented databases enforce schema consistency rules to
guarantee type safety, i.e., that no run-time type error can
occur. When the schema must evolve, some schema updates may violate
these rules.  In order to maintain complete schema consistency,