Database Theory - ICDT 2005: 10th International Conference, Edinburgh, UK, January 5-7, 2005, Proceedings (Lecture Notes in Computer Science, 3363)

This volume collects the papers presented at the 10th International Conference on Database Theory, ICDT 2005, held during January 5–7, 2005, in Edinburgh, UK. ICDT (http://alpha.luc.ac.be/~lucp1080/icdt/) has now a long tra- tion of international conferences, providing a biennial scienti?c forum for the communication of high-quality and innovative research results on theoretical - pects of all forms of database systems and database technology. The conference usually takes place in Europe, and has been held in Rome (1986), Bruges (1988), Paris (1990), Berlin (1992), Prague (1995), Delphi (1997), Jerusalem (1999), London (2001), and Siena (2003) so far. ICDT has merged with the Sym- sium on Mathematical Fundamentals of Database Systems (MFDBS), initiated in Dresden in 1987, and continued in Visegrad in 1989 and Rostock in 1991. ICDT had a two-stage submission process. First, 103 abstracts were subm- ted, which were followed a week later by 84 paper submissions. From these 84 submissions, the ICDT Program Committee selected 24 papers for presentation at the conference. Most of these papers were “extended abstracts” and preli- nary reports on work in progress. It is anticipated that most of these papers will appear in a more polished form in scienti?c journals. Front Matter....Pages - Model Checking for Database Theoreticians....Pages 1-16 The Design Space of Type Checkers for XML Transformation Languages....Pages 17-36 Semantics of Data Streams and Operators....Pages 37-52 Conjunctive Query Evaluation by Search Tree Revisited....Pages 53-67 Which XML Schemas Admit 1-Pass Preorder Typing?....Pages 68-82 The Pipelined Set Cover Problem....Pages 83-98 Well-Definedness and Semantic Type-Checking in the Nested Relational Calculus and XQuery....Pages 99-113 First Order Paths in Ordered Trees....Pages 114-128 An Abstract Framework for Generating Maximal Answers to Queries....Pages 129-143 Optimal Distributed Declustering Using Replication....Pages 144-157 When Is Nearest Neighbors Indexable?....Pages 158-172 Nonmaterialized Motion Information in Transport Networks....Pages 173-188 Algorithms for the Database Layout Problem....Pages 189-203 Approximately Dominating Representatives....Pages 204-214 On Horn Axiomatizations for Sequential Data....Pages 215-229 Privacy in Database Publishing....Pages 230-245 Anonymizing Tables....Pages 246-258 Authorization Views and Conditional Query Containment....Pages 259-273 PTIME Queries Revisited....Pages 274-288 Asymptotic Conditional Probabilities for Conjunctive Queries....Pages 289-305 Magic Sets and Their Application to Data Integration....Pages 306-320 View-Based Query Processing: On the Relationship Between Rewriting, Answering and Losslessness....Pages 321-336 First-Order Query Rewriting for Inconsistent Databases....Pages 337-351 Rewriting Queries Using Views with Access Patterns Under Integrity Constraints....Pages 352-367 Optimal Workload-Based Weighted Wavelet Synopses....Pages 368-382 Selecting and Using Views to Compute Aggregate Queries....Pages 383-397 Efficient Computation of Frequent and Top-k Elements in Data Streams....Pages 398-412 Back Matter....Pages -

This book constitutes the refereed proceedings of the 10th International Conference on Database Theory, ICDT 2005, held in Edinburgh, UK in January 2005.

The 24 revised full papers presented together with 3 invited articles were carefully reviewed and selected from 84 submissions. The papers are organized in topical sections on query languages and types, multi-dimensional data processing, algorithmic aspects, privacy and security, logic and databases, query rewriting, and query processing and data streams.

This book constitutes the refereed proceedings of the 10th International Conference on Database Theory, ICDT 2005, held in Edinburgh, UK in January 2005. The 24 revised full papers presented together with 3 invited articles were carefully reviewed and selected from 84 submissions. The papers are organized in topical sections on query languages and types, multi-dimensional data processing, algorithmic aspects, privacy and security, logic and databases, query rewriting, and query processing and data streams The recent growth in computer power and connectivity has changed the face of science and engineering, and is changing the way business is being conducted.