This book constitutes the refereed proceedings of the 8th International Conference on Database Theory, ICDT 2001, held in London, UK, in January 2001. The 26 revised full papers presented together with two invited papers were carefully reviewed and selected from 75 submissions. All current issues on database theory and the foundations of database systems are addressed. Among the topics covered are database queries, SQL, information retrieval, database logic, database mining, constraint databases, transactions, algorithmic aspects, semi-structured data, data engineering, XML, term rewriting, clustering, etc.
Author(s): Leonid Libkin (auth.), Jan Van den Bussche, Victor Vianu (eds.)
Series: Lecture Notes in Computer Science 1973
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2001
Language: English
Pages: 454
Tags: Database Management; Mathematical Logic and Formal Languages; Information Storage and Retrieval; Information Systems Applications (incl.Internet); Algorithm Analysis and Problem Complexity
Expressive Power of SQL....Pages 1-21
Query Evaluation via Tree-Decompositions....Pages 22-38
Scalar Aggregation in FD-Inconsistent Databases....Pages 39-53
On Decidability and Complexity of Description Logics with Uniqueness Constraints....Pages 54-67
Expressiveness Issues and Decision Problems for Active Database Event Queries....Pages 68-82
A Theory of Transactions on Recoverable Search Trees....Pages 83-98
Minimizing View Sets without Losing Query-Answering Power....Pages 99-113
Cost Based Data Dissemination in Broadcast Networks....Pages 114-128
Parallelizing the Data Cube....Pages 129-143
Asymptotically Optimal Declustering Schemes for Range Queries....Pages 144-158
Flexible Data Cubes for Online Aggregation....Pages 159-173
Mining for Empty Rectangles in Large Data Sets....Pages 174-188
FUN: An Efficient Algorithm for Mining Functional and Embedded Dependencies....Pages 189-203
Axiomatization of Frequent Sets....Pages 204-218
On Answering Queries in the Presence of Limited Access Patterns....Pages 219-233
The Dynamic Complexity of Transitive Closure Is in DynTC°....Pages 234-247
Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls....Pages 248-262
A Semi-monad for Semi-structured Data (ICDT Version)....Pages 263-300
Algebraic Rewritings for Optimizing Regular Path Queries....Pages 301-315
Why and Where: A Characterization of Data Provenance....Pages 316-330
Subsumption for XML Types....Pages 331-345
Towards Aggregated Answers for Semistructured Data....Pages 346-360
Orthogonal Range Queries in OLAP....Pages 361-374
Reasoning about Summarizability in Heterogeneous Multidimensional Schemas....Pages 375-389
Estimating Range Queries Using Aggregate Data with Integrity Constraints: A Probabilistic Approach....Pages 390-404
Constraint-Based Clustering in Large Databases....Pages 405-419
On the Surprising Behavior of Distance Metrics in High Dimensional Space....Pages 420-434
On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces....Pages 435-449
