Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/1662
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGELADE, Wouter-
dc.contributor.authorMARTENS, Wim-
dc.contributor.authorNEVEN, Frank-
dc.date.accessioned2007-06-21T09:31:31Z-
dc.date.available2007-06-21T09:31:31Z-
dc.date.issued2007-
dc.identifier.citationProceedings of International Conference on Database Theory. p. 269-283-
dc.identifier.isbn3-540-69269-X-
dc.identifier.issn1611-3349-
dc.identifier.urihttp://hdl.handle.net/1942/1662-
dc.description.abstractThe presence of a schema offers many advantages in processing, translating, querying, and storage of XML data. Basic decision problems like equivalence, inclusion, and non-emptiness 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 remain within the regular languages, their presence or absence has 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.format.extent209075 bytes-
dc.format.mimetypeapplication/pdf-
dc.language.isoen-
dc.publisherSpringer-
dc.relation.ispartofseriesLecture notes in computer science-
dc.subject.otherComplexity, XML Schema, Decision problems-
dc.titleOptimizing Schema Languages for XML: Numerical Constraints and Interleaving-
dc.typeProceedings Paper-
local.bibliographicCitation.authorsSchwentick, Thomas-
local.bibliographicCitation.authorsSuciu, Dan-
local.bibliographicCitation.conferencedate2007-
local.bibliographicCitation.conferencenameInternational Conference on Database Theory-
dc.bibliographicCitation.conferencenr11-
local.bibliographicCitation.conferenceplaceBarcelona-
dc.identifier.epage283-
dc.identifier.spage269-
local.bibliographicCitation.jcatC1-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
local.relation.ispartofseriesnr4353-
dc.bibliographicCitation.oldjcatC1-
dc.identifier.doi10.1007/11965893_19-
dc.identifier.isi000244800500019-
local.bibliographicCitation.btitleProceedings of International Conference on Database Theory-
item.fulltextWith Fulltext-
item.accessRightsOpen Access-
item.contributorNEVEN, Frank-
item.contributorMARTENS, Wim-
item.contributorGELADE, Wouter-
item.fullcitationGELADE, Wouter; MARTENS, Wim & NEVEN, Frank (2007) Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. In: Proceedings of International Conference on Database Theory. p. 269-283.-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
icdt07.pdf204.17 kBAdobe PDFView/Open
Show simple item record

SCOPUSTM   
Citations

17
checked on Sep 4, 2020

WEB OF SCIENCETM
Citations

12
checked on Jun 29, 2022

Page view(s)

58
checked on Jun 30, 2022

Download(s)

240
checked on Jun 30, 2022

Google ScholarTM

Check

Altmetric


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