On Subtyping of Tree-Structured Data: A Polynomial Approach
2004 (English)In: Principles and Practice of Semantic Web Reasoning, Second International Workshop, PPSWR 2004, St. Malo, France, Springer , 2004, 1-18 p.Conference paper (Refereed)
This paper discusses subtyping of tree-structured data encountered on the Web, e.g. XML and HTML data. Our long range objective is to define a type system for Web and/or Semantic Web query languages amenable to static type checking. We propose a type formalism motivated by XML Schema and accommodating two concepts of subtyping: inclusion subtyping (corresponding to XML Schema notion of type restriction) and extension subtyping (motivated by XML Schema's type extension). We present algorithms for checking both kinds of subtyping. The algorithms are polynomial if certain conditions are imposed on the type definitions, the conditions seem natural and not too restrictive.
Place, publisher, year, edition, pages
Springer , 2004. 1-18 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 3208
IdentifiersURN: urn:nbn:se:liu:diva-59991DOI: 10.1007/978-3-540-30122-6_1ISBN: 3-540-22961-2OAI: oai:DiVA.org:liu-59991DiVA: diva2:354526