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
Types for XML with Application to Xcerpt
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology.
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 [en]
XML, types, Xcerpt, XML schema, ontologies, XML querying
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-10687ISBN: 978-91-85895-08-3 (print)OAI: oai:DiVA.org:liu-10687DiVA: diva2:17393
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
List of papers
1. On types for XML query language Xcerpt
Open this publication in new window or tab >>On types for XML query language Xcerpt
2003 (English)In: Principles and Practice of Semantic Web Reasoning: International Workshop, PPSWR 2003, Mumbai, India, December 8, 2003. Proceedings / [ed] François Bry, Nicola Henze, Jan Małuszyński, Springer Berlin/Heidelberg, 2003, Vol. 2901, 128-145 p.Conference paper, Published paper (Refereed)
Abstract [en]

Our intention is to provide a type system for rule languages used in web applications. In this work we deal with an XML query language Xcerpt. Our types are sets of documents. We represent XML data as so called data terms and propose a formalism to define sets of data terms. The formalism is a generalization of tree automata, the defined sets roughly correspond to sets of documents definable by means of XML schema languages, like DTD and XML Schema. The main contribution of this paper is an algorithm for computing the type of possible results of an Xcerpt rule, given the type of the database. The algorithm can be used to automatically check correctness of Xcerpt programs with respect to type specifications. For non recursive Xcerpt programs it can also be used to compute the type of program results.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2003
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 2901
National Category
Language Technology (Computational Linguistics)
Identifiers
urn:nbn:se:liu:diva-48429 (URN)10.1007/978-3-540-24572-8_9 (DOI)000188097100009 ()978-3-540-20582-1 (ISBN)978-3-540-24572-8 (ISBN)3-540-20582-9 (ISBN)
Conference
International Workshop, PPSWR 2003, Mumbai, India, December 8, 2003
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2015-03-13Bibliographically approved
2. Descriptive typing rules for Xcerpt
Open this publication in new window or tab >>Descriptive typing rules for Xcerpt
2005 (English)In: Proceedings of the Third Workshop on Principles and Practice of Semantic Web Reasoning. Dagstuhl, Germany, 2005, Vol. LNCS 3703, 85-100 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present typing rules for the Web query language Xcerpt.

The rules provide a descriptive type system: the typing of a program is an

approximation of its semantics. The rules can also be seen as an abstract

form of a type inference algorithm (presented in previous work), and as a

stage in a formal soundness proof of the algorithm. The paper considers

a substantial fragment of Xcerpt; the main restriction is that we deal

with data terms corresponding to trees (instead of general graphs), and

we do not deal with Xcerpt rule chaining. We provide a formal semantics

for the fragment of Xcerpt and a soundness theorem for the presented

type system.

 

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-12914 (URN)
Available from: 2008-01-29 Created: 2008-01-29 Last updated: 2009-04-28
3. XML Querying Using Ontological Information
Open this publication in new window or tab >>XML Querying Using Ontological Information
2006 (English)In: Principles and Practice of Semantic Web Reasoning / [ed] Jóse Júlio Alferes, James Bailey, Wolfgang May, Uta Schwertel, Springer Berlin/Heidelberg, 2006, Vol. LNCS 4187, 190-203 p.Conference paper, Published paper (Refereed)
Abstract [en]

