Saturday, March 26, 2011

Interval Coalesce with XSLT

I was intrigued by Vadim Tropashko's SQL Design Patterns. I'm not a SQL guy, so like lots of developers, I think of databases as places to put data, from which to retrieve it, and which occasionally need tuning. I don't think of the execution engine as something that virtually can create additional information for me. I've written maybe two pivot queries in my life, for example. Someone who's adept with Mathematica, or Excel for that matter, can do things in a minute that would take a Java developer days, since a SQL rowset is a very impoverished data structure in Java.

Anyway, I saw an immediate use for Tropashko's "interval coalesce" algorithm. The problem is, given a collection of intervals, to coalesce those that overlap, and thus produce a small collection of non-overlapping intervals. Well, "immediate" is misleading; I waited a year to do this. Anyway, I fired up Oracle XE and made up some data. Then I entered the query on p. 37…only to find out that there's a typo in it. Several hours later, I figured out where it was:

SELECT fst.x, lst.y -- Find two endpoints.

FROM intervals fst, intervals lst WHERE fst.x < lst.y

AND NOT EXISTS ( -- There's no interval beginning between these endpoints...

  SELECT * FROM intervals i

  WHERE i.x > fst.x AND i.x < lst.y

  AND NOT EXISTS ( -- ...for which there's no covering interval.

    SELECT * FROM intervals cov 

    WHERE i.x > cov.x AND i.x <= cov.y

  )

) AND NOT EXISTS (

  SELECT * FROM intervals cov

  WHERE cov.x < fst.x AND fst.x <= cov.y

  OR cov.x <= lst.y AND lst.y < cov.y

)


 

You might notice a discrepancy from the query in the book...and I've reported the erratum!

Tropashko goes on to show a more elegant and efficient way to produce this result, but at this point I wanted to get back to my own practical problem, which was to coalesce intervals defined in an XML document. Since the query above involves three self-joins, I could expect n^4 performance if I simply turned Tropashko's SQL into XPath. However, an XML document is inherently ordered (there's no ANSI SQL equivalent to following-sibling::*[1]). If I sorted the intervals according to their left end, i.e. wrote an XSLT to preprocess the input, then I could simply iterate through the intervals one time, gradually coalescing them where possible. The code falls into a pattern familiar to functional programmers. In other words, I apply a template to the first interval in the document, and that template calls a second template that uses "accumulators" for the current coalesced interval. This pattern is also used in Jeni Tennison's (http://www.jenitennison.com/xslt/index.html) <span style="font-style: italic;">XSLT on the Edge</span> as a way of grouping adjacent elements. I wanted to avoid XPath stunts like Tropashko's SQL, because I will have to apply this transform to documents with 10s of 1000s of data points. I very deliberate select only following-sibling::*[1].

Since blogger's editor widget hacks up my XSLT in horrifying ways, and I can't attach text files, I had to format this XSTL with non-breaking spaces and whatnot. Let me know if you want the real thing. Let's say the input looks like this (it must be sorted, perhaps by another XSLT, by starting time only):

<?xml version='1.0' ?>
<intervals>

<interval x="10" y="14.1155607415243584888223696987094362306"/>

<interval x="10" y="27.2574271976039591982711142331954001295"/>

<interval x="30" y="33.7147910106524433624672477551503835313"/>

<interval x="40" y="46.844920420920822280815378491005656766"/>

<interval x="50" y="61.30421963829719394371538034317434986025"/>


Then the XSLT to coalesce these intervals will look about like this:

<?xml version="1.0"?>
<xsl:stylesheet version="2.0"

xmlns:xsl=
"http://www.w3.org/1999/XSL/Transform"

xmlns:xs=
"http://www.w3.org/2001/XMLSchema">


<xsl:output indent="yes"/>


<!-- I could have named this template "start-recursion", but it's
convenient to be able to set the context node. --
>

<xsl:template match="interval">

<xsl:call-template name="coalesce-intervals">

<xsl:with-param name="next-interval" select="."/>

<xsl:with-param name="from" select="number(@x)" tunnel="yes"/>

<xsl:with-param name="to" select="number(@y)" tunnel="yes"/>

</xsl:call-template>

</xsl:template>


<xsl:template name="coalesce-intervals">

<xsl:param name="next-interval" as="element(interval)?"/>

<xsl:param name="from" as="xs:double" tunnel="yes"/>

<xsl:param name="to" as="xs:double" tunnel="yes"/>

<xsl:choose>

<!-- Stop the recursion. -->

<xsl:when test="not($next-interval)">

<interval x="{$from}" y="{$to}"/>

</xsl:when>

<!-- The current coalesced interval overlaps this one, so move on. -->

<xsl:when test="$to gt number($next-interval/@x)">

<xsl:call-template name="coalesce-intervals">

<xsl:with-param name="next-interval" select="$next-interval/following-sibling::interval[1]"/>

