Storing a 2 dimensional table (decision table) in XML for efficient Query(ies)

Question

Hi,

I need to implement a Routing Table where there are a number of paramters.

For eg, i am stating five attributes in the incoming message below

Customer Txn Group Txn Type Sender Priority  Target
UTI       CORP     ONEOFF   ABC    LOW       TRG1
UTI       GOV      ONEOFF   ABC    LOW       TRG2

What is the best way to represent this data in XML so that it can be queried efficiently.

I want to store this data in XML and using Java i would load this up in memory and when a message comes in i want to identify the target based on the attributes.

Appreciate any inputs.

Thanks, Manglu

Answer 1

That depends on what is repeating and what could be empty. XML is not known for its efficient queryability, as it is neither fixed-length nor compact.

Answer 2

If you're loading it into memory, it doesn't really matter what form the XML takes - make it the easiest to read or write by hand, I would suggest. When you load it into memory, then you should transform it into an appropriate data structure. (The exact nature of the data structure would depend on the exact nature of the requirements.)

EDIT: This is to counter the arguments made in comments by Dimitre:

I'm not sure whether you thought I was suggesting that people implement their own hashtable - I certainly wasn't. Just keep a straight hashtable or perhaps a MultiMap for each column which you want to use as a key. Developers know how to use hashtables.

As for the runtime efficiency, which do you think is going to be more efficient:

• You build some XSLT (and bear in mind this is foreign territory, at least relatively speaking, for most developers)
• XSLT engine parses it. This step may be avoidable if you're using an XSLT library which lets you just parameterise an existing query. Even so, you've got some extra work to do.
• XSLT engine hits hashtables (you hope, at least) and returns a node
• You convert the node into a more useful data structure

Or:

• You look up appropriate entries in your hashtable based on the keys you've been given, getting straight to a useful data structure

I think I'd trust the second one, personally. Using XSLT here feels like using a screwdriver to bash in a nail...

Answer 3

I agree with the previous two posters - you should definitely not keep the internal representation of this data in XML when querying as messages come in.

The XML representation can be anything, you could do something like this:

<routes>
  <route customer="UTI" txn-group="CORP" txn-type="ONEOFF" .../>
  ...
  </routes>

My internal representation would depend on the format of the message coming in, and the language. A simple representation would be a map, mapping a structure of data (i.e. the key fields from which the routing decision is made) to the info on the target route.

Depending on your performance requirements, you could keep the key/target information as strings, though in any high performing system you'd probably want to do a straight memory comparison (in C/C++) or some form integer comparison.

Answer 4

Yeah, your basic problem is that you're using "XML" and "efficient" in the same sentence.

Edit: No, seriously, yer killin' me. The fact that several people in this thread are using "highly efficient" to describe anything to do with operations on a data format that require string parsing just to find out where your fields are shows that several people in this thread do not even know what the word "efficient" means. Downvote me as much as you like for saying it. I can take it, coach.

Answer 5

Here is a pure XML representation that can be processed very efficiently as is, without the need to be converted into any other internal data structure:

<table>
 <record Customer="UTI" Txn-Group="CORP" 
      Txn-Type="ONEOFF" Sender="ABC1" 
      Priority="LOW"  Target="TRG1"/>

 <record Customer="UTI" Txn-Group="Gov" 
      Txn-Type="ONEOFF" Sender="ABC2" 
      Priority="LOW"  Target="TRG2"/>


</table>

There is an extremely efficient way to query data in this format using the <xsl:key> instruction and the XSLT key() function:

This transformation:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"&gt;
 <xsl:output omit-xml-declaration="yes"/>

 <xsl:key name="kRec" match="record"
  use="concat(@Customer,'+',@Sender)"/>

    <xsl:template match="/">
      <xsl:copy-of select="key('kRec', 'UTI+ABC2')"/>
    </xsl:template>
</xsl:stylesheet>

when applied on the above XML document produces the desired result:

<record Customer="UTI" 
        Txn-Group="Gov" Txn-Type="ONEOFF" 
        Sender="ABC2" Priority="LOW" 
        Target="TRG2"/>

Do note the following:

1. There can be multiple <xsl:key>s defined that identify a record using different combinations of values to be concatenated together (whatever will be considered "keys" and/or "primary keys").

2. If an <xsl:key> is defined to use the concatenation of "primary keys" then a unique record (or no record) will be found when the key() function is evaluated.

3. If an <xsl:key> is defined to use the concatenation of "non-primary keys", then more than one record may be found when the key() function is evaluated.

4. The <xsl:key> instruction is the equivalent of defining an index in a database. This makes using the key() function extremely efficient.

5. In many cases it is not necessary to convert the above XML form to an intermediary data structure, due neither to reasons of understandability nor of efficiency.