Descriptive Types for XML Query Language Xcerpt

The work presented in this thesis is related to XML (Extensible Markup Language) developed by World Wide Web Consortium (W3C)1. XML has be-come a dominant standard in the Internet and majority of data being exchanged on the Web is encoded using it.

The thesis presents a type system for a substantial fragment of XML query language Xcerpt. The system is descriptive; the types associated with Xcerpt constructs are sets of data terms and approximate the semantics of the constructs. A formalism of Type Definitions, related to XML schema languages, is adopted to specify such sets. The type system is presented as typing rules which provide a basis for type inference and type checking algorithms, used in a prototype implementation…


1 Introduction
1.1 The Problem and the Motivation
1.2 The Approach
1.3 The Results
1.4 Thesis Overview
2 Background
2.1 Introduction to Xcerpt
2.1.1 Data Terms
2.1.2 Query Terms
2.1.3 Queries
2.1.4 Construct Terms
2.1.5 Query Rules
2.1.6 Programs
2.2 XML Schema Languages
2.2.1 DTD
2.2.2 XML Schema
2.2.3 Relax NG
3 Type Specification
3.1 Type Definitions
3.1.1 Proper Type Definitions
3.2 Operations on Types
3.2.1 Emptiness Check
3.2.2 Intersection of Types
3.2.3 Type Inclusion
3.3 Type Definitions and XML Schema Languages
3.3.1 DTD
3.3.2 XML Schema
3.3.3 Relax NG
4 Reasoning about Types
4.1 Motivation
4.2 Variable-type Mappings
4.3 Typing Rules for Xcerpt
4.3.1 Query terms
4.3.2 Queries
4.3.3 Construct terms
4.3.4 Xcerpt query rules
4.3.5 Xcerpt programs
4.3.6 Exactness of the Typing Rules
4.4 Type Inference Algorithm
4.4.1 Type Inference for a Query Rule
4.4.2 Type Inference for a Multiple Query Rule Program
4.5 Type Correctness of Programs
4.6 Possible Extensions
4.6.1 Type Correctness of Recursive Programs
4.6.2 The Most General Type
4.6.3 Correctness Checking Based on Types of Variables
5 The Prototype
5.1 Usage of the Prototype
5.2 Overall Structure of the Source Code
6 Use Cases
6.1 Type Inference
6.1.1 Manual Type Checking
6.1.2 Empty Result Type
6.1.3 Program Documentation
6.2 Result Type Correctness
7 Conclusions

Author: Wilk, Artur

Source: Linköping University

Download URL 2: Visit Now

Leave a Comment