The paper addresses the problem of using semantic annotations in XML documents for better querying XML data. We assume that the annotations refer to an ontology defined in OWL (Web Ontology Language). The intention is then to combine syntactic querying techniques on XML documents with OWL ontology reasoning to filter out semantically irrelevant answers. The solution presented in this paper is an extension of the declarative rule-based XML query and transformation language Xcerpt. The extension allows to interface an ontology reasoner from Xcerpt rules. This makes it possible to use Xcerpt to filter extracted XML data using ontological information. Additionally it allows to retrieve ontological information by sending semantic queries to a reasoner. The prototype implementation uses DIG (Description Logic interface) for communication with the OWL reasoner RacerPro where the ontology queries are answered.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2006
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 4187
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-12915 (URN)10.1007/11853107_14 (DOI)000241555100014 ()978-3-540-39586-7 (ISBN)e-978-3-540-39587-4 (ISBN)
Conference
4th International Workshop (PPSWR 2006), Budva, Montenegro, June 10-11, 2006
Available from: 2008-01-29 Created: 2008-01-29 Last updated: 2013-06-27
4. A prototype of a descriptive type system for Xcerpt
Open this publication in new window or tab >>A prototype of a descriptive type system for Xcerpt
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).

Series
Lecture Notes in Computer Science, ISSN 0302-9743 (Print) 1611-3349 (Online) ; 4187
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-12916 (URN)10.1007/11853107_21 (DOI)
Available from: 2008-01-29 Created: 2008-01-29 Last updated: 2009-06-08
5. Combining XML querying with ontology reasoning: Xcerpt and DIG
Open this publication in new window or tab >>Combining XML querying with ontology reasoning: Xcerpt and DIG
2006 (English)In: Online Proceedings of RuleMLWorkshop: Ontology and Rule Integration, Athens, Georgia, USA, 2006Conference paper, Published paper (Refereed)
Abstract [en]

The paper addresses the problem of combining ontological

reasoning with querying XML data. We present an extension

of a rule-based XML query and transformation language

Xcerpt. The extension allows to interface an ontology

reasoner from Xcerpt programs. In this way querying can

employ the ontology information, for instance to filter out

semantically irrelevant answers. Communication between

Xcerpt programs and ontology reasoner is based on DIG

interface. The extension can be implemented without modifying

the underlying Xcerpt implementation.

 

National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-12917 (URN)
Available from: 2008-01-29 Created: 2008-01-29
6. Extending XML Query Language Xcerpt by Ontology Queries
Open this publication in new window or tab >>Extending XML Query Language Xcerpt by Ontology Queries
2007 (English)In: Proceedings of IEEE / WIC / ACM International Conference on Web Intelligence (WI 2007), Silicon Valley, USA, IEEE , 2007, 447-451 p.Conference paper, Published paper (Refereed)
Abstract [en]

The paper addresses a problem of combining XML querying with ontology reasoning. We present an extension of a rule-based XML query and transformation language Xcerpt. The extension allows to interface an ontology reasoner from Xcerpt programs. In this way querying can employ the ontology information, for instance to filter out semantically irrelevant answers. The approach employs an existing Xcerpt engine and ontology reasoner; no modifications are required. We present the semantics of extended Xcerpt and an implementation algorithm. Communication between Xcerpt programs and ontology reasoner is based on DIG interface.

Place, publisher, year, edition, pages
IEEE, 2007
National Category
Computer Science
Identifiers
urn:nbn:se:liu:diva-12918 (URN)10.1109/WI.2007.128 (DOI)0-7695-3026-5 (ISBN)978-0-7695-3026-0 (ISBN)
Conference
IEEE/WIC/ACM International Conference on Web Intelligence
Available from: 2008-01-29 Created: 2008-01-29 Last updated: 2013-12-03

Open Access in DiVA

cover(30 kB)68 downloads
File information
File name COVER01.pdfFile size 30 kBChecksum SHA-1
cf563be4797bf63e1591937a2b35bc9b95f446c97a9069b4f5026589305ad62634e7e3ef
Type coverMimetype application/pdf
fulltext(1274 kB)592 downloads
File information
File name FULLTEXT01.pdfFile size 1274 kBChecksum SHA-1
e8a38a17f715d3927c8ee41c6439e884eabafa42333515ece6920a0022acff6506ebf6b3
Type fulltextMimetype application/pdf

Authority records BETA

Wilk, Artur

Search in DiVA

By author/editor
Wilk, Artur
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 592 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2204 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