Database Theory - ICDT'99

Databaseresearchisa?eldofcomputersciencewheretheorymeetsapplications. Many concepts and methods, that were regarded as issues of theoretical interest when initially proposed, are now included in implemented database systems and related products. Examples abound in the ?elds of database design, query languages, query optimization, concurrency control, statistical databases, and many others. The papers contained in this volume were presented at ICDT'99, the 7th - ternationalConferenceonDatabaseTheory,inJerusalem,Israel,January10-12, 1999. ICDT is an international forum for research on the principles of database systems. It is a biennial conference, and has a tradition of being held in beau- ful European sites: Rome in 1986, Bruges in 1988, Paris in 1990, Berlin in 1992, Prague in 1995, and Delphi in 1997. From 1992, ICDT has been merged with another series of conferences on theoretical aspects of database systems, The Symposium on Mathematical Fundamentals of Database Systems (MFDBS), that was initiated in Dresden (1987), and continued in Visegrad (1989) and Rostock (1991). ICDT aims to enhance the exchange of ideas and cooperation in database research both within uni?ed Europe, and between Europe and the other continents. ICDT'99 was organized in cooperation with: ACM Special Interest Group on Management of Data (Sigmod) IEEE Israel Chapter ILA - The Israel Association for Information Processing EDBT Foundation ICDT'99 was sponsored by: The Hebrew University of Jerusalem Tel Aviv University Tandem Labs Israel, a Compaq Company This volume contains 26 technical papers selected from 89 submissions.

Inhalt

Invited Talks.- Issues Raised by Three Years of Developing PJama: An Orthogonally Persistent Platform for Java(TM).- Novel Computational Approaches to Information Retrieval and Data Mining.- Tutorial.- Description Logics and Their Relationships with Databases.- Query Languages.- An Equational Chase for Path-Conjunctive Queries, Constraints, Views.- Adding For-Loops to First-Order Logic.- Logic.- Definability and Descriptive Complexity on Databases of Bounded Tree-Width.- Decidability of First-Order Logic Queries over Views.- Performence I.- Urn Models and Yao's Formula.- On the Generation of 2-Dimensional Index Workloads.- Increasing the Expressiveness of Analytical Performance Models for Replicated Databases.- Concurrency and Distribution.- Transactions in Stack, Fork, and Join Composite Systems.- Databases for Tracking Mobile Units in Real Time.- Constraint Databases.- On Capturing First-Order Topological Properties of Planar Spatial Databases.- On the Orthographic Dimension of Constraint Databases.- Index Structures.- When Is "Nearest Neighbor" Meaningful?.- On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity and Applications.- Optimal Dynamic Range Searching inNon-replicating Index Structures.- Index Structures for Path Expressions.- Semi-Structured Data.- Schemas for Integration and Translation of Structured and Semi-structured Data.- In Search of the Lost Schema.- Mediation.- Tableau Techniques for Querying Information Sources through Global Schemas.- Optimizing Large Join Queries in Mediation Systems.- Computational Issues.- Incremental FO( +, < ) Maintenance of All-Pairs Shortest Paths for Undirected Graphs after Insertions and Deletions.- A Framework for the Investigation of Aggregate Functions in Database Queries.- Discovering Frequent Closed Itemsets for Association Rules.- Views.- View Disassembly.- Answering Queries Using Materialized Views with Disjunctions.- Selection of Views to Materialize Under a Maintenance Cost Constraint.- The Data Warehouse of Newsgroups.