XML Tutorials

  Home arrow XML Tutorials arrow Solving Problems by Querying XML
XML TUTORIALS

Solving Problems by Querying XML
By: O'Reilly Media
  • Search For More Articles!
  • Disclaimer
  • Author Terms
  • Rating: 5 stars5 stars5 stars5 stars5 stars / 1
    2008-01-31

    Table of Contents:
  • Solving Problems by Querying XML
  • 9.4 Performing Structure-Preserving Queries
  • 9.5 Joins
  • Joins With Many Members

  •  
     

    SEARCH CODEWALKERS

    Solving Problems by Querying XML


    (Page 1 of 4 )

    In this third part of a five-part series on using XSLT as an XML query language, you will learn how to determine set equity by value, relate elements in a document to other elements in the same or different document, and more. This article is excerpted from chapter nine of the XSLT Cookbook, Second Edition, written by Sal Mangano (O'Reilly; ISBN: 0596009747). Copyright © 2007 O'Reilly Media, Inc. All rights reserved. Used with permission from the publisher. Available from booksellers or direct from O'Reilly Media.

    9.3 Determining Set Equality by Value

    Problem

    You need to determine if the nodes in one node set are equal (by value) to the nodes in another node set (ignoring order).

    Solution

    This problem is slightly more subtle than it appears on the surface. Consider an obvious solution that works in many cases:

      <xsl:template name="vset:equal-text-values">
        <xsl:param name="nodes1" select="/.."/>
        <xsl:param name="nodes2" select="/.."/>
        <xsl:choose>
         <!--Empty node-sets have equal values
    -->
         
    <xsl:when test="not($nodes1) and not($nodes2)">
            <xsl:value-of select="true()"/>
            </xsl:when>
          <!--Node sets of unequal sizes cannot have equal values -->
          <xsl:when test="count($nodes1) != count($nodes2)"/>
          <!--If an element of nodes1 is present in nodes2 then the node sets
          
    have equal values if the node sets without the common element have equal
           values -->
          <xsl:when test="$nodes1[1] = $nodes2">
           
    <xsl:call-template name="vset:equal-text-values">
                <xsl:with-param name="nodes1" select="$nodes1[position()>1]"/>
                <xsl:with-param name="nodes2"
                               
    select="$nodes2[not(. = $nodes1[1])]"/>
           
    </xsl:call-template>
          </xsl:when>
          <xsl:otherwise/>
        </xsl:choose>
      </xsl:template>

    We have chosen a name for this equality test to emphasize the context in which it should be applied. That is when value equality indicate string-value equality. Clearly, this template will not give the correct result if equality is based on attributes or criteria that are more complex. However, this template has a more subtle problem. It tacitly assumes that the compared node sets are proper sets (i.e., they contain no duplicates) under string-value equality. In some circumstances, this may not be the case. Consider the following XML representing the individuals who borrowed books from a library:

      <?xml version="1.0" encoding="UTF-8"?>
      <library>
       
    <book>
          <name>High performance Java programming.</name>
          <borrowers>
            <borrower>James Straub</borower>
          </borrowers>
        </book>
        <book>
         
    <name>Exceptional C++</name>
          <borrowers>
            <borrower>Steven Levitt
    </borower>
          </borrowers>
        </book>
        <book> 
          
    <name>Design Patterns</name>
         
    <borrowers>
            <borrower>Steven Levitt</borower>
            <borrower>James Straub</borower>
            <borrower>Steven Levitt</borower>
          </borrowers>
        </book>
        <book>
         
    <name>The C++ Programming Language</name>
         
    <borrowers>
            <borrower>James Straub</borower>
            <borrower>James Straub</borower>
            <borrower>Steven Levitt</borower>

          </borrowers>
        </book>
      </library>

    If an individualís name appears more than once, it simply means he borrowed the book more than once. Now, if you wrote a query to determine all books borrowed by the same people, most would agree that Design Patterns and The C++ Programming Language qualify as two such books. However, if you usedvset:equal-text-valuesin the implementation of that query, you would not get this result because it assumes that sets do not contain duplicates. You can altervset:equal-text-valuesto tolerate duplicates with the following changes:

      <xsl:template name="vset:equal-text-values-ignore-dups">
        <xsl:param name="nodes1" select="/.."/>
        <xsl:param name="nodes2" select="/.."/>
        <xsl:choose>
         <!--Empty node-sets have equal values
    -->
         
    <xsl:when test="not($nodes1) and not($nodes2)">
            <xsl:value-of select="true()"/>
            </xsl:when>
         
    <!--If an element of nodes1 is present in nodes2 then the node sets
           have equal values if the node sets without the common element have equal
           values -->
         
    <!--delete this line
              <xsl:when test="count($nodes1) != count($nodes2)"/> -->
          <xsl:when test="$nodes1[1] = $nodes2">
            <xsl:call-template name="vset:equal-text-values"> 
              <xsl:with-param name="nodes1"
                        select="$nodes1[not(. = $nodes1[1])]"/>
             
    <xsl:with-param name="nodes2"
                    
    select="$nodes2[not(. = $nodes1[1])]"/>        </xsl:call-template>
          </xsl:when>
          <xsl:otherwise/>
        </xsl:choose>
      </xsl:template>

    Notice that we have commented out the test for unequal sizes because that test is not valid in the presence of duplicates. For example, one set might have three occurrences of an element with string valuefoo, while the other has a single elementfoo.

    These sets should be equal when duplicates are ignored. You also must do more than remove just the first element on the recursive step; you should remove all elements with the same value as the first element, just as you do for the second set. This will ensure that duplicates are fully accounted for on each recursive pass. These changes make all equality tests based on text value come out correct, but at the cost of doing additional work on sets that are obviously unequal.

    These equality tests are not as general as the value-set operations produced in Recipe 9.2 because they presume that the only notion of equality you care about is text-value equality. You can generalize them by reusing the same technique you used for testing membership based on a test of element equality that can be overridden by an importing stylesheet:

      <xsl:template name="vset:equal">
        <xsl:param name="nodes1" select="/.."/>
        <xsl:param name="nodes2" select="/.."/>
        <xsl:if test="count($nodes1) = count($nodes2)">
         
    <xsl:call-template name="vset:equal-impl">
            <xsl:with-param name="nodes1" select="$nodes1"/>
            <xsl:with-param name="nodes2" select="$nodes2"/>
          </xsl:call-template>
        </xsl:if>
      </xsl:template>

      <!-- Once we know the sets have the same number of elements -->
      <!-- we only need to test that every member of the first set is -->
      <!-- a member of the second -->
      <xsl:template name="vset:equal-impl">
        <xsl:param name="nodes1" select="/.."/>
        <xsl:param name="nodes2" select="/.."/>
        <xsl:choose>
         
    <xsl:when test="not($nodes1)">
           
    <xsl:value-of select="true()"/>
          </xsl:when>
          <xsl:otherwise>
           
    <xsl:variable name="test">
              <xsl:apply-templates select="$nodes2" mode="vset:member-of">
                <xsl:with-param name="elem" select="$nodes1[1]"/>
             
    </xsl:apply-templates>
            </xsl:variable>
            <xsl:if test="string($test)">
              <xsl:call-template name="vset:equal-impl">
                <xsl:with-param name="nodes1" select="$nodes1[position() > 1]"/>
                <xsl:with-param name="nodes2" select="$nodes2"/>
             
    </xsl:call-template>
            </xsl:if>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:template>

    If you want generalized equality that works in the presence of duplicates, then you must apply a more brute-force approach that makes two passes over the sets:

      <xsl:template name="vset:equal-ignore-dups">
        <xsl:param name="nodes1" select="/.."/>
        <xsl:param name="nodes2" select="/.."/>

        <xsl:variable name="mismatch1">
          <xsl:for-each select="$nodes1">
            <xsl:variable name="test-elem">
              <xsl:apply-templates select="$nodes2" mode="vset:member-of">
                <xsl:with-param name="elem" select="."/>
             
    </xsl:apply-templates>
            </xsl:variable>
            <xsl:if test="not(string($test-elem))">
              <xsl:value-of select=" 'false' "/>
            </xsl:if>
          </xsl:for-each>
        </xsl:variable>
        <xsl:if test="not($mismatch1)">
          <xsl:variable name="mismatch2">
            <xsl:for-each select="$nodes2">
              <xsl:variable name="test-elem">
                <xsl:apply-templates select="$nodes1" mode="vset:member-of">
                  <xsl:with-param name="elem" select="."/>
               
    </xsl:apply-templates>
              </xsl:variable>
              <xsl:if test="not(string($test-elem))">
               
    <xsl:value-of select=" 'false' "/>
              </xsl:if>
            </xsl:for-each>
          </xsl:variable>
          <xsl:if test="not($mismatch2)">
            <xsl:value-of select="true()"/>
          </xsl:if>
        </xsl:if>
      </xsl:template>

    This template works by iterating over the first set and looking for elements that are not a member of the second. If no such element is found, the variable$mismatch1will be null. In that case, it must repeat the test in the other direction by iterating over the second set.

    Discussion

    The need to test set equality comes up often in queries. Consider the following tasks:

    1. Find all books having the same authors.
    2. Find all suppliers who stock the same set of parts.
    3. Find all families with same-age children.

    Whenever you encounter a one-to-many relationship and you are interested in elements that have the same set of associated elements, the need to test set equality will arise.

    More XML Tutorials Articles
    More By O'Reilly Media

    blog comments powered by Disqus

    XML TUTORIALS ARTICLES

    - Validation with Document Type Definitions (D...
    - Creating a Well-Formed XML Document
    - Getting to Know XML
    - A Friendly Approach to XML
    - Creating RSS 2.0 Feeds
    - Using Modules in Your RSS Feed
    - RSS 2.0
    - Querying XML: Use Cases
    - Joins and Query Use with XML
    - Solving Problems by Querying XML
    - Performing Set Operations When Querying XML
    - Querying XML
    - Handling Data for Ajax with JSON
    - Handling XML Data for Ajax
    - XML and JSON for Ajax

    Developer Shed Affiliates

     



    © 2003-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap