Abstract
In this paper, we study the different steps of translation from XML to relational models, while maintaining semantic constraints. Our work is based on the theory of regular tree grammars, which provides a useful formal framework for understanding various aspects of XML schema languages. We first study two normal form representations for regular tree grammars. The first normal form representation, called NF1, is used in the two scenarios: (a) Several document validation algorithms use the NF1 representation as the first step in the validation process for efficiency reasons, and (b) NF1 representation can be used to check whether a given schema satisfies the structural constraints imposed by the schema language. The second normal form representation, called NF2, forms the basis for conversion of a set of type definitions in a schema language L 1 that supports union types (e.g., XML-Schema), to a schema language L 2 that does not support union types (e.g., SQL), and is used as the first step in our XML to relational conversion algorithm.
This author is partially supported by NSF grants 00861 16, 0085773, 9817773.
We differentiate two terms - XML schema(s) and XML-Schema. The former is a general term for schema in XML model while the latter refers in particular to the XML schema language proposed by W3C [17].
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P.V. Biron and A. Malhotra (Eds). “XML Schema Part 2: Datatypes”. W3C Recommendation, May 2001. http://www.w3.org/TR/xmlschema-2/. 89
P. Bohannon, J. Freire, P. Roy, and J. Simeon. “From XML Schema to Relations: A Cost-Based Approach to XML Storage”. In IEEE ICDE, San Jose, CA, Feb. 2002. 82, 83
P. Buneman, S. Davidson, W. Fan, C. Hara, and W. Tan. “Keys for XML”. In Int’l World Wide Web Conf. (WWW), Hong Kong, May 2001. 100
D. Chamberlin, D. Florescu, J. Robie, J. Siméon, and M. Stefanescu (Eds). “XQuery 1.0: An XML Query Language”. W3C Working Draft, Jun. 2001. http://www.w3.org/TR/2001/WD-xquery-20010607/. 81
J. Clark and M. Murata (Eds). “RELAX NG Tutorial”. OASIS Working Draft, Jun. 2001. http://www.oasis-open.org/committees/relax-ng/tutorial.html. 81, 83
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. “Tree Automata Techniques and Applications”, 1997. http://www.grappa.univ-lille3.fr/tata. 81
A. Deutsch, M. F. Fernandez, and D. Suciu. “Storing Semistructured Data with STORED”. In ACM SIGMOD, Philadephia, PA, Jun. 1998. 82, 83
D. Florescu and D. Kossmann. “Storing and Querying XML Data Using an RDBMS”. IEEE Data Eng. Bulletin, 22(3):27–34, Sep. 1999. 82, 83
H. Hosoya and B.C. Pierce. “XDuce: A Typed XML Processing Language”. In Int’l Workshop on the Web and Databases (WebDB), Dallas, TX, May 2000. 81, 83
D. Lee and W.W. Chu. “CPI: Constraints-Preserving Inlining Algorithm for Mapping XML DTD to Relational Schema”. J. Data & Knowledge Engineering (DKE), 39(1):3–25, Oct. 2001. 82, 83, 90
D. Lee, M. Mani, F. Chiu, and W.W. Chu. “Nesting-based Relational-to-XML Schema Translation”. In Int’l Workshop on the Web and Databases (WebDB), Santa Barbara, CA, May 2001. 82
D. Lee, M. Mani, F. Chiu, and W.W. Chu. “NeT & CoT: Translating Relational Schemas to XML Schemas using Semantic Constraints”. Technical report, UCLA Computer Science Dept., Feb. 2002. 82, 89, 102
M. Mani, D. Lee, and R.D. Muntz. “Semantic Data Modeling using XML Schemas”. In Int’l Conf. on Conceptual Modeling (ER), Yokohama, Japan, Nov. 2001. 81, 89
M. Murata, D. Lee, and M. Mani. “Taxonomy of XML Schema Languages using Formal Language Theory”. In Extreme Markup Languages, Montreal, Canada, Aug. 2001. http://www.cs.ucla.edu/~dongwon/paper/. 81, 82, 83, 84, 86, 87
J. Shanmugasundaram, K. Tufte, G. He, C. Zhang, D. DeWitt, and J. Naughton. “Relational Databases for Querying XML Documents: Limitations and Opportunities”. In VLDB, Edinburgh, Scotland, Sep. 1999. 82, 83, 98
M. Takahashi. “Generalizations of Regular Sets and Their Applicatin to a Study of Context-Free Languages”. Information and Control, 27(1):1–36, Jan. 1975. 81
H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn (Eds). “XML Schema Part 1: Structures”. W3C Recommendation, May 2001. http://www.w3.org/TR/xmlschema-1/. 81
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mani, M., Lee, D. (2003). XML to Relational Conversion Using Theory of Regular Tree Grammars. In: Bressan, S., Lee, M.L., Chaudhri, A.B., Yu, J.X., Lacroix, Z. (eds) Efficiency and Effectiveness of XML Tools and Techniques and Data Integration over the Web. DIWeb EEXTT 2002 2002. Lecture Notes in Computer Science, vol 2590. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36556-7_6
Download citation
DOI: https://doi.org/10.1007/3-540-36556-7_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00736-4
Online ISBN: 978-3-540-36556-3
eBook Packages: Springer Book Archive