Rada CHIRKOVA1, Leonid LIBKIN2, Juan L. REUTTER2()
1. Department of Computer Science, North Carolina State University, Raleigh NC 27606, USA; 2. School of Informatics, University of Edinburgh, Edinburgh EH8 9AB, UK
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.
Corresponding Author(s):
REUTTER Juan L.,Email:juan.reutter@ed.ac.uk
引用本文:
. Tractable XML data exchange via relations[J]. Frontiers of Computer Science, 2012, 6(3): 243-263.
Rada CHIRKOVA, Leonid LIBKIN, Juan L. REUTTER. Tractable XML data exchange via relations. Front Comput Sci, 2012, 6(3): 243-263.
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 doi: 10.1145/1247480.1247482
3
Barceló P. Logical foundations of relational data exchange. ACM SIGMOD Record , 2009, 38(1): 49-58 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 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 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 doi: 10.1145/1007568.1007611
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 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 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 doi: 10.1007/978-3-540-39429-7_1
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 doi: 10.1145/375663.375722
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 doi: 10.1145/564691.564715
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 doi: 10.1007/978-3-642-18690-5_1
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 doi: 10.1016/B978-155860869-6/50059-7
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 doi: 10.1145/1807085.1807112
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 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 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 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 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
29
Abiteboul S, Segoufin L, Vianu V. Representing and querying XML with incomplete information. ACMTransactions on Database Systems , 2006, 31(1): 208-254 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 doi: 10.1145/1559845.1559914
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 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 doi: 10.1145/1131342.1131345
