Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/1957
Title: Succinctness of Pattern-Based Schema Languages for XML
Authors: GELADE, Wouter 
NEVEN, Frank 
Issue Date: 2007
Publisher: Springer Berlin / Heidelberg
Source: Proceedings of Database Programming Languages. p. 201-215
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 4797
Abstract: Martens et al. defined a pattern-based specification language equivalent in expressive power to the widely adopted XML Schema definitions (XSDs). This language consists of rules of the form (r,s) where r and s are regular expressions and can be seen as a type-free extension of DTDs with vertical regular expressions. Sets of such rules can be interpreted both in an existential or universal way. In the present paper, we study the succinctness of both semantics w.r.t. each other and w.r.t. the common abstraction of XSDs in terms of single-type extended DTDs. The investigation is carried out relative to three kinds of vertical pattern languages: regular, linear, and strongly linear patterns. We also consider the complexity of the simplification problem for each of the considered pattern-based schema’s.
Keywords: XML, Schema Languages, Succinctness, Complexity
Document URI: http://hdl.handle.net/1942/1957
ISBN: 978-3-540-75986-7
DOI: 10.1007/978-3-540-75987-4_14
ISI #: 000250804700014
Category: A1
Type: Journal Contribution
Validations: ecoom 2008
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
dbpl07.pdfExtended version349 kBAdobe PDFView/Open
Show full item record

SCOPUSTM   
Citations

2
checked on Sep 2, 2020

WEB OF SCIENCETM
Citations

1
checked on May 21, 2022

Page view(s)

46
checked on May 23, 2022

Download(s)

94
checked on May 23, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.