×

Tractable XML data exchange via relations. (English) Zbl 1251.68083

Summary: 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 data-exchange 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 in-lining 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.

MSC:

68P05 Data structures
68T30 Knowledge representation

Software:

TIMBER; XQuery
PDFBibTeX XMLCite
Full Text: DOI Link

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 · Zbl 05746793 · doi:10.1145/1558334.1558341
[4] Fagin R, Kolaitis P, Miller R, Popa L. Data exchange: semantics and query answering. Theoretical Computer Science, 2005, 336(1): 89–124 · Zbl 1080.68019 · doi:10.1016/j.tcs.2004.10.033
[5] Fagin R, Kolaitis P, Popa L. Data exchange: getting to the core. ACM Transactions on Database Systems (TODS), 2005, 30(1): 174–210 · Zbl 1326.68119 · doi:10.1145/1061318.1061323
[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 · Zbl 1326.68116 · doi:10.1145/1346330.1346332
[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 · Zbl 1047.68575 · doi:10.1007/s00778-002-0081-x
[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. W 3C 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 · Zbl 05444532 · doi:10.1145/603867.603871
[24] Balmin A, Papakonstantinou Y. Storing and querying XML data using denormalized relational databases. The VLDB Journal, 2005, 14(1): 30–49 · Zbl 02224595 · doi:10.1007/s00778-003-0113-1
[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 · Zbl 05340385 · doi:10.1109/TKDE.2007.1060
[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 · Zbl 05444516 · doi:10.1145/373626.373713
[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 · Zbl 1251.68083
[29] Abiteboul S, Segoufin L, Vianu V. Representing and querying XML with incomplete information. ACMTransactions on Database Systems, 2006, 31(1): 208–254 · Zbl 05456994 · doi:10.1145/1132863.1132869
[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 · Zbl 1047.68040 · doi:10.1007/s00778-002-0076-7
[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 · Zbl 1326.68110 · doi:10.1145/1131342.1131345
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.