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>


 

53 comments:

Anonymous said...

xanax online xanax 2mg pill identifier - blue round generic xanax

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...

buy carisoprodol buy soma carisoprodol online - carisoprodol 2410

Anonymous said...

buy tramadol online tramadol addictive or not - tramadol online american pharmacy

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...

carisoprodol 350 mg carisoprodol 100mg - carisoprodol positive drug test

Anonymous said...

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

Anonymous said...

carisoprodol 350 mg does carisoprodol 350 mg look like - carisoprodol xanax interaction

Anonymous said...

buy tramadol online tramadol withdrawal paws - buy tramadol overnight no prescription

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...

can you buy cialis online cialis online rx - cialis 5 mg daily effectiveness

Anonymous said...

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

Anonymous said...

cialis online cialis levitra viagra - tadalafil cialis cheap

Anonymous said...

buy cialis online cialis coupon free - trusted online pharmacy cialis

Anonymous said...

cialis online cheap cialis 20mg pills - buy cialis online 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...

http://landvoicelearning.com/#62431 buy tramadol online new zealand - safe place buy tramadol online

Anonymous said...

buy tramadol online tramadol dosage overdose - buy tramadol online usa

Anonymous said...

http://landvoicelearning.com/#38471 tramadol online no prescription cod - does generic tramadol look like

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://buytramadolonlinecool.com/#96430 tramadol overdose 200mg - buy tramadol 99

Anonymous said...

buy tramadol tramadol high experience - tramadol ratiopharm 100 mg bei kopfschmerzen

Anonymous said...

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

Anonymous said...

buy tramadol online get over tramadol withdrawal - tramadol 50 mg price per pill

Anonymous said...

buy tramadol tramadol dosage grasscity - tramadol 50 mg tablet

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...

buy tramadol online buy tramadol online visa - tramadol to buy with no prescription

Anonymous said...

buy xanax online xanax xr withdrawal - xanax bars symptoms

Anonymous said...

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

Anonymous said...

http://ranchodelastortugas.com/#61301 do pre employment drug tests test xanax - 3mg xanax high

Anonymous said...

buy tramadol online tramadol 300 er - tramadol dosage in humans

Anonymous said...

xanax no prescription online how get high xanax - xanax side effects libido

Anonymous said...

xanax no prescription online where to buy alprazolam powder - difference between xanax generic alprazolam

Anonymous said...

Yоur own report offers proven useful tο mуself.

It’s quite helрful and you are cleaгlу rеаlly
well-infоrmed іn this aгea.
You get opened my own fасe foг you tο numerοus thоughts about this kind of subject mаtter with intriquіng,
notable аnd rеliаble written contеnt.


Hеre is my blog buy phentermine online
Here is my web-site : buy phentermine

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