Back to Search
Start Over
Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages
- Source :
- PODS
- Publication Year :
- 2010
- Publisher :
- ACM, 2010.
-
Abstract
- XML Schema Definitions (XSDs) can be adequately abstracted by the single-type regular three languages. It is well-known, tha these form a strict subclass of the robust class of regular unranked three languages. Sadly, in this respect, XSDs are not closed under the basic operations of union and set difference, complicating important tasks in schema integration and evolution. The purpose of this paper is to investigate how the union and difference of two XSDs can be approximated within the framework of single-type regular three languages. We consider both optimal lower and upper approximations. We also adress the more general question of how to approximate an arbitrary regular tree language by an XSD and consider the complexity of associated decision problems.
- Subjects :
- Document Structure Description
Theoretical computer science
Programming language
Computer science
XML validation
0102 computer and information sciences
02 engineering and technology
computer.software_genre
01 natural sciences
Schema (genetic algorithms)
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
010201 computation theory & mathematics
Document Schema Definition Languages
XML Schema Editor
Regular Language description for XML
XML
XML schema
approximation
complexity
Regular tree grammar
ComputingMethodologies_DOCUMENTANDTEXTPROCESSING
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
RELAX NG
computer
Computer Science::Databases
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- PODS
- Accession number :
- edsair.doi.dedup.....87f49edbd5d58a1cb8b4e030ec7441e6