Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/9220
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | GELADE, Wouter | - |
dc.contributor.author | MARTENS, Wim | - |
dc.contributor.author | NEVEN, Frank | - |
dc.date.accessioned | 2009-02-02T13:06:31Z | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | SIAM Journal on Computing, 38(5). p. 2021-2043 | - |
dc.identifier.issn | 0097-5397 | - |
dc.identifier.uri | http://hdl.handle.net/1942/9220 | - |
dc.description.abstract | The presence of a schema offers many advantages in processing, translating, querying, and storage of XML data. Basic decision problems such as equivalence, inclusion, and nonemptiness of intersection of schemas form the basic building blocks for schema optimization and integration, and algorithms for static analysis of transformations. It is thereby paramount to establish the exact complexity of these problems. Most common schema languages for XML can be adequately modeled by some kind of grammar with regular expressions at right-hand sides. In this paper, we observe that, apart from the usual regular operators of union, concatenation, and Kleene-star, schema languages also allow numerical occurrence constraints and interleaving operators. Although the expressiveness of these operators remains within the regular languages, the presence or absence of these operators has a significant impact on the complexity of the basic decision problems. We present a complete overview of the complexity of the basic decision problems for DTDs, XSDs, and Relax NG with regular expressions incorporating numerical occurrence constraints and interleaving. We also discuss chain regular expressions and the complexity of the schema simplification problem incorporating the new operators. | - |
dc.language.iso | en | - |
dc.rights | Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. | - |
dc.subject.other | XML schema languages; complexity; optimization; regular expressions | - |
dc.subject.other | XML schema languages; complexity; optimization; regular expressions | - |
dc.title | Optimizing Schema Languages for XML: Numerical Constraints and Interleaving | - |
dc.type | Journal Contribution | - |
local.bibliographicCitation.conferencename | 11th International Conference on Database Theory | - |
local.bibliographicCitation.conferenceplace | Barcelona, SPAIN, JAN 10-12, 2007 | - |
dc.identifier.epage | 2043 | - |
dc.identifier.issue | 5 | - |
dc.identifier.spage | 2021 | - |
dc.identifier.volume | 38 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1137/070697367 | - |
dc.identifier.isi | 000264353000015 | - |
item.contributor | GELADE, Wouter | - |
item.contributor | MARTENS, Wim | - |
item.contributor | NEVEN, Frank | - |
item.validation | ecoom 2010 | - |
item.fullcitation | GELADE, Wouter; MARTENS, Wim & NEVEN, Frank (2009) Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. In: SIAM Journal on Computing, 38(5). p. 2021-2043. | - |
item.accessRights | Open Access | - |
item.fulltext | With Fulltext | - |
crisitem.journal.issn | 0097-5397 | - |
crisitem.journal.eissn | 1095-7111 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
siam.pdf | Peer-reviewed author version | 322.46 kB | Adobe PDF | View/Open |
gelade2009.pdf Restricted Access | Published version | 337.05 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
18
checked on Sep 5, 2020
WEB OF SCIENCETM
Citations
17
checked on Apr 22, 2024
Page view(s)
102
checked on Sep 7, 2022
Download(s)
160
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.