Database Theory – ICDT 2005: 10th International Conference, Edinburgh, UK, January 5-7, 2005. Proceedings

Moshe Y. Vardi (auth.), Thomas Eiter, Leonid Libkin (eds.)3540242880, 9783540242888, 9783540305705

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.

---

Table of contents :
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 –