Tractable XML data exchange via relations

Abstract

We consider data exchange for XML documents: given source and target schemas, a mapping between them, and a document conforming to the source schema, construct a target document and answer target queries in a way that is consistent with the source information. The problem has primarily been studied in the relational context, in which dataexchange systems have also been built.

Since many XML documents are stored in relations, it is natural to consider using a relational system for XML data exchange. However, there is a complexity mismatch between query answering in relational and in XML data exchange. This indicates that to make the use of relational systems possible, restrictions have to be imposed on XML schemas and mappings, as well as on XML shredding schemes.

We isolate a set of five requirements that must be fulfilled in order to have a faithful representation of the XML data-exchange problem by a relational translation. We then demonstrate that these requirements naturally suggest the inlining technique for data-exchange tasks. Our key contribution is to provide shredding algorithms for schemas, documents, mappings and queries, and demonstrate that they enable us to correctly perform XML data-exchange tasks using a relational system.

Keywords

data exchange / XML / XML shredding / inlining

References

[1] Kolaitis P. Schema mappings, data exchange, and metadata management. In: Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems. 2005, 61-75

[2] Bernstein P, Melnik S. Model management 2.0: manipulating richer mappings. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. 2007, 1-12

[3] Barceló P. Logical foundations of relational data exchange. ACM SIGMOD Record, 2009, 38(1): 49-58

[4] Fagin R, Kolaitis P, Miller R, Popa L. Data exchange: semantics and query answering. Theoretical Computer Science, 2005, 336(1): 89-124

[5] Fagin R, Kolaitis P, Popa L. Data exchange: getting to the core. ACM Transactions on Database Systems (TODS), 2005, 30(1): 174-210

[6] Yu C, Popa L. Constraint-based XML query rewriting for data integration. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 2004, 371- 382

[7] Hernández M, Ho H, Popa L, Fukuda T, Fuxman A, Miller R, Papotti P. Creating nested mappings with clio. In: Proceedings of the IEEE 23rd International Conference on Data Engineering ICDE ’07, . 2007, 1487-1488

[8] Arenas M, Libkin L. XML data exchange: consistency and query answering. Journal of the ACM, 2008, 55(2): 1-72

[9] Amano S, Libkin L, Murlak F. XML schema mappings. In: Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2009, 33-42

[10] Amano S, David C, Libkin L, Murlak F. On the tradeoff between mapping and querying power in XML data exchange. In: Proceedings of the 13th International Conference on Database Theory. 2010, 155-164

[11] Jagadish H V, Al-Khalifa S, Chapman A, Lakshmanan L V S, Nierman A, Paparizos S, Patel J M, Srivastava D, Wiwatwattana N, Wu Y, Yu C. Timber: A native XML database. The VLDB Journal, 2002, 11(4): 274-291

[12] Krishnamurthy R, Kaushik R, Naughton J. XML-to-SQL query translation literature: The state of the art and open problems. In: Bellahsène Z, Chaudhri A, Rahm E, Rys M, Unland R, eds. Database and XML Technologies. Berlin: Springer, 2003, 1-18

[13] Florescu D, Kossmann D. Storing and querying XML data using an RDMBS. IEEE Data Engineering Bulletin, 1999, 22(3): 27-34

[14] Zhang C, Naughton J, DeWitt D, Luo Q, Lohman G. On supporting containment queries in relational database management systems. In: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data. 2001, 425-436

[15] Tatarinov I, Viglas S, Beyer K, Shanmugasundaram J, Shekita E, Zhang C. Storing and querying ordered XML using a relational database system. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. 2002, 204-215

[16] Shanmugasundaram J, Tufte K, Zhang C, He G, Dewitt D, Naughton J. Relational databases for querying XML documents: limitations and opportunities. In: Proceedings of the 25th International Conference on Very Large Data Bases. 1999, 302-314

[17] Klarlundi N, Schwentick T, Suciu D. XML: model, schemas, types, logics, and queries. In: Chomicki J, Meyden R, Saake G, eds. Logics for Emerging Applications of Databases. Berlin: Springer, 2004, 1-40

[18] Fuxman A, Hernandez M, Ho H, Miller R, Papotti P, Popa L. Nested mappings: schema mapping reloaded. In: Proceedings of the 32nd International Conference on Very Large Data Bases. 2006, 67-78

[19] Popa L, Velegrakis Y, Hernández M, Miller R, Fagin R. Translating web data. In: Proceedings of the 28th International Conference on Very Large Data Bases. 2002, 598-609

[20] Afrati F, Li C, Pavlaki V. Data exchange in the presence of arithmetic comparisons. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology. 2008, 487-498

[21] Boag S, Chamberlin D, Fernández M, Florescu D, Robie J, Siméon J, Stefanescu M. XQuery 1.0: An XML query language. W3C Working Draft, 2003

[22] David C, Libkin L, Murlak F. Certain answers for XML queries. In: Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems of Data. 2010, 191-202

[23] Shanmugasundaram J, Shekita E, Kiernan J, Krishnamurthy R, Viglas E, Naughton J, Tatarinov I. A general technique for querying XML documents using a relational database system. ACMSIGMOD Record, 2001, 30(3): 20-26

[24] Balmin A, Papakonstantinou Y. Storing and querying XML data using denormalized relational databases. The VLDB Journal, 2005, 14(1): 30-49

[25] Krishnamurthy R, Kaushik R, Naughton J. XML views as integrity constraints and their use in query translation. In: Proceedings of the 21st International Conference on Data Engineering, ICDE ’05. 2005, 693-704

[26] Gou G, Chirkova R. Efficiently querying large XML data repositories: A survey. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(10): 1381-403

[27] Miller R, Hernandez M, Haas L, Yan L, Ho C, Fagin R, Popa L. The Clio project: managing heterogeneity. SIGMOD Record, 2001, 30(1): 78-83

[28] Chirkova R, Libkin L, Reutter J. Tractable XML data exchange via relations. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 2011, 1629-1638

[29] Abiteboul S, Segoufin L, Vianu V. Representing and querying XML with incomplete information. ACMTransactions on Database Systems, 2006, 31(1): 208-254

[30] Mecca G, Papotti P, Raunich S. Core schema mappings. In: Proceedings of the 35th SIGMOD International Conference on Management of Data. 2009, 655-668

[31] Bjöklund H, Martens W, Schwentick T. Conjunctive query containment over trees. In: Database Programming Languages. 2007, 66-80

[32] Amer-Yahia S, Cho S, Lakshmanan L V S, Srivastava D. Tree pattern query minimization. The VLDB Journal, 2002, 11(4): 315-331

[33] Lakshmanan L, Ramesh G, Wang H, Zhao Z. On testing satisfiability of tree pattern queries. In: Proceedings of the 30th International Conference on Very Large Data Bases. 2004, 120-131

[34] Gottlob G, Koch C, Schulz K. Conjunctive queries over trees. Journal of the ACM, 2006, 53(2): 238-272

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg