XML Relational Mapping CPS 116 Introduction to Database Systems Announcements November 1 Homework 2 3 due next Tuesday Yi will conduct a help session next Monday Time location will be announced by this weekend Project milestone 2 due in one week Approaches to XML processing 3 Text files Specialized XML DBMS Lore Stanford Strudel AT T Timber Michigan MonetDB XQuery CWI Netherlands Tamino Software AG eXist Sedna Apache XIndice XML DB API initiative Still a long way to go Object oriented DBMS ObjectStore ozone Not as mature as relational DBMS Relational and object relational DBMS Middleware and or object relational extensions 1 4 Mapping XML to relational Store XML in a CLOB Character Large OBject column Simple compact Full text indexing can help often provided by DBMS vendors as object relational extensions Poor integration with relational query processing Updates U d are expensive i Alternatives Schema oblivious mapping well formed XML generic relational schema Node edge based mapping for graphs Interval based mapping for trees Path based mapping for trees Schema aware mapping valid XML special relational schema based on DTD 5 Node edge based schema Element eid tag Attribute eid attrName attrValue Key eid attrName Attribute order does not matter ElementChild eid pos child Keys eid pos child pos specifies ifi the h ordering d i off children hild child references either Element eid or Text tid Text tid value tid cannot be the same as any eid Need to invent lots of id s Need indexes for efficiency e g Element tag Text value Node edge based example bibliography book ISBN ISBN 10 price 80 00 title Foundations of Databases title author Abiteboul author author Hull author author Vianu author publisher Addison Wesley publisher year 1995 year book bibliography Attribute Text Element 6 ElementChild eid tag eid pos child e0 bibliography e0 1 e1 e1 book e1 1 e2 e2 title e1 2 e3 e3 author e1 3 e4 e4 author e1 4 e5 eid attrName attrValue e5 author e1 5 e6 e1 ISBN ISBN 10 e6 publisher e1 6 e7 e1 price 80 e7 year e2 1 t0 e3 1 t1 e4 1 t2 e5 1 t3 e6 1 t4 e7 1 t5 tid value t0 Foundations of Databases t1 Abiteboul t2 Hull t3 Vianu t4 Addison Wesley t5 1995 2 Node edge based simple paths 7 title SELECT eid FROM Element WHERE tag title section title SELECT e2 eid FROM Element e1 ElementChild c Element e2 WHERE e1 tag section AND e2 tag title AND e1 eid c eid AND c child e2 eid Path expression becomes joins Number of joins is proportional to the length of the path expression Node edge based more complex paths 8 bibliography book author Abiteboul price SELECT a attrValue FROM Element e1 ElementChild c1 Element e2 Attribute a WHERE e1 tag bibliography AND e1 eid c1 eid AND c1 child e2 eid AND e2 tag e2 tag book book AND EXISTS SELECT FROM ElementChild c2 Element e3 ElementChild c3 Text t WHERE e2 eid c2 eid AND c2 child e3 eid AND e3 tag author AND e2 eid c3 eid AND c3 child t tid AND t value Abiteboul AND e2 eid a eid AND a attrName price Node edge based descendent or self 9 book title Requires SQL3 recursion WITH ReachableFromBook id AS SELECT eid FROM Element WHERE tag book UNION ALL SELECT c child FROM ReachableFromBook r ElementChild c WHERE r eid c eid SELECT eid FROM Element WHERE eid IN SELECT FROM ReachableFromBook AND tag title 3 10 Interval based schema Element left right level tag left is the start position of the element right is the end position of the element level is the nesting depth of the element strictly speaking unnecessary Key is Text left right level value Key is Attribute left attrName attrValue Key is 11 Interval based example 1 bibliography 2 book ISBN ISBN 10 price 80 00 3 title 4Foundations of Databases title 5 6 author 7Abiteboul author 8 9 author 10Hull author 11 12 author 13Vianu author 14 15 publisher 16Addison Wesley publisher 17 18 year 191995 year 20 book 21 bibliography 999 bibliography book 1 999 1 2 21 2 title author author author publisher year 3 5 3 6 8 3 9 11 3 12 14 3 15 17 3 18 20 3 Where did ElementChild go E1 is the parent of E2 iff Interval based queries 12 section title SELECT e2 left FROM Element e1 Element e2 WHERE e1 tag section AND e2 tag title AND e1 left e2 left AND e2 right e1 right AND e1 level e2 level 1 Path expression becomes containment joins book title 4 Summary of interval based mapping 13 Path expression steps become containment joins No recursion needed for descendent or self Comprehensive XQuery SQL translation is possible A path based mapping 14 Label path encoding Element pathid left right Path pathid path path is a label path starting from the root Why are left and right still needed Path Element pathid left right pathid path 1 1 999 1 bibliography 2 2 21 2 bibliography book 3 3 5 3 bibliography book title 4 6 8 4 bibliography book author 4 9 11 4 12 14 Label path encoding queries 15 Simple path expressions with no conditions book title Perform string matching on Path Join qualified pathid s with Element book publisher Prentice book publisher Prentice Hall title Hall title 5 Another path based mapping 16 Dewey order encoding Each component of the id represents the order of the child within its parent Unlike label path this encoding is lossless bibliography book 1 1 1 title author author author publisher year Element dewey pid tag 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 Text dewey pid value Attribute dewey pid attrName attrValue Dewey order encoding queries 17 Examples title section title book title b k bli h P ti book publisher Prentice Hall title H ll titl Serves a different purpose from label path encoding Any advantage over interval based mapping Schema aware mapping 18 Idea use DTD to design a better schema Basic approach elements of the same type go into one table Tag name table name Attributes columns If one exists exists ID attribute key column otherwise otherwise need to invent invent a key IDREF attribute foreign key column Children of the element foreign key columns Ordering of columns encodes ordering of children DOCTYPE bibliography ELEMENT book title ATTLIST book ISBN ID REQUIRED ATTLIST book price CDATA IMPLIED ELEMENT title PCDATA book ISBN price title id title id PCDATA id PCDATA id value 6 Handling and in DTD 19 What if an element can have any number of children Example Book can have multiple authors book ISBN price title id author id publisher id year id Id create Idea t another th ttable bl tto ttrackk suchh relationships l ti hi book ISBN price title id publisher id year id book author ISBN author id BCNF decomposition in
View Full Document
Unlocking...