liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A prototype of a descriptive type system for Xcerpt
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
2006 (English)In: Proceedings of the Fourth Workshop on Principles and Practice of Semantic Web Reasoning. Budva, Montenegro, 2006, Vol. LNCS 4187, 262-275 p.Conference paper, Published paper (Refereed)
Abstract [en]

The paper presents a prototype implementation of a descriptive type system for the XML query language Xcerpt. Its intended application is finding (a certain kind of) errors in programs. The implementation is able to check correctness of an Xcerpt program with respect to a type specification. A type specification describes a set of possible data bases to which the program is to be applied and an expected set of results. Program correctness means that all its results are in the expected set. Failure of a correctness check suggests an error in the program. Under certain conditions such failure indeed means that the program is incorrect.

Current implementation works for a restricted, but interesting subset of Xcerpt. The system provides (approximations of) the set of program results and the sets of values of program variables; this information is useful for programmers (and is produced even when the specification of the expected set of results is not given).

Place, publisher, year, edition, pages
2006. Vol. LNCS 4187, 262-275 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (Print) 1611-3349 (Online) ; 4187
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:liu:diva-12916DOI: 10.1007/11853107_21OAI: oai:DiVA.org:liu-12916DiVA: diva2:17390
Available from: 2008-01-29 Created: 2008-01-29 Last updated: 2009-06-08
In thesis
1. Types for XML with Application to Xcerpt
Open this publication in new window or tab >>Types for XML with Application to Xcerpt
2008 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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. A non standard way of assuring termination of fixed point computations is proposed, as standard approaches are too inefficient. The method is proved correct wrt. the formal semantics of Xcerpt.

We also present a method for type checking of programs. A success of type checking implies that the program is correct wrt. its type specification. This means that the program produces results of the specified type whenever it is applied to data of the given type. On the other hand, a failure of type checking suggests that the program may be incorrect. Under certain conditions (on the program and on the type specification), the program is actually incorrect whenever the proof attempt fails.

A prototype implementation of the type system has been developed and usefulness of the approach is illustrated on example programs.

In addition, the thesis outlines possibility of employing semantic types (ontologies) in Xcerpt. Introducing ontology classes into Type Definitions makes possible discovering some errors related to the semantics of data queried by Xcerpt. We also extend Xcerpt with a mechanism of combining XML queries with ontology queries. The approach employs an existing Xcerpt engine and an ontology reasoner; no modifications are required.

Place, publisher, year, edition, pages
Institutionen för datavetenskap, 2008. 175 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1156
Keyword
XML, types, Xcerpt, XML schema, ontologies, XML querying
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-10687 (URN)978-91-85895-08-3 (ISBN)
Public defence
2008-02-19, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2008-01-29 Created: 2008-01-29 Last updated: 2015-03-13

Open Access in DiVA

No full text

Other links

Publisher's full textLink to Ph.D. thesis

Authority records BETA

Wilk, ArturDrabent, Włodzimierz

Search in DiVA

By author/editor
Wilk, ArturDrabent, Włodzimierz
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 55 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf