Database Theory - ICDT 2003: 9th International Conference, Siena, Italy, January 8-10, 2003, Proceedings (Lecture Notes in Computer Science, 2572)

This volume collects the papers presented at ICDT 2003, the 9th International ConferenceonDatabaseTheory,heldfrom8to10January2003intheRettorato dell’Universit` a di Siena, Siena, Italy. ICDT (http://alpha.luc.ac.be/ ̃lucp1080/icdt/) has now a long t- dition of international conferences, providing a biennial scienti?c forum for the communicationofhigh-qualityresearchresultsontheoreticalaspectsofallforms of database systems and database technology. ICDT is traditionally held in - storic European locations: Rome in 1986, Bruges in 1988, Paris in 1990, Berlin in 1992, Prague in 1995, Delphi in 1997, Jerusalem in 1999, and London in 2001. ICDThasmergedwiththeSymposiumonMathematicalFundamentalsofDa- base Systems (MFDBS), initiated in Dresden in 1987, and continued in Visegrad in 1989 and Rostock in 1991. This volume contains 26 papers selected from 92 submissions, plus three invited papers by Hector Garcia-Molina, Yannis Ioannidis, and Limsoon Wong. We wish to thank all the authors who submitted papers, the members of the program committee for their e?orts in reviewing and selecting the papers, the external referees, the organizing committee, and the sponsors for their support. Diego Calvanese Maurizio Lenzerini Rajeev Motwani Organization ICDT 2003 was organized by the Dipartimento di Informatica e Sistemistica, Universit` a di Roma “La Sapienza”. Database Theory - ICDT 2003 Preface Organization Table of Contents Open Problems in Data-Sharing Peer-to-Peer Systems Introduction Search Overview Expressiveness Autonomy, Efficiency, and Robustness Quality of Service Security Availability File Authenticity Anonymity Access Control Conclusion Approximations in Database Systems* Introduction Definitions Data Distributions Histograms Unification of Approximation Problems Pattern (Bucket) Recognition Approximation within a Bucket Approximation of Dimension Values and Frequencies Approximation of Multi-dimensional Elements Distance Metric Approximations and Indices Original Data and Final Result Approximation Conclusions Bioinformatics Adventures in Database Research The Great Challenges in Bioinformatics From Theory of Query Languages to Biological Data Integration Integration: What Are the Problems? Integration: Solution Nested Relational Data Model Self-Describing Data Exchange Format Thin Wrappers High-Level Query Language From Emerging Patterns to Biological Datamining Prediction: What Are the Problems? Recognition of Translation Initiation Sites Feature Generation Feature Selection Prediction: Solution A Practical Challenge Another Important Role of Databases: Laboratory Workflow Incremental Validation of XML Documents Introduction Basic Framework Incremental Validation of Sequences Incremental DTD Validation Incremental Validation via Binary Trees Encodings Conclusions and Future Work Typechecking Top-Down Uniform Unranked Tree Transducers Introduction Definitions Trees and Hedges DTDs and Tree Automata Transducers The Typechecking Problem The General Case Non-deleting Transformations Tree Automata DTDs Transducers of Bounded Width Conclusion Structural Properties of XPath Fragments Introduction Notations Logic and Qualified Fragments Closure Properties Root Equivalence Axiom Systems and Normal Forms Axiom Systems Axiom Systems for ${cal X}_r$ and ${cal X}$ Normal Forms for ${cal X}_r$ and ${cal X}$ Conclusion On Reasoning about Structural Equality in XML: A Description Logic Approach Introduction Related Work and Outline Definitions Decision Procedures and Complexity Bounds ${cal DLF}_{@mathrm {reg}}$: Lower Bounds A Decision Procedure for ${cal DLF}_{@mathrm {reg}}$ Adding Regular Functional Dependencies: ${cal DLFD}_{@mathrm {reg}}$ Structural Equality in XML Summary Future Work Adding Roles to ${cal DLF}_{@mathrm {reg}}$ Role Inverses and Other Role Constructs Containment of Aggregate Queries* Introduction Aggregate Queries Syntax of Queries Semantics of Queries Containment and Equivalence Containment of Aggregate Queries Queries with Expandable Aggregation Functions Integrity Constraints Containment of Conjunctive Count-Queries Containment of Conjunctive Sum-Queries Rewriting Conjunctive Count-Queries Definitions Class of Views and Class of Rewritings Conclusion Auditing Sum Queries 1 Introduction 2 The Bipartite Case 3 A Bipartite Map Associate with a Nonbipartite Map 4 Bounds on the Weight of an Arc 5 A Special Case 6 Future Research References CRB-Tree: An Efficient Indexing Scheme for Range-Aggregate Queries* Introduction CRB-Tree Extensions Experimental Results Implementation Experiments Optimal Range Max Datacube for Fixed Dimensions* Introduction Previous Work Our Contribution Overview Notations The Model Review of Techniques One-Dimensional Queries Construction and Storage Query Two-Dimensional Queries Construction and Storage Query Extensions to Higher Dimensions A Function Notation Function Composition Construction and Storage Query Conclusion Processing XML Streams with Deterministic Automata Introduction Overview The Event-Based Processing Model Processing with DFAs Background on DFAs The DFA at Run Time Analyzing the Size of the DFA The Eager DFA The Lazy DFA Validation of the Size of the Lazy DFA Constant Values Experiments Implementation Issues Related Work Conclusion Deciding Termination of Query Evaluation in Transitive-Closure Logics for Constraint Databases Introduction Definitions and Preliminaries Constraint Databases and First-Order Logic over the Reals Transitive-Closure Logics Undecidability of the Termination of the Evaluation of Transitive-Closure Formulas Deciding Termination for Continuous Function Graphs in the Plane Logics with Transitive Closure Restricted to Function Graphs Deciding Termination of the Evaluation of unhbox voidb @x hbox {${rm FO}{rm +}{rm cTC}^{2}$} Queries A Guarded Fragment of unhbox voidb @x hbox {${rm FO}{rm +}{rm cTC}^{2}$} Expressiveness Results Concluding Remarks Data Exchange: Semantics and Query Answering Introduction The Data Exchange Problem Universal Solutions Computing Universal Solutions Chase: Canonical Generation of Universal Solutions Polynomial-Length Chase Query Answering Query Answering: Complexity and Inexpressibility Computational Complexity First-Order Inexpressibility Concluding Remarks Reformulation of XML Queries and Constraints Introduction Contributions and Related Work Relational Query Reformulation: The unhbox voidb @x hbox {C&B} Algorithm XML Query Reformulation Using Relational Constraints to Capture XML XML Queries and Constraints Compiling Schema Correspondences The Algorithm Constraint Reformulation Summary New Rewritings and Optimizations for Regular Path Queries Introduction Background Partial Rewritings Computing the Maximal Partial Rewriting Optimizing Regular Path Queries Using Partial Rewritings Optimizing Conjunctive Regular Path Queries Complexity Analysis Database Interrogation Using Conjunctive Queries* Introduction Preliminaries Database-Independent Model Quantification and Non-equality The Adaptive Model Concluding Remarks On the Difficulty of Finding Optimal Relational Decompositions for XML Workloads: A Complexity Theoretic Perspective* Introduction Relational Decompositions and Query Translation Algorithms Motivating Example Two Simple Cost Metrics Formal Model Definitions Query Translation Algorithms Set System Coloring Complexity Results under Metric ${it SSCost_{RC}}$ Complexity Results for Other Cost Metrics Complexity of the {em Grouping} and {em Completegrouping} Problems Conclusions and Future Work Horizontal Partitioning and the {em Grouping} Problem Generating Relations from XML Documents* Introduction Framework Creating Relations from Trees Example Uses for Relation Generating Mechanism Querying Trees and Relations Using SQL An XML Search Engine Complexity of Creating Relations from Trees Complete-Interconnections Reachable-Interconnections Conclusion Containment for XPath Fragments under DTD Constraints Introduction XML Trees, XPath Queries, and DTDs Decidability of Containment under DTDs {sc ptime} Classes Limitations of Constraints Related Work Conclusion XPath Containment in the Presence of Disjunction, DTDs, and Variables Introduction Preliminaries The Base Cases: text {$/$}, text {$/tmspace -thinmuskip {.1667em}/$}, text {rm [tmspace +thinmuskip {.1667em}]}, text {$|$}, and text {$*$} Containment in the Presence of DTDs Containment in the Presence of Data Values Discussion Decidable Containment of Recursive Queries Introduction Databases and Queries Containment of Datalog in Unions of Conjunctive Queries Two-Way Alternating Tree Automata Containment of Datalog in Unions of C2RPQs Conclusions Containment of Conjunctive Queries with Safe Negation Introduction Preliminaries Query Containment The Containment Checking Algorithm for $CQ$s Query Containment for ${CQ^{neg }}$s Some Necessary Conditions Containment of ${CQ^{neg }}$s Containment of Unions of ${CQ^{neg }}$s Some Notes on Answering Queries Using Views Conclusion and Further Research Probabilistic Interval XML Introduction Motivating Example Preliminaries Semistructured Databases Interval Probabilities The textbf {textit {PIXml }}Data Model textbf {textit {PIXml }}: Declarative Semantics Compatible Semistructured Instances Global and Local Interpretations Connections between Local and Global Semantics Satisfaction textbf {textit {PIXml }}Queries textbf {textit {PIXml }}: Operational Semantics Related Work Conclusion Condensed Representation of Database Repairs for Consistent Query Answering General Problem Description General Repairing Framework Downfixing Revisited Fixes and Mends Trustable Query Answers Tableau Queries and Full Dependencies Greatest Lower Bounds Chasing Fixes Condensed Representation Size Issues Contributions and Related Work Typing Graph-Manipulation Operations Introduction The Graph-Based Data Model GDM Instance Graphs Schema Graphs Extension Relations Discussion of GDM The Graph-Based Update Language GUL Patterns The Addition The Deletion The Reduction Typing GUL Typing Patterns Typing Additions Typing Deletions Typing the Reduction Conclusion Characterizing the Temporal and Semantic Coherency of Broadcast-Based Data Dissemination Introduction The Model Model Assumption Update Period Preliminary Definitions Temporal Coherency A Temporal Coherency Framework Achieving Temporal Coherency Semantic Coherency A Semantic Coherency Framework Relation to Temporal Coherency Achieving Semantic Coherency Conclusions An Efficient Indexing Scheme for Multi-dimensional Moving Objects* Introduction Related Work The Contribution of the Paper Duality Transformations MB-Index for Answering Polyhedral Queries in $@mathbb R^d$ Bounding the Average Query Performance Experimental Results Conclusion Nearest Neighbors Can Be Found Efficiently If the Dimension Is Small Relative to the Input Size Introduction Previous Results Our Results Motivation Meaningfulness of the Average Case Exact versus Approximate Our Data Structure An Average-Case Analysis A Representation for the Nodes The Query Time The Storage Space Secondary Memory Delaunay Graphs for Random Point Sets High-Probability Bounds for the Degree The Expected Degree Conclusions Author Index This Volume Collects The Papers Presented At Icdt 2003, The 9th International Conferenceondatabasetheory,heldfrom8to10january2003intherettorato Dell’universit` A Di Siena, Siena, Italy. Icdt (http://alpha.luc.ac.be/ ̃lucp1080/icdt/) Has Now A Long T- Dition Of International Conferences, Providing A Biennial Scienti?c Forum For The Communicationofhigh-qualityresearchresultsontheoreticalaspectsofallforms Of Database Systems And Database Technology. Icdt Is Traditionally Held In - Storic European Locations: Rome In 1986, Bruges In 1988, Paris In 1990, Berlin In 1992, Prague In 1995, Delphi In 1997, Jerusalem In 1999, And London In 2001. Icdthasmergedwiththesymposiumonmathematicalfundamentalsofda- Base Systems (mfdbs), Initiated In Dresden In 1987, And Continued In Visegrad In 1989 And Rostock In 1991. This Volume Contains 26 Papers Selected From 92 Submissions, Plus Three Invited Papers By Hector Garcia-molina, Yannis Ioannidis, And Limsoon Wong. We Wish To Thank All The Authors Who Submitted Papers, The Members Of The Program Committee For Their E?orts In Reviewing And Selecting The Papers, The External Referees, The Organizing Committee, And The Sponsors For Their Support. Diego Calvanese Maurizio Lenzerini Rajeev Motwani Organization Icdt 2003 Was Organized By The Dipartimento Di Informatica E Sistemistica, Universit` A Di Roma “la Sapienza”. Invited Papers -- Open Problems In Data-sharing Peer-to-peer Systems -- Approximations In Database Systems -- Bioinformatics Adventures In Database Research -- Reasoning About Xml Schemas And Queries -- Incremental Validation Of Xml Documents -- Typechecking Top-down Uniform Unranked Tree Transducers -- Structural Properties Of Xpath Fragments -- On Reasoning About Structural Equality In Xml: A Description Logic Approach -- Aggregate Queries -- Containment Of Aggregate Queries -- Auditing Sum Queries -- Crb-tree: An Efficient Indexing Scheme For Range-aggregate Queries -- Optimal Range Max Datacube For Fixed Dimensions -- Query Evaluation -- Processing Xml Streams With Deterministic Automata -- Deciding Termination Of Query Evaluation In Transitive-closure Logics For Constraint Databases -- Query Rewriting And Reformulation -- Data Exchange: Semantics And Query Answering -- Reformulation Of Xml Queries And Constraints -- New Rewritings And Optimizations For Regular Path Queries -- Database Interrogation Using Conjunctive Queries -- Semistructured Versus Structured Data -- On The Difficulty Of Finding Optimal Relational Decompositions For Xml Workloads: A Complexity Theoretic Perspective -- Generating Relations From Xml Documents -- Query Containment -- Containment For Xpath Fragments Under Dtd Constraints -- Xpath Containment In The Presence Of Disjunction, Dtds, And Variables -- Decidable Containment Of Recursive Queries -- Containment Of Conjunctive Queries With Safe Negation -- Consistency And Incompleteness -- Probabilistic Interval Xml -- Condensed Representation Of Database Repairs For Consistent Query Answering -- Typing Graph-manipulation Operations -- Characterizing The Temporal And Semantic Coherency Of Broadcast-based Data Dissemination -- Data Structures -- An Efficient Indexing Scheme For Multi-dimensional Moving Objects -- Nearest Neighbors Can Be Found Efficiently If The Dimension Is Small Relative To The Input Size. Edited By Diego Calvanese, Maurizio Lenzerini, Rajeev Motwani. This Book Constitutes The Refereed Proceedings Of The 9th International Conference On Database Theory, Icdt 2002, Held In Siena, Italy In January 2002. The 26 Revised Full Papers Presented Together With 3 Invited Articles Were Carefully Reviewed And Selected From 92 Submissions. The Papers Are Organized In Topical Sections On Reasoning About Xml Schemas And Queries, Aggregate Queries, Query Evaluation, Query Rewriting And Reformulation, Semistructured Versus Structured Data, Query Containment, Consistency And Incompleteness, And Data Structures.