Inferring a relax NG schema from XML documents

Guen Hae Kim; Sang Ki Ko; Yo Sub Han

doi:10.1007/978-3-319-30000-9_31

Inferring a relax NG schema from XML documents

Guen Hae Kim, Sang Ki Ko, Yo Sub Han

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

An XML schema specifies the structural properties of XML documents generated from the schema and, thus, is useful to manage XML data efficiently. However, there are often XML documents without a valid schema or with an incorrect schema in practice. This leads us to study the problem of inferring a Relax NG schema from a set of XML documents that are presumably generated from a specific XML schema. Relax NG is an XML schema language developed for the next generation of XML schema languages such as document type definitions (DTDs) and XML Schema Definitions (XSDs). Regular hedge grammars accept regular tree languages and the design of Relax NG is closely related with regular hedge grammars. We develop an XML schema inference system using hedge grammars. We employ a genetic algorithm and state elimination heuristics in the process of retrieving a concise Relax NG schema. We present experimental results using real-world benchmark.

Original language	English
Title of host publication	Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings
Editors	Bianca Truthe, Jan Janoušek, Adrian-Horia Dediu, Carlos Martín-Vide
Publisher	Springer Verlag
Pages	400-411
Number of pages	12
ISBN (Print)	9783319299990
DOIs	https://doi.org/10.1007/978-3-319-30000-9_31
Publication status	Published - 2016
Event	10th International Conference on Language and Automata Theory and Applications, LATA 2016 - Prague, Czech Republic Duration: 2016 Mar 14 → 2016 Mar 18

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9618
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th International Conference on Language and Automata Theory and Applications, LATA 2016
Country/Territory	Czech Republic
City	Prague
Period	16/3/14 → 16/3/18

Bibliographical note

Publisher Copyright:
© Springer International Publishing Switzerland 2016.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-30000-9_31

Cite this

Kim, G. H., Ko, S. K., & Han, Y. S. (2016). Inferring a relax NG schema from XML documents. In B. Truthe, J. Janoušek, A.-H. Dediu, & C. Martín-Vide (Eds.), Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings (pp. 400-411). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9618). Springer Verlag. https://doi.org/10.1007/978-3-319-30000-9_31

Kim, Guen Hae ; Ko, Sang Ki ; Han, Yo Sub. / Inferring a relax NG schema from XML documents. Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings. editor / Bianca Truthe ; Jan Janoušek ; Adrian-Horia Dediu ; Carlos Martín-Vide. Springer Verlag, 2016. pp. 400-411 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a7375fb22f8345a992b85904b7a80b60,

title = "Inferring a relax NG schema from XML documents",

abstract = "An XML schema specifies the structural properties of XML documents generated from the schema and, thus, is useful to manage XML data efficiently. However, there are often XML documents without a valid schema or with an incorrect schema in practice. This leads us to study the problem of inferring a Relax NG schema from a set of XML documents that are presumably generated from a specific XML schema. Relax NG is an XML schema language developed for the next generation of XML schema languages such as document type definitions (DTDs) and XML Schema Definitions (XSDs). Regular hedge grammars accept regular tree languages and the design of Relax NG is closely related with regular hedge grammars. We develop an XML schema inference system using hedge grammars. We employ a genetic algorithm and state elimination heuristics in the process of retrieving a concise Relax NG schema. We present experimental results using real-world benchmark.",

keywords = "Genetic algorithm, Regular hedge grammar, Relax NG, XML schema inference",

author = "Kim, {Guen Hae} and Ko, {Sang Ki} and Han, {Yo Sub}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 10th International Conference on Language and Automata Theory and Applications, LATA 2016 ; Conference date: 14-03-2016 Through 18-03-2016",

year = "2016",

doi = "10.1007/978-3-319-30000-9_31",

language = "English",

isbn = "9783319299990",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "400--411",

editor = "Bianca Truthe and Jan Janou{\v s}ek and Adrian-Horia Dediu and Carlos Mart{\'i}n-Vide",

booktitle = "Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings",

address = "Germany",

}

Kim, GH, Ko, SK & Han, YS 2016, Inferring a relax NG schema from XML documents. in B Truthe, J Janoušek, A-H Dediu & C Martín-Vide (eds), Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9618, Springer Verlag, pp. 400-411, 10th International Conference on Language and Automata Theory and Applications, LATA 2016, Prague, Czech Republic, 16/3/14. https://doi.org/10.1007/978-3-319-30000-9_31

Inferring a relax NG schema from XML documents. / Kim, Guen Hae; Ko, Sang Ki; Han, Yo Sub.
Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings. ed. / Bianca Truthe; Jan Janoušek; Adrian-Horia Dediu; Carlos Martín-Vide. Springer Verlag, 2016. p. 400-411 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9618).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Inferring a relax NG schema from XML documents

AU - Kim, Guen Hae

AU - Ko, Sang Ki

AU - Han, Yo Sub

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - An XML schema specifies the structural properties of XML documents generated from the schema and, thus, is useful to manage XML data efficiently. However, there are often XML documents without a valid schema or with an incorrect schema in practice. This leads us to study the problem of inferring a Relax NG schema from a set of XML documents that are presumably generated from a specific XML schema. Relax NG is an XML schema language developed for the next generation of XML schema languages such as document type definitions (DTDs) and XML Schema Definitions (XSDs). Regular hedge grammars accept regular tree languages and the design of Relax NG is closely related with regular hedge grammars. We develop an XML schema inference system using hedge grammars. We employ a genetic algorithm and state elimination heuristics in the process of retrieving a concise Relax NG schema. We present experimental results using real-world benchmark.

AB - An XML schema specifies the structural properties of XML documents generated from the schema and, thus, is useful to manage XML data efficiently. However, there are often XML documents without a valid schema or with an incorrect schema in practice. This leads us to study the problem of inferring a Relax NG schema from a set of XML documents that are presumably generated from a specific XML schema. Relax NG is an XML schema language developed for the next generation of XML schema languages such as document type definitions (DTDs) and XML Schema Definitions (XSDs). Regular hedge grammars accept regular tree languages and the design of Relax NG is closely related with regular hedge grammars. We develop an XML schema inference system using hedge grammars. We employ a genetic algorithm and state elimination heuristics in the process of retrieving a concise Relax NG schema. We present experimental results using real-world benchmark.

KW - Genetic algorithm

KW - Regular hedge grammar

KW - Relax NG

KW - XML schema inference

UR - http://www.scopus.com/inward/record.url?scp=84960341938&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84960341938&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-30000-9_31

DO - 10.1007/978-3-319-30000-9_31

M3 - Conference contribution

AN - SCOPUS:84960341938

SN - 9783319299990

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 400

EP - 411

BT - Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings

A2 - Truthe, Bianca

A2 - Janoušek, Jan

A2 - Dediu, Adrian-Horia

A2 - Martín-Vide, Carlos

PB - Springer Verlag

T2 - 10th International Conference on Language and Automata Theory and Applications, LATA 2016

Y2 - 14 March 2016 through 18 March 2016

ER -

Kim GH, Ko SK, Han YS. Inferring a relax NG schema from XML documents. In Truthe B, Janoušek J, Dediu AH, Martín-Vide C, editors, Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Proceedings. Springer Verlag. 2016. p. 400-411. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-30000-9_31

Inferring a relax NG schema from XML documents

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this