Abstract
We propose a mapping from a database conceptual design to a schema for XML that produces highly connected and nested XML structures. We first introduce two alternative definitions of the mapping, one modeling entities as global XML elements and expressing relationships among them in terms of keys and key references (flat design), the other one encoding relationships by properly including the elements for some entities into the elements for other entities (nest design). Then we provide a benchmark evaluation of the two solutions showing that the nest approach, compared to the flat one, leads to improvements in both query and validation performances. This motivates us to systematically investigate the best way to nest XML structures. We identify two different nesting solutions: a maximum depth nesting, that keeps low the number of costly join operations that are necessary to reconstruct information at query time using the mapped schema, and a maximum density nesting, that minimizes the number of schema constraints used in the mapping of the conceptual schema, thus reducing the validation overhead. On the one hand, the problem of finding a maximum depth nesting turns out to be NP-complete and, moreover, it admits no constant ratio approximation algorithm. On the other hand, we devise a graph-theoretic algorithm, NiduX, that solves the maximum density problem in linear time. Interestingly, NiduX finds the optimal solution for the harder maximum depth problem whenever the conceptual design graph is either acyclic or complete. In randomly generated intermediate cases of the graph topology, we experimentally show that NiduX finds a good approximation of the optimal solution.
- Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.Google ScholarCross Ref
- Barabási, A.-L., Albert, R., and Jeong, H. 1999. Mean-field theory for scale-free random networks. Physica A 272, 1--2, 173--187.Google ScholarCross Ref
- Bazgan, C., Santha, M., and Tuza, Z. 1999. On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs. J. Algor. 31, 1, 249--268. Google ScholarDigital Library
- Bird, B., Goodchild, A., and Halpin, T. 2000. Object role modelling and XML-Schema. In Proceedings of the 19th International Conference on Conceptual Modeling. Springer, 309--322. Google ScholarDigital Library
- Boncz, P., Grust, T., van Keulen, M., Manegold, S., Rittinger, J., and Teubner, J. 2011. MonetDB/XQuery. MonetDB database system with XQuery front-end. http://monetdb.cwi.nl/XQuery/index.html.Google Scholar
- Cayley, A. 1889. A theorem on trees. Q. J. Math. 23, 376--378.Google Scholar
- Combi, C. and Oliboni, B. 2002. Conceptual modeling of XML data. In Proceedings of the 17th Symposium on Applied Computing. ACM, 467--473. Google ScholarDigital Library
- Conrad, R., Scheffner, D., and Freytag, J. 2000. XML conceptual modeling using UML. In Proceedings of the 19th International Conference on Conceptual Modeling. Springer, 558--571. Google ScholarDigital Library
- DBIS Research Group. 2011. BaseX: Processing and visualizing XML with a native XML database. http://www.inf.uni-konstanz.de/dbis/basex/.Google Scholar
- Dobbie, G., Xiaoying, W., Ling, T., and Lee, M. 2001. Designing semistructured databases using ORASS model. In Proceedings of the 2nd International Conference on Web Information Systems Engineering. IEEE Computer Society, 171--180. Google ScholarDigital Library
- Dovier, A., Piazza, C., and Policriti, A. 2004. An efficient algorithm for computing bisimulation equivalence. Theor. Comput. Sci. 311, 1--3, 221--256. Google ScholarDigital Library
- Duta, A., Barker, K., and Alhajj, R. 2004. Converting relationships to XML nested structures. J. Inf. Org. Sci. 28, 1--2, 15--29.Google Scholar
- Elmasri, R. and Navathe, S. 2010. Fundamentals of Database Systems. 6th edn. Addison-Wesley. Google ScholarDigital Library
- Fong, J. and Cheung, S. 2005. Translating relational schema into XML schema definition with data semantic preservation and XSD graph. Inf. Softw. Tech. 47, 7, 437--462. Google ScholarDigital Library
- Fong, J., Cheung, S., and Shiu, H. 2008. The XML tree model - toward an XML conceptula schema reversed from XML Schema Definition. Data Knowl. Engin. 64, 624--661. Google ScholarDigital Library
- Fong, J., Fong, A., Wong, H., and Yu, P. 2006. Translating relational schema with constraints into XML schema. Int. J. Softw. Engin. Knowl. Engin. 16, 2, 201--244.Google ScholarCross Ref
- Franceschet, M. and de Rijke, M. 2006. Model checking for hybrid logics (with an application to semistructured data). J. Appl. Logic 4, 3, 279--304.Google ScholarCross Ref
- Franceschet, M., Gubiani, D., Montanari, A., and Piazza, C. 2012. From entity relationship to XML Schema: a graph-theoretic approach. Tech. rep. UDMI/01/12/RR, University of Udine.Google Scholar
- Galbiati, G., Morzenti, A., and Maffioli, F. 1997. On the approximability of some maximum spanning tree problems. Theor. Comp. Sci. 181, 107--118. Google ScholarDigital Library
- Gubiani, D. and Montanari, A. 2007. A tool for the visual synthesis and the logical translation of spatiotemporal conceptual schemas. In Proceedings of the 15th Italian Symposium on Advanced Database Systems. 495--498.Google Scholar
- Kappel, G., Kapsammer, E., and Retschitzegger, W. 2004. Integrating XML and relational database systems. World Wide Web 7, 4, 343--384. Google ScholarDigital Library
- Karger, D., Motwani, R., and Ramkumar, G. 1997. On approximating the longest path in a graph. Algorithmica 18, 1, 82--98.Google ScholarDigital Library
- Kay, M. 2011. Saxon. The XSLT and XQuery processor. http://saxon.sourceforge.net.Google Scholar
- Kirchhoff, G. 1847. Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird. Annalen für der Physik und der Chemie 72, 497--508.Google ScholarCross Ref
- Kleiner, C. and Lipeck, U. 2001. Automatic generation of XML DTDs from conceptual database schemas. GI Jahrestagung 1, 396--405.Google Scholar
- Krishnan, R. and Raghavachari, B. 2001. The directed minimum-degree spanning tree problem. In Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, 232--243. Google ScholarDigital Library
- Lee, D., Mani, M., Chiu, F., and Chu, W. W. 2002. NeT & CoT: translating relational schemas to XML schemas using semantic constraints. In Proceedings of the 11th International Conference on Information and Knowledge Management. ACM, 282--291. Google ScholarDigital Library
- Link, S. and Trinh, T. 2007. Know your limits: Enhanced XML modeling with cardinality constraints. In Proceedings of the 26th International Conference on Conceptual Modeling. Springer, 19--30. Google ScholarDigital Library
- Liu, C. and Li, J. 2006. Designing quality XML schemas from E-R diagrams. In Proceedings of the 7th International Conference on Advances in Web-Age Information Management. Springer, 508--519. Google ScholarDigital Library
- Liu, C., Vincent, M., and Liu, J. 2006. Constraint preserving transformation from relational schema to XML Schema. World Wide Web 9, 1, 93--110. Google ScholarDigital Library
- Lv, T. and Yan, P. 2006. Mapping relational schemas to XML DTDs with constraints. In Proceedings of the 1st International Multi-Symposiums of Computer and Computational Sciences. IEEE Computer Society, 528--533. Google ScholarDigital Library
- Necasky, M. 2007. XSEM: A conceptual model for XML. In Proceedings of the 4th Asia-Pacific Conference on Conceptual Modelling. Australian Computer Society, 37--48. Google ScholarDigital Library
- Papadimitriou, C. 1995. Computational Complexity. Addison Wesley Longman.Google Scholar
- Pigozzo, P. and Quintarelli, E. 2005. An algorithm for generating XML schemas from ER schemas. In Proceedings of the 15th Italian Symposium on Advanced Database Systems. 192--199.Google Scholar
- Psaila, G. 2000. ERX: A conceptual model for XML documents. In Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography. Springer, 898--903. Google ScholarDigital Library
- Schmidt, A., Waas, F., Kersten, M., Carey, M., Manolescu, I., and Busse, R. 2002. XMark: A benchmark for XML data management. In Proceedings of the 28th International Conference on Very Large Data Bases. ACM, 974--985. Google ScholarDigital Library
- Schroeder, R. and dos Santos Mello, R. 2008. Conversion of generalization hierarchies and union types from extended Entity-Relationship model to an XML logical model. In Proceedings of the 23rd Symposium on Applied Computing. ACM, 1036--1037. Google ScholarDigital Library
- Schroeder, R. and dos Santos Mello, R. 2009. Designing XML documents from conceptual schemas and workload information. Multimedia Tools Appl. 43, 3, 303--326. Google ScholarDigital Library
- Shanmugasundaram, J., Shekita, E. J., Barr, R., Carey, M. J., Lindsay, B. G., Pirahesh, H., and Reinwald, B. 2001. Efficiently publishing relational data as XML documents. VLDB J. 10, 2--3, 133--154. Google ScholarDigital Library
- Yao, G., Zhu, D., Li, H., and Ma, S. 2008. A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem. Discrete Math. 308, 17, 3951--3959.Google ScholarDigital Library
- Zhou, R., Liu, C., and Li, J. 2008. Holistic constraint-preserving transformation from relational schema into XML Schema. In Proceedings of the 13th International Conference on Database Systems for Advanced Applications. Springer, 4--18. Google ScholarDigital Library
Index Terms
- A graph-theoretic approach to map conceptual designs to XML schemas
Recommendations
Conceptual modeling of XML schemas
WIDM '03: Proceedings of the 5th ACM international workshop on Web information and data managementXML has become the standard format for representing structured and semi-structured data on the Web. To describe the structure and content of XML data, several XML schema languages have been proposed. Although being very useful for validating XML ...
Using schematron as schema language in conceptual modeling for XML
APCCM '13: Proceedings of the Ninth Asia-Pacific Conference on Conceptual Modelling - Volume 143Today, XML is a standard for message exchange inside and among IT infrastructures. For the exchange to work an XML format must be negotiated between the communicating parties. The format is often expressed as an XML schema. In our previous work, we ...
Conceptual modeling of XML data
SAC '06: Proceedings of the 2006 ACM symposium on Applied computingIn this paper, we propose a conceptual model for building schemata for XML documents. In particular, we define the conceptual model UXS (UML & XML Schema), which is based on UML and provides several graphical constructs to help the programmer to define ...
Comments