title DTD <!ELEMENT root(*, *)> <!ELEMENT (title,, *)> <!ELEMENT (title, )> <!ELEMENT ()> <!ELEMENT title(#pcdata)> <!ELEMENT title(#pcdata)> <!ELEMEN

Transcription

1 DEIM Forum 2011 E6-3 XML-RDB / / [email protected], [email protected], [email protected] XML-RDB XML RDB 1:n XML n:1 C-Mapping C-Mapping RDB C-Mapping C-Mapping XML-RDB, An XML-RDB Mapping Method using Functional and Inclusion Dependencies Sosuke OTA, Atsuyuki MORISHIMA, and Toshiyuki AMAGASA Grad. Sch. of Library, Information and Media Studies, Univ. of Tsukuba 1 2 Kasuga, Tsukuba, Ibaraki,Japan Japan Grad. Sch. of Library, Information and Media Studies/Research Center for Knowledge Communities, Univ. of Tsukuba., Univ. of Tsukuba 1 2 Kasuga, Tsukuba, Ibaraki,Japan Japan Grad. Sch. of Sys. and Info. Eng./Center for Computational Sciences, Univ. of Tsukuba Tennohdai, Tsukuba, Japan [email protected], [email protected], [email protected] 1. XML RDB XML RDB [1] [2] [3] RRXS [4] XML Data Model [5] ( XML ) RDB 1:1 1:n Shared-Inlining [1] ( 1, 2) Shared-Inlining.dtd ( 1 ).xml ( 2 ) XML (ID,.title) ( 2 ) ( ID) title ID.title.xml title title 1:1 XML 1:1 XML RDB 1:n 1:n 1:1 1:n XML-RDB C-

2 title DTD <!ELEMENT root(*, *)> <!ELEMENT (title,, *)> <!ELEMENT (title, )> <!ELEMENT ()> <!ELEMENT title(#pcdata)> <!ELEMENT title(#pcdata)> <!ELEMENT (#PCDATA)> * root * title *.xml <root> <> <title>the Sartorialist</title> <>Scott Schuman</> </> <> <title>sherlock Holmes</title> </> <> <title>sherlock Holmes</title> </> </root> ID.title 1 The Sartorialist 2 Sherlock Holmes ID.title 1 Sherlock Holmes 1.dtd( ) DTD ( ) 2 1:n Mapping (Consistency-conscious Mapping) XML () RDB C-Mapping 1:1 1:n n:1 C-Mapping n:1 n:1 XML 1 RDB 1.dtd XML.xml n:1 3 3.xml title title 3.xml title title XML 1 RDB n:1 XML 1:1 1:n title Sherlock Holmes RDB n:1 2 3 C-Mapping XML 4 C-Mapping 5 C-Mapping (Basic-Inlining Shared-Inlining) ( ) C-Mapping 6 2. XML-RDB 1:1 1:n DTD XML Basic-Inlining, Shared-Inlining, Hybrid-Inlining [1].xml <root> <> <title>the Sartorialist</title> <>Scott Schuman</> </> <> <title>sherlock Holmes</title> </> <> <title>sherlock Holmes</title> </> </root> 3 ID.title 1 The Sartorialist 2 Sherlock Holmes ID 1 2 n:1 ID XML XML XML [2] [3] RRXS [4] XML XML ( 3.1 ) C-Mapping n:1 3. XML C-Mapping XML [4] XML XML Functional Dependencies XFD+ XML XML Inclusion Dependencies 3. 1 XML Functional Dependencies XML Functional Dependencies ( XFD) [4] XML RDB RDB A B R(..., A,..., B,...) 2 A B A B

3 仮想的な属性 概要ノードnのlocal-name ノードnへのルートからのパスノードnの開始バイトオフセットノードnの終了バイトオフセットノードnを始点とするエッジ集合ノードnの型ノードnのID ノードnへのルートからのパスのID エッジeの始点エッジeの終点 XMLデータxのID XFDSet XFD+ a b a b XINDSet XIND A B X XML <a> <b></b> </a> Input 5 C-Mapping RDB R Output X XML 4 XFD+ XFD XML XFD XML.xml ( 2 ) title XFD for $x in.xml/root/ (1) $x $x/title/text() (2) (1) in XPath for $x (1) $x (2) 3. 2 XFD+ XFD XML ( ) ( + () ) 4.xml ( 2 ) XFD+ for $x in.xml//* $x/@path() $x/@nodename() XFD+ for $x in.xml/root/ for $e in $x/@edges() $x, $e $e/@childnode() 4 XFD XML 3. 3 XML Inclusion Dependencies XML Inclusion Dependencies ( XIND) XML RDB R[A] = S[B], R(..., A,...) S(..., B,...) B A XML XIND XML XFD+ for $x in.xml/root/ $x $x/title/text() XIND.xml for $y in.xml/root/ $y $y/title/text().xml/root//title/text().xml/root//title/text() <root> <> <title>the Sartorialist</title> <>Scott Schuman</> </> <> <title>sherlock Holmes</title> </> <> <title>sherlock Holmes</title> </> </root> 6 Input C-Mapping Output ID title 1 The Sartorialist 2 Sherlock Holmes ID 1 2.xml <root> < id= 1 > <title></title> ID <>Scott Schuman</> </> < id= 2 > <title></title> </> < id= 1 > <title></title> </> </root> 3 外部キー制約 2 XML.xml ( 2 ) title title XIND.xml/root//title/text() =.xml/root//title/text() XIND [8] 4. C-Mapping XML-RDB C-Mapping (Consistency-conscious Mapping) C- Mapping C-Mapping C-Mapping 4. 1 C-Mapping 5 XML X X XFD+ XF DSet X XIND XINDSet XINDSet XML XF DSet XML X R XML X C-Mapping XML RDB XFD+ RDB XML X XML XFD+

4 id XML XML XML C-Mapping 3 6 C-Mapping XIND n:1 C-Mapping (1) XF DSet XINDSet RS (2) X RS I XML X 4. 2 C-Mapping (1) 1 XF DSet RS 2 XINDSet RS XINDSet RS 1 RS XF DSet XFD+ 1 7 XF DSet XFD+ XFD+ 2.xml XF DSet..xml XF DSet = {xfd 1, xfd 2 } xfd 1 for $x in.xml/root/ $x $x/title/text() xfd 2 for $y in.xml/root/ $y $y/title/text() XF DSet XFD+ xfd xfd 1 title 15 xfd 2 XF DSet (ID, title) (ID, title) + ID ID 1. Procedure Step1 { 2. //input:xfdset 3. //output:rs 4. let XFDSet={xfd1, xfd2,...}; 5. let xfdn={ det1 res1, det2 res2,...}; 6. RS =empty; 7. for each xfdi XFDSet 8. rs=empty; 9. for each det res xfdi 10. if rs==empty 11. rs.union({det(as primarykey)}); 12. end if 13. rs.union({res}); 14. end for 15. RS.union(rs); 16. end for 17. return RS ; 18. } 7 1 ID XML 1 XFD+ ( 4) 2 2 SQL XML RS RS 2 R(K R,..., A,...) S(K S,..., B,...) R[K R ] = S[B] B K R RDBMS SQL (unique key) [7] R[A] = S[B] A SQL XIND e 1 = e 2 XPath XML U[A e1 ] = V [A e2 ] Ae 1 SQL XIND SQL XIND R[A] = S[B] R[K R] = S[K R] K R K R S S K R T = R KR =K S t T (t[a] = t[b]) R K R R K R A S K R B R[K R] = S[K R] R[A] = S[B] 2 (1) S K R (2) S B ( T A )

5 1. Procedure Step2 { 2. //input: RS, XINDSet 3. //output: RS 4. RS=RS 5. let XINDSet={dep 1 ref 1, dep 2 ref 2,...} 6. for each dep i ref i XINDSet { 7. let R[A] = CorrespondingAttr(dep i) in RS 8. let S[B] = CorrespondingAttr(ref i) in RS 9. S.addAttribute(R.primarykey) 10. S.removeAttribute(B) 11. } 12. return RS; 13. } XFD RRXS XIND, XFD+ C-Mapping XFD+ 決定子を構造に関する情報に限定構造写像モデル写像アプローチアプローチ , 8 XIND 9 (1) 10 (2) 3.3 XIND XFD+ XFD+ XPath XPath XML 2 S B S K R S S R S[B] R[A] R R[K R ] S[K R] R[A] S[K R] 6.xml ( R [title] R[A] ) ( S [title] S[B] [ID] S[K R] ) 6 (3, ) (4, ) [title] [ID] [title] URA [6] Universal Instance 9 C-Mapping string, name string = name XIND 5. C-Mapping C-Mapping C-Mapping 9 XFD RRXS XFD ID XML ( ) XFD+ C-Mapping XFD+ XIND n:1 C-Mapping 5. 1 XML DTD DTD XML RDB XML a a ID DTD a 2 ID title XML Basic- Inlining Shared-Inlining, Hybrid-Inlining C-Mapping XFD x {y 1, y 2,..., y n} for $x in P x/x $x $x/p 1/y 1

6 ID.parentID.title. root rootid 1 1 The Sartorialist Scott Schuman backpointer 2 Sherlock Holmes Arthur Conan Doyle root. * root.id root..parentid root..title root..auth or 1 1 The Sartorialist Scott Schuman title 2 1 Sherlock Holmes Arthur Conan Doyle ID.title. 1 Sherlock Holmes Arthur Conan Doyle root. root.id root..parentid root..title root Sherlock Holmes Arthur Conan Doyle 11 root. rootid ID.parentID.parentCODE ID.parentID.title.auth or.id..parentid Scott Schuman Arthur Conan Doyle title title ID.parentID.parentCODE Arthur Conan Doyle ID titleid title titleid title 1 Scott Schuman 1 The Sartorialist 1 Sherlock Holmes 2 Arthur Conan Doyle 2 Sherlock Holmes ID.parentID.parentCODE.title ID.parentID.parentCODE.title 3 Arthur Conan Doyle Sherlock Holmes The Sartorialist Sherlock Holmes 10 Basic-Inlining.xml ( 2 ) 12 Shared-Inlining.xml ( 2 ) $x $x/p 2/y 2... $x $x/p n/y n Basic-Inlining Basic-Inlining DTD XML.dtd ( 1 ) XML.xml ( 2 ) 10 Basic-Inlining Basic-Inlining DTD DTD 1 DTD backpointer Basic-Inlining (1) ID 2 A (a) * (b) backpointer (2) (a) (b) ID B (3) parentid parentid ID ID title (a) (b).. parentid..refrence 10 Basic-Inlining 1 C-Mapping Basic-Inlining ( ) Basic-Inlining A B DTD a G (a) (b) b A XFD a {n n V (G) (P 1(n) P 2(n, a))} P 1 (n) n G (a) (b) a P 2 (n, a) n G 2 B XFD b {n n V (G) (P 3(n) P 2(n, b))} P 3 (n) n G a b Shared-Inlining Shared-Inlining Basic-Inlining DTD XML Shared-Inlining.dtd ( 1 ) XML.xml ( 2 ) 12 Shared-Inlining Shared-Inlining DTD XML (a) (b) * (c) 2 (d) DTD 1 1 DTD (a) root (b),, (c) (d) Shared-Inlining (1) DTD

7 ID.parentID.parentCODE.title.auth or root rootid ID.parentID.parentCODE.boo k.title.. path pathid pathexpression element docid pathd start end text docid pathid start end value 1 1 #/root The Sartorialist 2 #/root#/ Scott Schuman ID.parentID.parentCODE.title. 3 #/root#/#/title Sherlock Holmes Sherlock Holmes Arthur Conan Doyle 4 #/root#/#/ 5 #/root#/ Arthur Conan Doyle Sherlock Holmes 6 #/root#/#/title Arthur Conan Doyle The Sartorialist Scott Schuman Sherlock Holmes Arthur Conan Doyle 7 #/root#/#/ attribute docd pathid start end value 13 Hybrid-Inlining.xml ( 2 ) (a) (d) (2) ID DTD (b),(c),(d) parentid 1 DTD 12 ID title parentid Shared-Inlining 2 C-Mapping Shared-Inlining ( ) Shared-Inlining XML DTD D (a) a XFD a {n n V (D) P 4 (n, a)} P 4 (n, a) n D (a),(b),(c),(d) 2 (b), (c), (d) b XFD b {n n V (D) (P 4 (n, b) P 5 (n))} P 5 (n) n D b Hybrid-Inlining Hybrid-Inlinig Basic-Inlining Shared-Inlining Basic-Inlining Shared-Inlining (c).dtd ( 1 ) XML.xml ( 2 ) 13 Hybrid-Inlining 3 C-Mapping Hybrid-Inlining 3 Shared-Inlining (c) 14.xml ( 2 ) 5. 2 XML XML DTD XML C-Mapping test.xml XML XML ( ) (path) XML.xml ( 2 ) 14 [2] 4 XML (a) path (b) element (c) attribute (d) text (a) path pathid ( XPath ID) pathexpression ( XPath ) (b) element docid (XML ID) start (XML ( ) ) end (XML ) pathid (path pathid) (c) attribute docid (XML ID) pathid (path pathid), start (XML ) end (XML ) value (XML ) (d) text docid (XML ID) start () end ( ) pathid (path pathid) value () 4 C-Mapping [2] ( ) 4 (a) path XFD+

8 Edge source ordinal name flag target 1 1 ref ref ref title string v1 2 2 string v2 5 1 title string v3 5 2 string v4 8 1 title string v5 8 2 string v6 Vstring vid value v1 The Sartorialist v2 Scott Schuman v3 Sherlock Holmes v4 Arthur Conan Doyle v5 Sherlock Holmes v6 Arthur Conan Doyle 15.xml ( 2 ) for $n in test.xml//* test.xml//@* $n/@pathid() $n/@path() (b) element XFD+ for $e in test.xml//* test.xml/@docid(), $e/@pre(), $e/@post() $e/@pathid() (c) attribute XFD+ for $a in test.xml//@* test.xml/@docid(), $a/@pathid(), $a/@pre(), $a/@post() $a (d) text XFD+ for $t in test.xml//text() test.xml/@docid(), $t/@pre(), $t/@post() $t/@pathid(), $t XML XML.xml ( 2 ) 15 [3] XML (a) Edge (b) Vtype (a) Edge source ( ID) ordinal (source ID) name ( ), flag (ordinal ) target (ordinal ID) (b) Vtype vid ( ID) value ( ) Vtype string Vstring int Vint Vtype 5 C-Mapping [3] ( ) (a) Edge XFD+ for $n in test.xml//* for $e in $n/@edges() $n, $e $n/@nodename(), $e/@childnode()/@type(), $e/@childnode()/@nodeid() (b) Vtype XFD+ for $v in test.xml//text()[./@type()=string] test.xml//@* [./@type()=string] $v/@nodeid() $v (b) string Vtype Vtype string 6. XML-RDB C-Mapping C-Mapping (1) XML 1 RDB n:1 (2) XIND (B)(# ) [1] Jayavel Shanmugasundaram, Kristin Tufte, Gang He, Chun Zhang, David De Witt, Jeffrey Naughton: Relational Databases for Querying XML Documents:Limitations and Opportunities. the 25th VLDB Conference: , [2] M. Yoshikawa, T. Amagasa, T. Shimura and S. Uemura: XRel: A path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology(TOIT), 1( 1): , [3] Daniela Florescu, Donald Kossmann: Storing and Querying XML Data using an RDMBS. Bulletin of the Technical Committee on Data Engineering, 22(3): 27-34, [4] Yi Chen, Susan Davidson, Carmem Hara, Yifeng Zheng: RRXS: Redundancy reducing XML storage in relations. the 29th VLDB Conference: , [5] B. Box, The XML Data Model, 1997, [6] Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley [7] ISO/IEC 9075:1999, Information Technology-Database Language-SQL-Part [8] Michael Karlinger, Millist W. Vincent, Michael Schrefl: Inclusion Dependencies in XML: Extending Relational Semantics. In Database and Expert Systems Applications, volume 5690 of Lecture Notes in Computer Science: 23-37, 2009.