<!-- Extend the current interval if possible (hence max). -->

<xsl:with-param name="to" select="max((number($next-interval/@y), $to))" tunnel="yes"/>

</xsl:call-template>

</xsl:when>

<xsl:otherwise>

<!-- No more to coalesce. Output the "accumulator" and start again. -->

<interval x="{$from}" y="{$to}"/>

<xsl:apply-templates select="$next-interval"/>

</xsl:otherwise>

</xsl:choose>

</xsl:template>


<xsl:template match="/intervals">

<intervals>

<xsl:apply-templates select="interval[1]"/>

</intervals>

</xsl:template>
</xsl:stylesheet>


 

30 comments:

Anonymous said...

buy tramadol online what is tramadol hcl generic for - tramadol for dogs and humans

Anonymous said...

buy tramadol online buy tramadol topix - tramadol no prescription overseas

Anonymous said...

xanax online xanax 250 dosage - pass mouth swab drug test xanax

Anonymous said...

tramadol 50 mg tramadol addiction stories - tramadol hcl 50 mg price

Anonymous said...

generic xanax xanax pills what is it - best kind xanax bars

Anonymous said...

buy tramadol online dosage for tramadol 50mg for dogs - tramadol dosage for humans

Anonymous said...

buy tramadol online tramadol dosage for high - tramadol hcl 50 mg nausea

Anonymous said...

buy carisoprodol carisoprodol soma compound - buy carisoprodol online no prescription

Anonymous said...

tramadol online 150 mg tramadol high - order tramadol next day

Anonymous said...

no prescription xanax xanax generic . 5 mg - xanax pills ingredients

Anonymous said...

buy tramadol online how to order tramadol - tramadol hydrochloride 50 mg effects

Anonymous said...

buy tramadol online safe place order tramadol online - tramadol hcl dogs dosage

Anonymous said...

xanax online xanax with high blood pressure - xanax effects early pregnancy

Anonymous said...

buy cheap cialis online no prescription cialis 36 hour price - buy cialis online from us

Anonymous said...

learn how to buy tramdadol tramadol hcl 50 mg tab uses - order tramadol online international

Anonymous said...

learn how to buy tramdadol tramadol dosage supplied - tramadol for dogs purchase

Anonymous said...

tramadol online tramadol 50 mg para que es - tramadol withdrawal brain zaps

Anonymous said...

buy tramadol what is tramadol high like - tramadol 50mg online

Anonymous said...

buy tramadol tramadol use for withdrawal symptoms - tramadol withdrawal day 1

Anonymous said...

http://blog.dawn.com/dblog/buy/#21563 tramadol hcl 50 mg street value - legitimate online pharmacy tramadol

Anonymous said...

ativan without prescription ativan and alcohol liver - order ativan no prescription

Anonymous said...

buy lorazepam cheap ativan online - ativan for nausea

Anonymous said...

buy ativan online ativan 0.25 - ativan 1mg dosage

Anonymous said...

order ativan online ativan prolonged qt interval - ativan dosage levels

Anonymous said...

order tramadol online mastercard cheap tramadol cod delivery - buy tramadol online by cod

Anonymous said...

buy tramadol online tramadol 300 er - tramadol dosage in humans

Anonymous said...

Your post features proven necessarу to me. Іt’s extremеly helpful anԁ you are clearly really ωell-informed of thіs typе.

You hаve got popрed our sight
for уou to different opinion of this κind of tоρic using
intriguіng аnd strong contеnt.

my homepagе Buy Valium
Here is my site ; Buy Valium Online

Anonymous said...

http://www.achildsplace.org/banners/tramadolonline/#1257 order tramadol online - cheap tramadolonline

Anonymous said...

Przy użyciu szczelinę między gałęziami drzew a także liśćmi paproci widziała
wodę zatoki plus kawałek nieba. Nieoczekiwanie, z przejmującym dresz­czem wzruszenia, przypomniała samemu wygląd i nazwy narnijskich gwiazdozbiorów.


Here is my website; kliknij po dokładne informacje

Anonymous said...

Κażdy ludzie, któгуch poznałeś – rzeczуωіściе wszyscy – nіe
pojawili się tu przyρadkowo. Przуѕzli, bу Cię czegoś nаuczyć.
Z normу wybieramy sobie ludzi, jakiсh mamy sρotkać
pгzed narodzinami.
Atoli dzіsiaj zagłębie się w jakіś, specyficznу rodzaj poznania, mianowicie: Bliskości Inkагnасyϳnej.

Podеjrzewam, że każdy ma ω otoczenіu
osobę, jaką znalіśmy w pοprzednіch wcіelenіaсh… Jаkim spoѕοbem to
odczuć?

Also visіt my web-ѕite: http://www.thassos-dialogos.gr/giannis/?attachment_id=187