vldb_1997_elementary.txt

利用lwp：：get写的

strong contribution from the area of database systems.</abstract></paper><paper><title>Incremental Organization for Data Recording and Warehousing.</title><author><AuthorName>H. V. Jagadish</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>P. P. S. Narayan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>S. Seshadri</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>S. Sudarshan</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Rama Kanneganti</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Very Large Data Bases</conference><citation><name>View Maintenance Issues for the Chronicle Data Model.</name><name>The Art of Computer Programming, Volume III: Sorting and Searching.
 Addison-Wesley 1973, ISBN 0-201-03803-X</name><name>ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes.</name><name>ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging.</name><name>The Log-Structured Merge-Tree (LSM-Tree).</name><name>A Log-Structured History Data Access Method (LHAM).</name><name>Database System Concepts, 3rd Edition.
 McGraw-Hill Book Company 1997, ISBN 0-07-044756-X</name><name>Differential Files: Their Application to the Maintenance of Large Databases.</name><name>On-Line Index Construction Algorithms.</name></citation><abstract>Data warehouses and recording systems typically have a large continuous 
stream of incoming data, that must be stored in a manner suitable for future access.
Access to stored records is usually based on a key.
Organizing the data on disk as the data arrives
using standard techniques would result in 
either (a) one or more I/Os to store each incoming record (to keep the
data clustered by the key), which is too expensive when data arrival rates
are very high, or (b) many I/Os to locate records
for a particular customer (if data is stored clustered by arrival order).
We study two techniques, inspired by external sorting algorithms, 
to store data incrementally as it arrives, 
simultaneously providing good performance for recording 
and querying.  
We present concurrency control and recovery schemes for both techniques.
We show the benefits of our techniques both analytically and 
experimentally.</abstract></paper><paper><title>Multiple-View Self-Maintenance in Data Warehousing Environments.</title><author><AuthorName>Nam Huyn</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Optimal Implementation of Conjunctive Queries in Relational Data Bases.</name><name>Using Partial Information to Update Materialized Views.</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>Constraint Checking with Partial Information.</name><name>The Stanford Data Warehousing Project.</name><name>Efficient View Self-Maintenance.</name><name>Rdb/VMS: Developing the Data Warehouse.
 QED Publishing Group/John Wiley 1993, ISBN 0-471-56920-8</name><name>On conjunctive queries containing inequalities.</name><name>On the Efficient Computation of the Difference Between Concecutive Database States.</name><name>Queries Independent of Updates.</name><name>Making Views Self-Maintainable for Data Warehousing.</name><name>Incremental Maintenance of Externally Materialized Views.</name><name>Maintaining materialized views without accessing base data.</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>View Maintenance in a Warehousing Environment.</name></citation><abstract>A data warehouse materializes views derived from data that may not
