sigmod2003

Composing XSL Transformations with XML Publishing Views: 

Composing XSL Transformations with XML Publishing Views Chengkai Li University of Illinois at Urbana-Champaign Philip Bohannon Lucent Technologies, Bell Labs Henry F. Korth Lehigh University PPS Narayan Lucent Technologies, Bell Labs SIGMOD 2003

Motivation: 

Motivation XML: popular for data representation and exchange The data: stored in RDBMS Vast majority of existing data stored in RDBMS Efficiency, robustness of RDBMS for XML applications XML Publishing Views (SilkRoute, XPERANTO) The query: expressed as XSLT Designed for document transformation Popular as XML query language How to evaluate queries on relational data posed in XSLT?

XML Publishing: 

XML Publishing SQL queryes Relational DB Query Logic Tagger XML data Publisher view query: specifies the mapping between relational tables and resulting XML document. view query

Example: tables and schema of view: 

Example: tables and schema of view HOTEL METROAREA ROOM / metro (name) hotel (name, star) room (#) total_room available

Example: published XML document: 

Example: published XML document / metro (“Chicago”) metro (“New York City”) room (2) total_room available room (1) 2 hotel (“Hilton”, 4) room (102) total_room room (101) 2 hotel (“Hyatt”, 2)

Example of View Query: 

Example of View Query Relational Schema Metroarea(metroid, metroname) Hotel(hotelid, hotelname, starrating, metro_id) Room(hotel_id, room#, available) Desired Hierarchical Structure of Published XML <metro> <hotel> <total_room> <available> <room> /

Evaluate XSLT queries on relational data?: 

Evaluate XSLT queries on relational data? XSLT stylesheet view query view

Approach 1: Materialization: 

Approach 1: Materialization 1 XML data XSLT stylesheet view query materialized view

Unnecessary Materializations: 

Unnecessary Materializations rule 1. metro [@name=“Chicago”] : output name rule 2. hotel [@star>3]: no output rule 3. total_room : output total number of rooms nodes that do not satisfy type requirement nodes that do not satisfy selection condition nodes not involved in output / metro (“Chicago”) metro (“New York City”) room (2) total_room available room (1) 2 hotel (“Hilton”, 4)

Approach 2: View Composition: 

Approach 2: View Composition + new view query 1 2 XML data XSLT stylesheet view query XSLT stylesheet view query XML data materialized view

Algorithm Overview: 

Algorithm Overview nodes that do not satisfy type requirements: What type of nodes are accessed? nodes that do not satisfy selection condition: What are the instances of these types of nodes? nodes not involved in output: How do we avoid materializing uninvolved nodes? / metro (“Chicago”) metro (“New York City”) room (2) total_room available room (1) 2 hotel (“Hilton”, 4)

Algorithm Overview: 

Algorithm Overview view query XSLT stylesheet new view query + Context Transition Graph (CTG) Traverse View Query (TVQ) Output Tag Tree (OTT) What type of nodes are accessed? What are the instances of these types of nodes? How do we avoid materializing nodes uninvolved in output?

Example of XSLT Stylesheet: 

Example of XSLT Stylesheet R1: <xsl:template match=“/”> <result_metro> <A/> <xsl:apply-templates select=“metro/hotel/total_room”/> </result_metro> </xsl:template> R2: <xsl:template match=“total_room”> <result_total> <B/> <xsl:apply-templates select=“../available/../room”/> </result_total> </xsl:template> R3: <xsl:template match=“metro/hotel/room”> <xsl:value-of select=“.”/> </xsl:template>

Template Rule: 

Template Rule <xsl:template match=“/”> <result_metro> <A/> <xsl:apply-templates select=“metro/hotel/total_room”/> </result_metro> </xsl:template> A stylesheet consists of a set of template rules. R = < match_pattern(r), output(r), select_expression(r) > match the root generate output process total_room for all hotels of all metro areas

Simplified Representation: 

Simplified Representation R1: match=“/” select=“metro/hotel/total_room” R2: match=“total_room” select=“../available/../room” R3: match=“metro/hotel/room”

XSLT processing: 

XSLT processing R1: match=“/” select=“metro/hotel/total_room” R2: match=“total_room” select=“../available/../room” R3: match=“metro/hotel/room” <metro> / <metro> <hotel> <hotel> <room> <total_room> <room> <available> (/, R1) (total_room,R2) (room,R3)

Context Transition Graph (CTG): 

Context Transition Graph (CTG) (/, R1) (total_room,R2) (room,R3) Document instances of <total_room> may be matched by R2, which further selects document instances of <room>, which may be matched by R3. MATCHQ: nodes SELECTQ: edges CTG: Which type of nodes are accessed? total_room: context node room: new context node

Instances of accessed nodes?: 

Instances of accessed nodes? (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=?

Traverse View Query (TVQ): 

Traverse View Query (TVQ) (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new =SELECT * FROM room WHERE hotel_id=$t_new.hotelid AND EXISTS (SELECT * FROM room WHERE hotel_id=$t_new.hotelid AND available = TRUE) TVQ: Instances of accessed nodes

TVQ: Instances of accessed nodes: 

TVQ: Instances of accessed nodes R2: match=“total_room” select=“../available/../room” R3:match=“metro/hotel/room” (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=?

Select-Match Tree: How does context transition happen?: 

Select-Match Tree: How does context transition happen? <hotel> <total_room> <room> <available> <metro> Select-Match Tree (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=?

UNBIND: Select-Match Tree  tag query: 

UNBIND: Select-Match Tree  tag query <hotel> <total_room> <room> <available> <metro> Select-Match Tree (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=?

UNBIND: Select-Match Tree  tag query: 

UNBIND: Select-Match Tree  tag query <hotel> <total_room> <available> <metro> Select-Match Tree (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=? <room> $r =SELECT * FROM room WHERE hotel_id=$h.hotelid

UNBIND: Select-Match Tree  tag query: 

UNBIND: Select-Match Tree  tag query <hotel> <total_room> <available> <metro> Select-Match Tree (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=SELECT * FROM room WHERE hotel_id=$t_new.hotelid <room> $r =SELECT * FROM room WHERE hotel_id=$h.hotelid

UNBIND: Select-Match Tree  tag query: 

UNBIND: Select-Match Tree  tag query <hotel> <total_room> <metro> Select-Match Tree (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new=SELECT * FROM room WHERE hotel_id=$t_new.hotelid <room> <available> $a=SELECT * FROM room WHERE hotel_id=$h.hotelid AND available = TRUE

UNBIND: Select-Match Tree  tag query: 

UNBIND: Select-Match Tree  tag query <hotel> <total_room> <metro> Select-Match Tree (/, R1) (total_room,R2) $t_new= … (room,R3) $r_new =SELECT * FROM room WHERE hotel_id=$t_new.hotelid AND EXISTS (SELECT * FROM room WHERE hotel_id=$t_new.hotelid AND available = TRUE) <room> <available> $a=SELECT * FROM room WHERE hotel_id=$h.hotelid AND available = TRUE

UNBIND: General Cases : 

UNBIND: General Cases General Select-Match Tree with Predicates Unbind along the lowest common ancestor to the new context node (FROM) Nest of all sub-trees not on the two paths (WHERE EXISTS) Attribute access of all nodes (WHERE) lowest common ancestor a=10 b<5 context node new context node

Output Tag Tree: 

Output Tag Tree (root, R1) (total_room,R2) (room,R3)

Output Tag Tree (OTT): 

Output Tag Tree (OTT) R1: <xsl:template match=``/''> <result_metro> <A/> <xsl:apply-templates select=``…''/> </result_metro> </xsl:template> <result_metro> <A> apply-template (root, R1) (total_room,R2) (room,R3)

Output Tag Tree (OTT): 

Output Tag Tree (OTT) R2: <xsl:template match=``total_room''> <result_total> <B/> <xsl:apply-templates select=``...''/> </result_total> </xsl:template> <result_metro> <A> <result_total> <B> apply-template (root, R1) (total_room,R2) (room,R3)

Output Tag Tree (OTT): 

Output Tag Tree (OTT) <result_metro> <A> <result_total> <B> <room> R3: <xsl:template match=``metro/hotel/room''> <xsl:value-of select=''.''/> </xsl:template> (root, R1) (total_room,R2) (room,R3)

New View Query: 

New View Query <result_metro> <A> <result_total> <B> <room> Forced Unbind during the generation of OTT (root, R1) (total_room,R2) (room,R3)

XSLT_basic: 

XSLT_basic no type coercion no document order no “//” no function no variable and parameter no recursion no predicate in expression no flow-control elements (<xsl:if>, <xsl:for-each>,<xsl:choose>) no conflicting rule resolution select of <xsl:value-of> is “.”

Relaxing Assumptions: 

Relaxing Assumptions recursion predicate in expression flow-control elements (<xsl:if>, <xsl:for-each>,<xsl:choose>) conflicting rule resolution select of <xsl:value-of> be other than “.” and “@attribute”

Summary: 

Summary Problem: Composing XSL Transformations with XML publishing views Advantages compared with materialization approach Algorithm Context Transition Graph Traverse View Query Output Tag Tree Relaxing Assumptions

Future Work: 

Future Work //: CTG graph multigraph recursion

Related Work: 

Related Work Translating XSLT into SQL queries: Jain et al, WWW 02 XML publishing middleware SilkRoute: Fernandez et al, WWW 00, SIGMOD 01 XPERANTO: Carey et al, WebDB 00 & Shanmugasundaram et al, VLDB 01 Incorporating XSL processing into database engines: Moerkotte, VLDB 02