Database Programming Language

✍ Scribed by Gosta Grahne (editor), Giorgia Ghelli (editor)

• Publisher: Springer
• Year: 2002
• Tongue: English
• Leaves: 353
• Category: Library

✦ Synopsis

(Limburg), Benjamin Pierce (Philadelphia), Chris Ramming (Menlo Park), J´ erˆ ome Sim´ eon (Murray Hill), Victor Vianu (San Diego), and Philip Wadler (Basking Ridge).

✦ Table of Contents

Database Programming Languages
Preface
Organization
Table of Contents
Typechecking for Semistructured Data
1 The Problem
2 Background
2.1 The Data
2.2 The Types
2.3 The Query Languages
3 Type Inference and Its Limitations
4 Type Checking and Its Limitations
4.1 Typechecking TreeQL
4.2 Typechecking for RecQL
5 Related Work
6 Discussion
References
Optimization Properties for Classes of Conjunctive Regular Path Queries
1 Introduction
2 Queries and Constraints
3 Summary of Results
4 Upper Bounds
5 Lower Bounds
6 Containment under Dependencies
7 Rewriting with Views under Dependencies
8 Conclusions
References
View-Based Query Answering and Query Containment over Semistructured Data
1 Introduction
2 Databases and Queries
3 Relationship between QA and QC
4 QA and QC for C2RPQ$_c$'s
4.1 Canonical Databases
4.2 Automaton Accepting Canonical DBs
4.3 Automaton for a Single Tuple
4.4 Automaton for Whole Answer Set
5 QA and QC for T2RPQ$_c$'s
5.1 Two-Way Alternating Automata
5.2 T2RPQ$_c$'s
5.3 Automaton for a Single Tuple
5.4 Automaton for Whole Answer Set
6 Conclusions
References
Model-Checking Based Data Retrieval
1 Introduction
2 Transition Systems and textit{CTL}
3 Syntax of the Query Language $mathbb {W}$
4 $mathbb {W}$-Instances as Kripke Transition System
5 Temporal Logic Semantics of $mathbb {W}$-Queries
5.1 Technique Overview
5.2 Admitted Queries
5.3 Query Translation
5.4 Acyclic Graphs
5.5 Cyclic Queries
6 Complexity Issues and Implementation of the Method
7 Comparison and Applicability of the Method
8 Conclusions and Future Work
References
A Temporal Query Language for OLAP: Implementation and a Case Study
1 Introduction
2 The Temporal Multidimensional Model
2.1 Temporal Dimensions
2.2 Temporal Fact Tables
2.3 The Case Study: A Medical Data Warehouse
3 TOLAP
4 Implementation
5 Translating {em TOLAP} into SQL
5.1 Translating {em TOLAP } Atoms
5.2 {em TOLAP } Rules
5.3 Join Elimination
5.4 Subquery Pruning
5.5 Translating to TSQL2
6 The Medical Clinic Case Study
6.1 Data Preparation
6.2 Discussion of Results
7 Conclusion and Future Work
References
Attribute Metadata for Relational OLAP and Data Mining
1 Introduction
2 The Domain Algebra
2.1 Actualization: Relational Algebra
2.2 Multidimensional Databases
3 Attribute Metadata
3.1 The General DataCube
3.2 The Decision Tree
4 Nested Relations
4.1 Association Data Mining
5 The Transpose Operator
5.1 Classification Data Mining
6 Conclusion
References
On Monotone Data Mining Languages
1 Introduction
2 Introductory Example
3 DML Syntax and Semantics
3.1 Syntax
3.2 DML Semantics
4 Additional Examples
4.1 Frequent Itemsets and Non-trivial Functional Dependencies
4.2 The Use of Binary Schema-Variables: Inclusion Dependencies
5 Subset-Closed and Superset-Closed DML Queries
6 Positive DML Queries
7 A Superset-Closed DML Query with a Single Schema-Variable That Cannot Be Expressed Positively
8 Mappings
8.1 Structure Encodings
8.2 Interpretation Encodings
8.3 Formula Mappings
9 A-priori and Finitely Monotone Properties
10 Discussion and Future Work
References
Reasoning about Keys for XML
1 Introduction
2 Keys
2.1 A Tree Model and Value Equality
2.2 Path Languages
2.3 A Key Constraint Language for XML
2.4 Decision Problems
3 Key Implication
3.1 Inclusion of $PL$ Expressions
3.2 Axiomatization for Absolute Key Implication
3.3 Axiomatization for Key Implication
4 Discussion
References
TAX: A Tree Algebra for XML
1 Introduction
2 Design Considerations
3 Data Model
4 Predicates and Patterns
4.1 Allowable Predicates
4.2 Pattern Tree
4.3 Witness Tree
4.4 Tree Value Function
5 The Operators
5.1 Selection
5.2 Projection
5.3 Product
5.4 Grouping
6 Expressive Power of TAX
7 Related Work
8 Summary and Status
References
A Rule-Based Querying and Updating Language for XML
1 Introduction
2 XPath-Logic: Adding Variable Bindings to XPath
3 XML Instances As Semantical Structures
4 XPathLog: The Horn Fragment of XPath-Logic
4.1 Query Semantics: Data Model
4.2 Semantics of Expressions
4.3 Queries in XPathLog
5 Updates: XPathLog Rules and Programs
5.1 Updates in XPathLog
5.2 Atomization
5.3 Updates
5.4 Formal Semantics of XPathLog Programs
6 Related Work and Conclusion
References
Linear Approximation of Semi-algebraic Spatial Databases Using Transitive Closure Logic, in Arbitrary Dimension
1 Introduction
2 Preliminaries
3 Local Topological Characterization
3.1 Expressibility of the Cone Radius in FO
3.2 Uniform Cone Radius Decomposition
4 Linearization of a Semi-algebraic Set
4.1 Construction of the Box Covering
4.2 Inductive Application of the Algorithm
4.3 Expressing the Construction in Transitive Closure Logic
5 Completeness Result
6 Concluding Remarks
References
A Theory of Spatio-Temporal Database Queries
1 Introduction
2 Definitions and Preliminaries
2.1 Spatio-temporal Databases
2.2 Spatio-temporal Database Queries
2.3 Constraint Query Languages
3 Spatio-temporal Genericity
3.1 Temporal Condition
3.2 Spatial and Spatio-temporal Conditions
3.3 Physical Conditions
3.4 Spatio-temporal Genericity: Definition
4 Sound and Complete Languages for the Generic First-Order Spatio-temporal Queries
4.1 Genericity for Time-Independent Transformations
4.2 Applications to Physics
4.3 Genericity for Time-Dependent Transformations
5 Sound and Complete Languages for the Generic Computable Spatio-temporal Queries
5.1 Genericity for Time-Independent Transformations
5.2 Applications to Physics
5.3 Genericity for Time-Dependent Transformations
6 Conclusion and Discussion
References
An Application-Specific Database
1 Introduction
2 Requirements
3 Hancock Maps
3.1 Map Declarations
3.2 Map Operations
4 Implementation
4.1 Defining Key Types
5 Performance Results
6 A Database Comparison
6.1 The Hancock Implementation
6.2 The Daytona Implementation
6.3 Experimental Results
6.4 Summary
7 Conclusion
References
A Model Theory for Generic Schema Management
1 Introduction
2 Schemas
3 Schema Morphisms
4 Schema Integration
5 Generic Schema Transformation Framework
6 An Application of Schema Transformation Frameworks
7 Conclusions and Related Work
References
View Serializable Updates of Concurrent Index Structures
1 Introduction
2 B-Trees
2.1 Preliminaries
2.2 Search
2.3 Insertion
2.3.1 Remarks on {em main_insert}
2.4 Deletion
2.4.1 Remarks on {em main_delete}
2.5 Correctness
2.5.1 Proposition
2.5.2 Definition
2.5.3 Theorem
2.5.4 Lemma
2.5.5 Definition
2.5.6 Lemma
3 Binary Search Trees
3.1 Preliminaries
3.2 Search
3.3 Insertion
3.4 Deletion
3.4.1 Remarks
3.5 Correctness
3.5.1 Proposition
3.5.2 Theorem
3.5.3 Lemma
3.5.4 Definition
3.5.5 Lemma
4 Conclusions and Open Problems
References
SQL4X: A Flexible Query Language for XML and Relational Databases
1 Introduction
2 Data Model
3 Language Definition
3.1 {tt FROM}xspace Clause Extensions
3.2 {tt SELECT}xspace Clause Extensions
3.3 Advanced Features
4 Relation-Generating Queries
4.1 Syntax and Semantics
4.2 Containment of {sf Datalog${4x}$} Queries
4.3 Extending Containment Results
5 Document-Generating Queries
5.1 Syntax and Semantics
5.2 Containment of {sf Tree-Datalog${4x}$} Queries
6 Related Work and Conclusion
References
ERX-QL: Querying an Entity-Relationship DB to Obtain XML Documents
1 Introduction
2 ERX Data Model
2.1 Inter-module Schema
2.2 Intra-module Schema
2.3 Case Study
3 ERX Query Language
3.1 Basic Structure
3.2 Managing Relationships and Links
3.3 Nested Queries
3.4 Query Libraries
4 Conclusions
References
Optimising Active Database Rules by Partial Evaluation and Abstract Interpretation
1 Introduction
2 Rule Optimisation Using Abstract Interpretation
2.1 The Rule Execution Semantics
2.2 The Abstract Execution Semantics
2.3 Mixed Execution Semantics
3 Rule Optimisation Using Partial Evaluation
4 Specialising for Possible Sequences of Actions
5 Dynamic Specialisation for Definite Sequences of Actions
6 Discussion
6.1 Related Work
7 Conclusions
References
Simulation of Advanced Transaction Models Using GOLOG
1 Introduction
2 Logical Foundations
3 The Specification Framework
4 Flat Transactions
5 Closed Nested Transactions
6 Simulating ATMs
6.1 Well-Formed GOLOG Programs
6.2 Semantics of GOLOG Programs
6.3 Simulation
7 Related Work
8 Conclusion and Future Work
References
Author Index