reside at the warehouse. Maintaining these views efficiently in
response to base updates is difficult, since it may involve querying
external sources where the base data reside.  This paper considers the
problem of view self-maintenance, where the views are maintained
without using all the base data.  Without full use of the base data,
however, maintaining a view unambiguously is not always possible.
Thus, the two critical questions that must be addressed are to
determine, in a given situation, whether a view is maintainable, and
how to maintain it.
We provide algorithms that answer these questions for a general class
of views, and for an important subclass, generate SQL queries that
test whether a view is self-maintainable and update the view if it is.
We improve significantly on previous work by solving the view
self-maintenance problem in the presence of multiple views, with
optional access to a subset of the base data, and under arbitrary
mixes of insertions and deletions. We provide better insight into the
problem by showing that view self-maintainability can be reduced to
the problem of deciding query containment.</abstract></paper><paper><title>Recovering Information from Summary Data.</title><author><AuthorName>Christos Faloutsos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>H. V. Jagadish</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Nikolaos Sidiropoulos</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Adaptive Selectivity Estimation Using Query Feedback.</name><name>Implications of Certain Assumptions in Database Performance Evaluation.</name><name>Answering Queries with Aggregation Using Views.</name><name>Closed World Databases Opened Through Null Values.</name><name>Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total.</name><name>Aggregate-Query Processing in Data Warehousing Environments.</name><name>Maintaining Views Incrementally.</name><name>Implementing Data Cubes Efficiently.</name><name>Incomplete Information in Relational Databases.</name><name>Balancing Histogram Optimality and Practicality for Query Result Size Estimation.</name><name>The INCINERATE Data Model.</name><name>View Maintenance Issues for the Chronicle Data Model.</name><name>Introduction to Linear and Nonlinear Programming.
 Addison-Wesley 1973</name><name>A Universal-Scheme Approach to Statistical Databases Containing Homogeneous Summary Tables.</name><name>Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries.</name><name>Information Synthesis in Statistical Databases.</name><name>Numerical Recipes in C, 2nd Edition.
 Cambridge University Press 1992</name><name>Access Path Selection in a Relational Database Management System.</name><name>An Information-Theoretic Study on Aggregate Responses.</name><name>A Model for the Prediction of R-tree Performance.</name><name>Time Series Prediction: Forecasting the Future and Understanding the Past.
 Addison-Wesley 1994, ISBN 0-201-62601-2</name><name>Research Problems in Data Warehousing.</name></citation><abstract>Data is often stored in summarized form, as a histogram of aggregates
(COUNTs, SUMs, or AVeraGes) over specified ranges. We study how to estimate
the original detail data from the stored summary. We formulate this task
as an inverse problem, specifying a well-defined cost function
that has to be optimized under constraints. We show that our formulation
includes the uniformity and independence assumptions as a special case,
and that it can achieve better reconstruction results if we maximize the
smoothness as opposed to the uniformity.
In our experiments on real and synthetic datasets, the proposed method
almost consistently outperforms its competitor, improving the root-mean-square
error by up to 20 per cent for stock price data, and up to 90 per cent
for smoother data sets. Finally, we show how to apply this theory to a
variety of database problems that involve partial information, such as
OLAP, data warehousing and histograms in query optimization.</abstract></paper><paper><title>A Language for Manipulating Arrays.</title><author><AuthorName>Arunprasad P. Marathe</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><author><AuthorName>Kenneth Salem</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Very Large Data Bases</conference><citation><name>ODMG-93: The Object Database Standard.</name><name>Image Information Systems: Where Do We Go From Here?</name><name>Client-Server Paradise.</name><name>Towards an Effective Calculus for Object Query Languages.</name><name>An Optimizer for Heterogeneous Systems with NonStandard Data and Search Capabilities.</name><name>A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques.</name><name>Design and Implementation of an Extensible Database Management System Supporting User Defined Data Types and Functions.</name><name>A Call to Order.</name><name>Query Processing in a Parallel Object-Relational Database System.</name><name>E-ADTs: Turbo-Charging Complex Data.</name><name>The Implementation of Postgres.</name><name>The JPEG Still Picture Compression Standard.</name></citation><abstract>This paper describes the Array Manipulation Language (AML),
an algebra for multidimensional array data. AML is generic, 
in the sense that it can be customized to support a wide variety 
of domain-specific operations on arrays. AML expressions can be 
treated declaratively and subjected to rewrite optimizations.
To illustrate this, several rewrite rules that exploit the
structural properties of the AML operations are presented.
Some techniques for efficient evaluation of AML expressions
are also discussed.</abstract></paper><paper><title>Implementing Abstract Objects with Inheritance in Datalogneg.</title><author><AuthorName>Hasan M. Jamil</AuthorName><institute><InstituteName></InstituteName><country></country></institute></author><year>1997</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Methods and Rules.</name><name>Towards a Logical-Object Oriented Programming Language for Databases.</name><name>A Type Declaration and Inference System for Smalltalk.</name><name>A Declarative View of Inheritance in Logic Programming.</name><name>A Logic for Encapsulation in Object Oriented Languages.</name><name>A Stable Model Semantics for Behavioral Inheritance in Deductive Object Oriented Languages.</name><name>OOLP: A Translation Approach to Object-Oriented Logic Programming.</name><name>Inheritance with Overriding Without Non-monotonic Reasoning in Datalog++.</name><name>A Declarative Semantics for Behavioral Inheritance and Conflict Resolution.</name><name>Logical Foundations of Object-Oriented and Frame-Based Languages.</name><name>O2, an Object-Oriented Data Model.</name><name>A Logical Analysis of Modules in Logic Programming.</name><name>CORAL - Control, Relations and Logic.</name><name>The C++ Programming Language, First Edition.
 Addison-Wesley 1986, ISBN 0-201-12078-X</name></citation><abstract>We present an elegant technique to  reduce  inheritance  and
