Types for XML with Application to Xcerpt

XML data is often accompanied by type information, usually expressed by some schema language. Sometimes XML data can be related to ontologies defining classes of objects, such classes can also be interpreted as types. Type systems proved to be extremely useful in programming languages, for instance to automatically discover certain kinds of errors. This thesis deals with an XML query language Xcerpt, which originally has no underlying type system nor any provision for taking advantage of existing type information. We provide a type system for Xcerpt; it makes possible type inference and checking type correctness.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 is adapted to specify such sets. The formalism may be seen as a simplification and abstraction of XML schema languages. The type inference method, which is the core of this work, may be seen as abstract interpretation….


1 Introduction
2 Background
2.1 Introduction to Xcerpt
2.1.1 Language Overview
2.1.2 Formal Semantics
2.2 XML Schema Languages
2.2.1 DTD
2.2.2 XML Schema
2.2.3 Relax NG
2.3 XQuery and its Type System
2.3.1 Data Model
2.3.2 Language Constructs
2.3.3 Type System
2.4 DIG Interface
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 Type Inference for Xcerpt
4.2.1 Variable-type Mappings
4.2.2 Typing of Query Rules
4.2.3 Typing of Programs
4.2.4 Exactness of Type Inference
4.2.5 Type Inference Algorithm for Query Rules
4.2.6 Typing of Remaining Xcerpt Constructs
4.3 Type-based Rule Dependency
4.4 Discovering of Type Errors
4.5 Relation to XQuery Type System
5 Type System Prototype
5.1 Usage of the Prototype
5.2 Overall Structure of the Source Code
6 Use Cases
6.1 CD Store
6.2 Bibliography
6.2.1 No Result Type Specified
6.2.2 Result Type Specified
6.3 Bookstore
6.4 Clique of Friends
7 Semantic Types
7.1 Ontology Classes in Type Definitions
7.2 DigXcerpt: Ontology Queries in Xcerpt
7.2.1 Syntax and Semantics
7.2.2 Implementation
7.2.3 Discussion
8 Conclusions
A Proofs
A.1 Type System Correctness
A.1.1 Type Inference for Rules
A.1.2 Type Inference for Programs
A.2 Exactness of Inferred Type
A.3 Soundness of DigXcerpt Implementation
B Typechecker Results

Author: Wilk, Artur

Source: Linköping University

Download URL 2: Visit Now

Leave a Comment