vldb_1998_elementary.txt

利用lwp：：get写的

Our experiments validate the intuition in our model and demonstrate speedups of 2x on 10 disks across four scan-based applications.
The model promises linear speedups in disk arrays of hundreds of disks, provided the application data is large enough.</abstract></paper><paper><title>Resource Scheduling for Composite Multimedia Objects.</title><author><AuthorName>Minos N. Garofalakis</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Yannis E. Ioannidis</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Banu {\"O}zden</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Maintaining Knowledge about Temporal Intervals.</name><name>Efficient 2-dimensional Approximate Matching of Non-Rectangular Figures.</name><name>Orthogonal Packings in Two Dimensions.</name><name>Shelf Algorithms for Two-Dimensional Packing Problems.</name><name>Improved Scheduling Algorithms for Minsum Criteria.</name><name>Retrieval of Composite Multimedia Objects.</name><name>Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms.</name><name>Bounds for Multiprocessor Scheduling with Resource Constraints.</name><name>Computer and Intractability: A Guide to the Theory of NP-Completeness.
 W. H. Freeman 1979, ISBN 0-7167-1044-7</name><name>Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources.</name><name>Bounds on Multiprocessing Timing Anomalies.</name><name>Fast Pattern Matching in Strings.</name><name>Non-standard stringology: algorithms and complexity.</name><name>A Low-Cost Storage Server for Movie on Demand Databases.</name><name>Combinatorial Optimization: Algorithms and Complexity.
 Prentice-Hall 1982, ISBN 0-13-152462-3</name><name>Multiple-Query Optimization.</name><name>Scheduling Parallel Machines On-Line.</name><name>On RAM Priority Queues.</name><name></name></citation><abstract>Scheduling algorithms for composite multimedia presentations need to ensure that the user-defined synchronization constraints for the various presentation components are met.
This requirement gives rise to task models that are significantly more complex than the models employed in scheduling theory and practice.
In this paper, we formulate the resource scheduling problems for compositemultimedia objects and develop novel efficient scheduling algorithms drawing on a number of techniques from pattern matching and multiprocessor scheduling.
Our formulation is based on a novel sequence packing problem, wherethe goal is to superimpose numeric sequences (representing the objects' resource needs as a function of time) within a fixed capacity bin (representing the server's resource capacity).
Given the intractability of the problem, we propose heuristic solutions using a two-step approach.
First, we present a "basic step" method for packing two composite object sequences into a single, combined sequence.
Second, we show how this basic step can be employed within different scheduling algorithms to obtain a playout schedule for multiple objects.
More specifically, we present an algorithm based on Graham's list-scheduling method that is provably near- optimal for monotonic object sequences.
We also suggest a number of optimizations on the base list- scheduling scheme. Preliminary experimental results confirm the effectiveness of our approach.</abstract></paper><paper><title>Hash Joins and Hash Teams in Microsoft SQL Server.</title><author><AuthorName>Goetz Graefe</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Ross Bunker</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Shaun Cooper</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Hashing Methods and Relational Algebra Operations.</name><name>Implementation Techniques for Main Memory Database Systems.</name><name>Multiprocessor Hash-Based Join Algorithms.</name><name>Nested Loops Revisited.</name><name>An Overview of The System Software of A Parallel Relational Database Machine GRACE.</name><name>Query Evaluation Techniques for Large Databases.</name><name>Sort-Merge-Join: An Idea Whose Time Has(h) Passed?</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>Query Execution Techniques for Caching Expensive Methods.</name><name>The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method.</name><name>Fragmentation: A Technique for Efficient Query Processing.</name><name>Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines.</name><name>Access Path Selection in a Relational Database Management System.</name><name>An Adaptive Hash Join Algorithm for Multiuser Environments.</name></citation><abstract>The query execution engine in Microsoft SQL Server employs hash-based algorithms for inner and outer joins, semi-joins, set operations (such as intersection), grouping, and duplicate removal.
The implementation combines many techniques proposed individually in the research literature but never combined in a single implementation, neither in a product nor in a research prototype.
One of the paper's contributions is a design that cleanly integrates most existing techniques.
One technique, however, which we call hash teams and which has previously been described only in vague terms, has not been implemented in prior research or product work.
It realizes in hash-based query processing many of the benefits of interesting orderings in sort-based query processing.
Moreover, we describe how memory is managed in complex and bushy query evaluation plans with multiple sort and hash operations.
Finally, we report on the effectiveness of hashing using two very typical database queries, including the performance effects of hash teams.</abstract></paper><paper><title>Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships.</title><author><AuthorName>Sven Helmer</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Till Westmann</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Guido Moerkotte</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Hashing Methods and Relational Algebra Operations.</name><name>Multiprocessor Hash-Based Join Algorithms.</name><name>Implementation Techniques for Main Memory Database Systems.</name><name>Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting.</name><name>An Overview of The System Software of A Parallel Relational Database Machine GRACE.</name><name>Sort-Merge-Join: An Idea Whose Time Has(h) Passed?</name><name>Sort versus Hash Revisited.</name><name>Seeking the Truth About ad hoc Join Costs.</name><name>Implementing a Generalized Access Path Structure for a Relational Database System.</name><name>Join Algorithm Costs Revisited.</name><name>Indexing Multiple Sets.</name><name>Indexing Techniques for Object-Oriented Databases.</name><name>The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses.
 John Wiley 1996, ISBN 0-471-15337-0</name><name>The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method.</name><name>A Low Communication Sort Algorithm for a Parallel Database Machine.</name><name>A Study of Sort Algorithms for Multiprocessor Database Machines.</name><name>Join Processing in Relational Databases.</name><name>Hash-Partitioned Join Method Using Dynamic Destaging Strategy.</name><name>Multi-Table Joins Through Bitmapped Join Indices.</name><name>FastSort: A Distributed Single-Input Single-Output External Sort.</name><name>Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines.</name><name>Join Processing in Database Systems with Large Main Memories.</name><name>A New Join Algorithm.</name><name>Join Indices.</name><name>Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases.</name></citation><abstract>Time of creation is one of the predominant (often implicit) clustering strategies found not only in Data Warehouse systems: line items are created together with their corresponding order, objects are created together with their subparts and so on.
The newly created data is then appended to the existing data.
We present a new join algorithm, called Diag- Join, which exploits time-of-creation clustering.
If we are able to take advantage of time- of-creation clustering, then theperformance evaluation reveals the superiority of Diag-Join over standard join algorithms like block-wise nested-loop join, GRACE hash join, and index nested-loop join.
We also present an analytical cost model for Diag-Join.</abstract></paper><paper><title>Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases.</title><author><AuthorName>Reinhard Braumandl</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Jens Clau{\ss}en</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Alfons Kemper</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1998</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Indexing Techniques for Queries on Nested Objects.</name><name>A High Performance Configurable Storage Manager.</name><name>Shoring Up Persistent Applications.</name><name>An Incremental Join Attachment for Starburst.</name><name>Pointer-Based Join Techniques for Object-Oriented Databases.</name><name>A Performance Evaluation of OID Mapping Techniques.</name><name>Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases.</name><name>Query Evaluation in CROQUE - Calculus and Algebra Coincide.</name><name>Query Evaluation Techniques for Large Databases.</name><name>Seeking the Truth About ad hoc Join Costs.</name><name>Join Algorithm Costs Revisited.</name><name>Object Identity.</name><name>Access Support in Object Bases.</name><name>The ObjectStore Database System.</name><name>Accurate Modeling of the Hybrid Hash Join Algorithm.</name><name>A Performance Evaluation of Pointer-Based Joins.</name><name>The relational model with relation-valued attributes.</name><name>Object-Relational DBMSs: The Next Great Wave.</name><name>Join Indices.</name><name>Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases.</name></citation><abstract>Previous work on functional joins was constrained in two ways: (1) all approaches we know assume references being implemented as physical object identifiers (OIDs) and (2) most approaches are, in addition, limited to single-valued reference attributes.
Both are severe limitations since most object-relational and all object-oriented database systems do support nested reference sets and many object systems do implement references as location-independent (logical) OIDs.