encapsulation    to    pure    deduction.    The   reduction
technique  presented  in  this  paper  makes  it possible to
model   object-oriented   database   features  in  a  purely
deductive  system.  Encapsulation   has    been    given   a
formal  treatment  for the first time by introducing the  so
called    context-resolution    scheme.    The    completion
technique   presented   in   this  paper  elegantly  tackles
inheritance  with  overriding  and  conflict  resolution  by
avoiding  non-monotonic  reasoning.  We  show    that    the
completion   based  reduction  technique   is   robust   and
appealing  compared  to  any   other   known rewriting based
approaches.   We  propose   an   object-oriented   front-end
language    called    the  Datalog++, and discuss a
rewriting   scheme  to  the acclaimed Datalogneg for this
language that exploits the context resolution and completion
techniques presented here.  We  claim that    our   approach
outperforms   other  known  approaches in  the literature in
terms of its   modeling    capabilities  and     efficiency.
Unlike most others, an implementation based on our reduction
technique   does   not   require   meta-interpretation   and
consequently   readily    exploits    the   rich   set    of
optimization techniques available in Datalogneg.</abstract></paper><paper><title>The Case for Enhanced Abstract Data Types.</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>1997</year><conference>International Conference on Very Large Data Bases</conference><citation><name>Semantic Query Optimization for Methods in Object-Oriented Database Systems.</name><name>Data Access for the Masses through OLE DB.</name><name>The Object Database Standard: ODMG-93 (Release 1.1).</name><name>A General Framework for the Optimization of Object-Oriented Queries.</name><name>Shoring Up Persistent Applications.</name><name>Join Queries with External Text Sources: Execution and Optimization Techniques.</name><name>Query Optimization in the Presence of Foreign Functions.</name><name>Optimization of Queries with User-defined Predicates.</name><name>Rule Languages and Internal Algebras for Rule-Based Optimizers.</name><name>Client-Server Paradise.</name><name>The Volcano Optimizer Generator: Extensibility and Efficient Search.</name><name>Abstract Data Type and the Development of Data Structures.</name><name>Optimization and Execution Techniques for Queries With Expensive Methods.
Ph.D. thesis,  Univ. of Wisconsin-Madison 1995</name><name>The Implementation of Functional Programming Languages.</name><name>Extending the Search Strategy in a Query Optimizer.</name><name>Programming with Abstract Data Types.</name><name>Challenges for Query Processing in Object-Oriented Databases.</name><name>Control of an Extensible Query Optimizer: A Planning-Based Approach.</name><name>Understanding and Extending Transformation-Based Optimizers.</name><name>The Sequoia 2000 Benchmark.</name><name>The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases.</name><name>The Implementation of Postgres.</name><name>A Modular Query Optimizer Generator.</name><name>Inclusion of New Types in Relational Data Base Systems.</name><name>Querying Nested Collections.
Ph.D. thesis,  Univ. Pennsylvania 1994</name></citation><abstract>The explosion in complex multi-media content makes it crucial for
database systems to support such data efficiently. We make the case 
that the next generation of object-relational database systems should 
be based on Enhanced Abstract Data Type (E-ADT) technology, rather 
than on the ``blackbox'' ADTs used in current systems. An E-ADT is an 
abstract data type that exposes the semantics of its methods. 
Query optimizations are performed using these semantics, resulting in 
efficient query processing. The added functionality does not compromise