Category Archives: CMDBf

May 7, 2008

The elusive XPath nodeset serialization

I have been involved in various capacity with five different specifications that define a GET (or GET-like) operation that takes as input an XPath expression used to pinpoint the subset of the XML document that should be retrieved (here is a quick history as of a couple of years ago, more has happened since). And I must shamefully admit that all but one are simply impossible to implement in an interoperable way.

That’s because they instruct implementers to return an XPath nodeset in the response SOAP message but say nothing about how to serialize the nodeset. While an XPath nodeset contains the kind of things that make up an XML document, it is not an XML document by itself. There is an infinite number of possible ways to serialized an XPath nodeset into XML. To have any hope of interoperability on this, a serialization algorithm has to be clearly described by the specification. Which hasn’t happened.

Let’s start with WS-ResourceProperties (WS-RP). It has a QueryResourceProperties operation that takes an XPath expression as input. The specification says that “the response MUST contain an XML serialization of the results of evaluating the QueryExpression against the resource properties document“. Great, thanks. The example provided happens to return a nodeset with only one node (a boolean), which is implicitly serialized into the text representation of that boolean. What if there is more than one node in the nodeset? What about other types of nodes?

Moving on to WS-Management, which defines a SOAP header that uses XPath to qualify a WS-Transfer GET request such that it only retrieves a subset of the target XML document. While it does a better job than WS-RP at describing the input (e.g. it specifies the context node and what namespace declarations are in scope for the XPath evaluation) it is even more cavalier than WS-RP in describing the output: “the output (lines 53-55) is like that supplied by a typical XPath processor and might or might not contain XML namespace information or attributes“. By “a typical XPath processor” we should understand MSXML I suppose. But as far as I know a “typical XML processor” doesn’t return XML, it returns language-specific data structures (e.g. a C# or Java object, like a nu.xom.Nodes instance). And here too, the examples only use single-node nodesets.

WS-ResourceTransfer (WS-RT) was supposed to be the convergence of these two efforts, so presumably it would have learned from their mistakes. While it is better written in general than its predecessors, it fails just as badly with regards to specifying the nodeset serialization. And once again, the example provided uses a nodeset with just one node.

And then came the CMDBf query operation which, for some unclear reason, was deemed in need of a built-in XPath transformation of records. As I pointed out in my review of CMDBf 1.0 at the time, this feature was added without taking the pain to define the XML serialization of the resulting nodeset. And there isn’t even an example of the XPath serialization.

It is sad in a way, but the only specification that acknowledges the problem and addresses it came before any of the four above even got started. It is the WSMF (Web Services Management Framework) work that we did at HP, and more specifically the “note on dynamic attributes and meta information” (not available at HP anymore but available from archive.org) . This specification was the first one to define a GET operation that is qualified by an XPath expression. Unlike its successors it also explicitly narrowed down the types of nodes that could be selected (“The manager MUST NOT send as input an XPath statement that returns a nodeset containing nodes other than element, attribute and namespace nodes“). And for those valid types it described how to serialized them in XML (“When a node in the result nodeset is an attribute node, for the sake of the response it is serialized as an element node which has the same name as the name of the original attribute (see example 4 for an illustration). The element is in the same namespace as the namespace the attribute it represents is in. This applies to namespace nodes as well, they are serialized like an attributes in the xmlns namespace“). Turning an attribute into an element of the same QName might not be the smartest thing in retrospect (after all there may be an element by that QName already) but at least we recognized and addressed the problem.

But all is good now, I am told, because XPath 2.0 is here, along with a clean data model and a well-described serialization.

Not so. Anyone wanting to use XPath for a SOAP-based query language still would have to specify a serialization.

The first problem with the W3C serialization is that the XML output method doesn’t work for all nodesets. Try to use it on a nodeset that contains a top-level attribute node and you get error err:SENR0001. And even for the nodesets it accepts, it sometimes returns less-than-useful results. For example, if your XPath is of the form /employee/name/text() and you have four employees, the result will look something like this:

“Joe SmithKathy O’ConnorHelen MartinBrian Jones”

Concatenated text values without separators. I guess W3C is like a department store, they don’t offer complimentary wrapping anymore…

That’s why the nux.xom.xquery.ResultSequenceSerializer class had to define its own wrapping mechanims to produce a useful XML serialization. The API gives you the choice between the W3C_ALGORITHM and the WRAP_ALGORITHM.

Bottom line, and however much some would like to think of it that way, XPath (1 or 2) is not an XML subsetting/transformation mechanism. It could be used to create one (as XSLT does), but you have to do your own plumbing.

In addition to the technical aspects of this discussion, what else can be learned from this sad state of things? The fact that all these specifications define an XPath-driven query mechanism that is simply broken (beyond the simplest use cases) withouth anyone even noticing tells me that there isn’t a real need for full XPath query over SOAP (and I am talking about XPath 1.0, the introduction of XPath 2.0 in CMDBf is even more out there). A way to retrieve individual elements (and maybe text values) is all that is needed for 99% of the use cases addressed by these specifications. Users would be better served (especially in a version 1.0) by specifications that cover the simple case correctly than by overly generic, complex and poorly documented features. There is always time to add features later if the initial specification is successful enough that users encounter its limitations.

3 Comments

Filed under CMDB Federation, CMDBf, Everything, SOAP, Specs, Standards, Tech, W3C, WS-Management, WS-ResourceTransfer, XPath

March 26, 2008

XPath brain teasers: graph queries in XPath 1.0

Consider this piece of XML, in which the <g> elements represent groups that the people are part of (groups can have several members and people can be members of several groups). For example, “paul” is a member of groups 2, 3 and 4.

<doc>
  <person name="alan"><g>1</g><g>2</g><g>4</g></person>
  <person name="marc"><g>1</g><g>2</g><g>3</g></person>
  <person name="paul"><g>2</g><g>3</g><g>4</g></person>
  <person name="ivan"><g>2</g><g>4</g></person>
  <person name="eric"><g>4</g></person>
</doc>

This is essentially a graph structure, represented as a tree because of the constraints of XML.

Using a graph query language like SPARQL, answering questions such as “which groups contain alan, paul and ivan” would be trivial. In SPARQL that would be something like:

SELECT ?group
WHERE {
  [ ns:hasName "alan" ] ns:partOf ?group .
  [ ns:hasName "paul" ] ns:partOf ?group .
  [ ns:hasName "ivan" ] ns:partOf ?group . }

In the CMDBf query language, another graph query language, it would be more verbose but just as straightforward to express:

<query>
  <itemTemplate id="alan">
    <recordConstraint>
      <propertyValue namespace="http://example.com/people" localName="name">
        <equal>alan</equal>
      </propertyValue>
    </recordConstraint>
  </itemTemplate>
  <itemTemplate id="paul">
    <recordConstraint>
      <propertyValue namespace="http://example.com/people" localName="name">
        <equal>paul</equal>
      </propertyValue>
    </recordConstraint>
  </itemTemplate>
  <itemTemplate id="ivan">
    <recordConstraint>
      <propertyValue namespace="http://example.com/people" localName="name">
        <equal>ivan</equal>
      </propertyValue>
    </recordConstraint>
  </itemTemplate>
  <itemTemplate id="group"/>
  <relationshipTemplate id="alan-in-group">
    <recordConstraint>
      <recordType namespace="http://example.com/people" localName="partOf"/>
    </recordConstraint>
    <sourceTemplate ref="alan"/>
    <targetTemplate ref="group"/>
  </relationshipTemplate>
  <relationshipTemplate id="paul-in-group">
    <recordConstraint>
      <recordType namespace="http://example.com/people" localName="partOf"/>
    </recordConstraint>
    <sourceTemplate ref="paul"/>
    <targetTemplate ref="group"/>
  </relationshipTemplate>
  <relationshipTemplate id="ivan-in-group">
    <recordConstraint>
      <recordType namespace="http://example.com/people" localName="partOf"/>
    </recordConstraint>
    <sourceTemplate ref="ivan"/>
    <targetTemplate ref="group"/>
  </relationshipTemplate>
</query>

But using the right tool for the job is just no fun. How can we answer this question using XPath 1.0? Your first response might be “this is the wrong XML format”. And yes, we could switch things around and make people children of groups rather than the contrary, as in:

<invertedDoc>
  <group number="1"><p>alan</p><p>marc</p></group>
  <group number="2"><p>alan</p><p>marc</p><p>paul</p></group>
  <group number="3"><p>marc</p><p>paul</p></group>
  <group number="4"><p>alan</p><p>paul</p><p>ivan</p><p>eric</p></group>
</invertedDoc>

That would make the “is there a group that contains alan, paul and ivan” question very easy to answer in XPath 1.0, but then I would ask you “which persons are part of groups 1, 2 and 4” and you’d be back to the same problem. You won’t get off the hook that easily.

So, XPath brain teaser #1 is: how to answer “which groups contain alan, paul and ivan” using XPath 1.0 on the first XML document (<doc>, not <invertedDoc>)?

The answer is:

/doc/person/g[../@name="alan" and text()=/doc/person/g[../@name="paul"
  and text()=/doc/person/g[../@name="ivan"]]]

Which returns:

<g>2</g>
<g>4</g>

It doesn’t look like much, but go through it carefully and you’ll see that we have somewhat of a recursive loop (as close as XPath can get to recursion). With these loops, we go through the entire document n^m times, where n is the number of <people> elements and m is the number of names that we need to look for in each group (3 in the present case: alan, paul an ivan). In our simple example, that’s 5^3=125. Not very efficient for a query that could, with the right language, be answered in one pass through the document (I am assuming a basic XPath engine, not one that may be able pre-analyze the query and optimize its execution).

Which takes us to XPath brain teaser #2: can you find a way to answer that same question with fewer passes through the doc?

There is an answer, but it requires the document to adopt a convention to make all group IDs multiples of 10. 1 stays 1, 2 becomes 10, 3 becomes 100, etc.

The document that we are querying against now looks like this:

<?xml version="1.0" encoding="iso-8859-1"?>
<doc>
  <person name="alan"><g>1</g><g>10</g><g>1000</g></person>
  <person name="marc"><g>1</g><g>10</g><g>100</g></person>
  <person name="paul"><g>10</g><g>100</g><g>1000</g></person>
  <person name="ivan"><g>10</g><g>1000</g></person>
  <person name="eric"><g>1000</g></person>
</doc>

On this document, the following XPath:

sum(((/doc/person[@name="alan"]) | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]) )/g)

returns: 3131

Which is the answer to our question. It doesn’t look like it? Well, here is the key to decode this answer: every “3” digit that appears in this number represents a group that contains all three required members (alan, paul and ivan). In this example, we have a “3” in the “thousands” position (so group 1000 qualifies) and a “3” in the “tens” position (so group 10 qualifies).

How do we get the 3131 result? In that XPath statement, the processor simply picks out the <person> elements that correspond to alan, paul and ivan. Then it simply adds up the value of all the <g> elements contained in all these selected <person> elements. And that’s our 3131.

The transformation of group values from n to 10^(n-1) is what allows us to turn a recursive loop into a simple addition of group values. Each column in the running sum keeps track of the number of people who are in the group that corresponds to that column (the “units” column corresponds to group 1, the “tens” column corresponds to group 10, the “hundreds” column corresponds to group 100, etc). This is why we had to turn the group IDs to multiples of 10.

Does this approach meet our goal of requiring fewer passes through the document than the XPath that is the solution to brain teaser #1? Yes, because we only scan the content of the <people> elements we are interested in (and we only scan each of them once). We don’t care how many groups there are. So we go from n^m passes through the entire document to m passes (one for each <person> element that we need to locate). In our example, it means 125 versus 3.

One potential gotcha is that we are assuming that a given group only appears once inside a given <person> element. Which seems logical. But what if the maintainer of the document is sloppy and we suspect that he may sometimes add a group inside a <person> element without first checking whether that <person> element already contains that group? We can protect ourselves against this by filtering out the redundant <g> elements inside a <person>. To do so, we replace replace:

sum(((/doc/person[@name="alan"]) | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]) )/g)

with:

sum(((/doc/person[@name="alan"]) | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]) )/g[not(text()=preceding-sibling::g)])

The [not(text()=preceding-sibling::g)] part removes <g> elements that have a preceding sibling with the same value. At little processing cost.

If you don’t like the looks of this “3131” result, you can add a simple transformation into the XPath to turn it into 1010, which can be interpreted as the sum of the numbers corresponding to all the groups that satisfy our request (again, groups 1000 and 10 in this case):

translate(sum(((/doc/person[@name="alan"]) | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]) )/g), "123456789", "001000000")

Returns: 1010.

If you are still not satisfied, we can actually extract the <g> elements (basically the same result as in the XPath statement that corresponds to brain teaser #1), but at the cost of a bit more work for the XPath processor: instead of calculating the 3131 result once, you do it once for each group that alan is a member of (why alan? it doesn’t matter, pick paul or ivan if you want). The corresponding XPath is:

/doc/person[@name="alan"]/g[floor(sum(((/doc/person[@name="alan"])
  | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]) )/g) div text()) mod 10 = 3]

Which returns:

<g>10</g>
<g>1000</g>

And here too, if you are concerned that the same group may appear more than once inside the <person name=”alan”> element and you don’t want that to appear in the result, you can remove the <g> elements that have a preceding sibling with the same value (you have to remove them twice, once in the sum calculation and once in the selection of the <g> elements for display, which is why [not(text()=preceding-sibling::g)] appears twice below):

/doc/person[@name="alan"]/g[floor(sum(((/doc/person[@name="alan"])
  | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]))/g[not(text()=preceding-sibling::g)])
  div text()) mod 10 = 3][not(text()=preceding-sibling::g)]

BTW, a practical advantage of presenting the result as a set of element nodes rather than as a number is that many interactive XPath engines (including many on-line ones as well as JDeveloper 10.1.3.2) aren’t happy with resulting nodesets in which the nodes are not element nodes. Of course XPath APIs don’t have that problem.

We have already acknowledged one limitation of our approach, the need to transform the XML doc (by turning “2” into “10”, “3” into “100”, etc). Now comes XPath brain teaser 3: what are the other limitations of this approach?

The first one is obvious (and doesn’t’ have much to do with XPath per se): what happens when there is a carry-over in the computation of the sum() function? Bad stuff is the answer. Basically, we can’t have this. Which means that since our calculations take place in base 10 (the only one XPath supports) we are limited to a maximum number of 9 persons in a group. We can look for groups that contain alan, paul and ivan, but not for those that contain all 15 members of a rugby team.

The second limitation requires a bit more XPath wonkery. Or rather IEEE 754 wonkery since numbers in XPath are defined as using the IEEE 754 double-precision (64-bit) format. Which has a 52 bits mantissa. The format normalizes the mantissa such that it only has one significant bit before the decimal. And since that bit can only be “1” it is ignored in the representation, which means we actually get 53 bits worth of precision. I would have thought that this would give us 16 significant digits in decimal form, but when I test this by converting 9999999999999999 into 64-bit representation I get 0100001101000001110000110111100100110111111000001000000000000000 or 4341C37937E08000 in hex which gets turned back into the decimal value 10000000000000000. Looks like we can only count on 15 digits worth of precision for a decimal integer in XPath.

What does it mean for our application? It means that we can only track 15 groups in our sum(). So if the document has more than 15 different groups we are out of luck. In the spirit of a “glass half full”, let’s count (no pun intended) ourselves lucky that XPath chose double precision (64-bit) and not single precision (32-bit)…

It would be nice if we could free ourselves of the constraint of having group IDs be multiples of 10. Maybe we can turn them into multiples of 10 as we go, by calculating 10^(n-1) whenever we hit such an ID? The first problem with this is that XPath does not have an exponentiation (^) operator. But this one is surmountable, because we don’t need a generic exponentiation operator, we just need to be able to calculate 10^n for n ranging from 0 to 14 (remember, we are limited to 15 digits of precision). We can simply seed our XPath with an enumerated result list. Sure it’s ugly, but by now it should be clear that we are far removed from any practical application anyway (practically-minded people would have long moved to another query language or at least to version 2.0 of XPath). If you’re still reading you must admit to yourself that your inner geek is intrigued by this attempt to push XPath where it was never meant to go. Our poor man exponentiation function looks like this:

substring-before(substring-after("A0:1 A1:10 A2:100 A3:1000 A4:10000
  A5:100000 A6:1000000 A7:10000000 A8:100000000 A9:1000000000
  A10:10000000000 A11:100000000000 A12:1000000000000
  A13:10000000000000 A14:100000000000000", concat("A", 12, ":")), " ")

When you execute this XPath (on whatever document), it returns: “1000000000000”. Replace the 12 with any other integer between 0 and 14 and the XPath will return 10 to the power of your integer. So in effect, we have emulated the exponentiation function for all needed values.

Unfortunately, this doesn’t take us very far. It would be tempting to plug this ad-hoc exponentiation function in our precedent XPath (at the place where we retrieve the value of the <g> element, as in:

sum(substring-before(substring-after("A1:1 A2:10 A3:100 A4:1000
  A5:10000 A6:100000 A7:1000000 A8:10000000 A9:100000000
  A10:1000000000 A11:10000000000 A12:100000000000
  A13:1000000000000 A14:10000000000000 A15:100000000000000",
  concat("A", ((/doc/person[@name="alan"])
  | (/doc/person[@name="paul"])
  | (/doc/person[@name="ivan"]) )/g, ":")), " "))

And to hope that our 3131 result pops out again. But this is not to be.

There are two problems. First, this is not valid XPath because the sum() function can only apply to a nodeset, not strings (or numbers for that matter). Second, even if sum() was more forgiving what we are sending to it is not several strings. It’s one string. That’s because the insertion of the ((/doc/person[@name=”alan”]) | (/doc/person[@name=”paul”]) | (/doc/person[@name=”ivan”]) )/g nodeset as an operand to a function that expects a string (in this case, our ad-hoc exponentiation function) doesn’t generate a set of text nodes that contain the result of running the function on all nodes in the nodeset. Rather, it generates the result of the evaluation of the function on the one string that corresponds to the string-value for the nodeset (which is the string value of its first node). Feel free to re-read this slowly.

You can’t modify nodesets in XPath, just integers and strings. Once you’ve turned your nodeset into another object, you’re out of the loop. Literally.

Sorry to end with a downer. At least I hope this entertained you, helped you better understand XPath or illuminated the difference between a graph query language and a tree query language.

[UPDATED 2008/3/27: For more XPath fun, Dare Obasanjo provides a guided walk through some tricky aspects of the XPath syntax. Unlike me, his focus is on understanding the syntax, not abusing it… ;-)]

11 Comments

Filed under Brain teaser, CMDBf, Everything, Graph query, SPARQL, XPath

March 4, 2008

Of graphs and trees: Kingsley Idehen to the rescue

I just read the transcript of Jon Udell’s podcast interview of Kingsley Idehen. It’s almost two years old but it contains something that I have tried (and mostly failed) to explain for a while now, so maybe borrowing someone else’s words (and credibility) would help.

Kingsley says:

“A graph model, ideally, will allow you to explore almost all the comprehensible dimensions of the nodes in that network. So you can traverse that network in a myriad of different ways and it will give you much more flexibility than if you’re confined to a tree, in effect, the difference between XQuery and SPARQL. I always see the difference between these two things as this. If you visualize nodes on a network, SPARQL is going to get you to the right node. Your journey to what you want is facilitated by SPARQL, and then XQuery can then take you deeper into this one node, which has specific data that the graph traversal is taking you to.”

Nicely said, especially considering that this is not a prepared statement but a transcript of a (presumably) unscripted interview.

He later provides an example:

“Let’s take a microformat as an example. HCard, or an hCalendar, is a well-formed format. In a sense, it’s XML. You can locate the hCard in question, so if you had a collection of individuals who had full files on the network in the repository, it could be a graph of a social network or a group of people. Now, through that graph you could ultimately locate common interests. And eventually you may want to set up calendars but if the format of the calendar itself is well formed, with XQuery you can search a location, with XPath it’s even more specific. Here you simply want to get to a node in the content and to get a value. Because the content is well formed you can traverse within the content, but XQuery doesn’t help you find that content as effectively because in effect XQuery is really all about a hierarchical model.”

Here is one way to translate this to the IT management domain. Replace hCard with an XML-formated configuration record. Replace the graph of social relationships with a graph of IT-relevant relationships (dependency, ownership, connections, containment…). Rather than attempt to XQuery across an entire CMDB (or, even worse, an entire CMDB federation), use a graph query (ideally SPARQL) to find the items of interest and then use XPath/XQuery to drill into the content of the resulting records. The graph query language in CMDBf is an attempt to do that, but it has to constantly battle attempts to impose a tree-based view of the world.

This also helps illustrate why SPARQL is superior to the CMDBf query language. It’s not just that it’s a better graph query language, one that has received much more review and validation by people more experienced in graph theory and queries, and one that is already widely implemented. It also does something that CMDBf doesn’t attempt to do: it lets you navigate the graph based on the semantics appropriate for the task at hand (dependency relationships, governance rules, distributed performance management…), something that CMDBf cannot do. There is more to classification than simply class inheritance. I think this is what Kingsley refers to when he says “in a myriad of different ways” in the quote above.

Here is a way to summarize the larger point (that tree and graph views are complementary):

Me Tarzan, you Jena

Where Tarzan (appropriately) represents the ability to navigate trees and Jane/Jena represents the ability to navigate graphs (Jena, from HP Labs, is the leading open source RDF/OWL/SPARQL framework). As in the movie, they complement each other (to the point of saving one another’s life and falling in love, but I don’t ask quite that much of SPARQL and XQuery).

On a related topic, I recently saw some interesting news from TopQuadrant. Based on explicit requests from the majority of their customers, they have added capabilities to their TopBraid Composer product to better make use of the RDF/OWL support in the Oracle database. TopQuadrant is at the forefront of many semantic web applications and the fact that they see Oracle being heavily used by their customers is an interesting external validation.

[UPDATED 2008/03/05: more related news! The W3C RDB2RDF incubator group has started is life at W3C, chaired by my colleague Ashok Malhotra, to work on mappings between RDF/OWL and relational data.]

1 Comment

Filed under CMDB Federation, CMDBf, Everything, Graph query, Query, RDF, SPARQL, Standards, W3C, XPath, XQuery

February 6, 2008

DMTF members as primary voters?

I just noticed this result from the 2007 DMTF member survey (taken a year ago, but as far as I can tell just released now). When asked what their “most important interoperability priority” is, members made it pretty clear that they want the current CIM/WBEM infrastructure fixed and polished. They seem a lot less interested in these fancy new SOAP-based protocols and even less in using any other model than CIM.

It will be interesting to see what this means for new DMTF activities, such as CMDBf or WS-RC, that are supposed to be model-neutral. A few possibilities:

the priorities of the members change over time to make room for these considerations
turn-over (or increase) in membership brings in members with a different perspective
the model-neutral activities slowly get more and more CIM-influenced
rejection by the DMTF auto-immune system

My guess is that the DMTF leadership is hoping for #1 and/or #2 while the current “base” (to borrow from the US election-season language) wouldn’t mind #3 or #4. I am expecting some mix of #2 and #3.

Pushing the analogy with current US political events further than is reasonable, one can see a correspondence with the Republican primary:

CIM/WBEM is Huckabe, favored by the base
CMDBf/WS-RC/WS-Management etc is Romney, the choice of the party leadership
At the end, some RDF and HTTP-based integration-friendly approach comes from behind and takes the prize (McCain)

Then you still have to win the general election (i.e. industry adoption of whatever the DMTF cooks up).

[UPDATED 2008/2/7: the day after I write this entry, Romney quits the race. Bad omen for CMDBf and WS-RC? ;-) ]

Comments Off on DMTF members as primary voters?

Filed under CMDB Federation, CMDBf, DMTF, Everything, Standards, WS-Management

January 10, 2008

An interesting business process query language

While doing some research on the different ways to probe and squeeze business process definitions to extract insight relevant for IT management I ran into this very interesting paper: Querying Business Processes. It defines a query language (called BP-QL) to query process definitions. Not much in common with CMDB Federation at first sight, and CMDBf was not on my mind at the time. Until I looked at the description of the query language that the researchers came up with. It is strikingly similar to the CMDBf query language. This is not very surprising since both are graph-based query languages that rely on patterns (where the patterns mix topological aspects with constraints on node/link properties).

CMDBf is more complete in some respects. It supports properties on the relationships, not just the items. The “depthLimit” element provide more control than BP-QL’s double-headed edges. BP-QL has its own extra features, including support for joins (something we discussed in CMDBf and that could be added to the specification) and negation at the graph level (e.g. A and B are not connected by any relationship of type “foo”, which may be useful but one should remember that CMDB discovery is rarely guaranteed to be comprehensive so an open-world approach is often preferable).

Assuming a suitable CMDB model for business processes, a CMDBf-compliant CMDB should cover many of the simpler use cases addressed by BP-QL. And reciprocally, the more advanced features in BP-QL are not really specific to business process definitions (even though that’s the scope of the paper) and could well be applied to CMDBf. I was also very interested by the BP-QL “compact representation” and the implementation choices. I hadn’t heard of Active XML before, something to look into especially if, as the paper hints, it does a better job than XQuery at dealing with idrefs. And Active XML introduces some interesting federation (or at least distribution) capabilities that are not currently exploited by BP-QL but which I find intriguing and which reinforce the parallel with the declared goal of CMDBf.

Is this similarity between the query languages just an interesting pattern to notice? Or is there more to it? The parallel between BP-QL and CMDBf invites the question of whether one should model business processes in a CMDB. And if so, is a business process represented by just one CI or do you break it down into a model similar to the one the BP-QL query language works on? You would need to go that far if you wanted to use queries to the CMDB to answer questions such as those handled by the BP-QL engine. And by doing this in the context of a CMDB that contains a lot more than just process definitions, you’d be able to enrich the queries with considerations from other domains, such as application or host topology. Modeling business process steps/activities may seem like very fine-grained modeling for a CMDB, but isn’t this part of the sales pitch for federated CMDBs, that participants in the federation can provide different levels of granularity? Of course, CMDB federation might never work out. If it does work and if we use it that way, we are not talking about just supporting change management processes (which are more likely to take place at the level of the overall process definition than the individual step) but rather about management integration for a wide variety of use cases. If that means we need to drop the term CMDB along the way (and leave it for the sole usage of the IT process people), I am more than happy to oblige.

[UPDATE on 2008/01/11: Prof. Milo pointed me to this follow-up paper that proposes a similar looking query language except that this time it is targeted at monitoring process instances rather than analyzing process definitions. And the monitoring runs as a set of BPEL processes within the monitored BPEL engine. Her group is doing some very interesting work.]

2 Comments

Filed under Business Process, CMDB Federation, CMDBf, Everything, Graph query, Mgmt integration, Query, Research

December 19, 2007

How not to re-use XML technologies

I like XML. Call me crazy but I find it relatively easy to work with. Whether it is hand-editing an XML document in a text editor, manipulating it programmatically (as long as you pick a reasonable API, e.g. XOM in Java), transforming it (e.g. XSLT) or querying an XML back-end through XPath/XQuery. Sure it carries useless features that betray its roots in the publishing world (processing instructions anyone?), sure the whole attribute/element overlap doesn’t have much value for systems modeling, but overall it hits a good compromise between human readability and machine processing and it has a pretty solid extensibility story with namespaces.

In addition, the XML toolbox of specifications is very large and offers standard-based answers to many XML-related tasks. That’s good, but when composing a solution it also means that one needs to keep two things in mind:

not all these XML specifications are technically sound (even if they carry a W3C stamp of approval), and
just because XML’s inherent flexibility lets one stretch a round hole, it doesn’t mean it’s a good idea to jam a square peg into it.

The domain of IT management provides examples for both of these risks. These examples constitute some of the technical deficiencies of management-related XML specifications that I mentioned in the previous post. More specifically, let’s look at three instances of XML mis-use that relate to management-related specifications. We will see:

a terrible XML specification that infects any solution it touches (WS-Addressing, used in WS-Management),
a mediocre XML specification that has plenty of warts but can be useful for a class of problems, except in this case it isn’t (XSD, used in SML), and
a very good XML specification except it is used in the wrong place (XPath, used in CMDBf).

Let’s go through them one by one.

WS-Addressing in WS-Management

The main defect of WS-Management (and of WSDM before it) is probably its use of WS-Addressing. SOAP needs WS-Addressing like a migraine patient needs a bullet in the head (actually, four bullets in the head since we got to deal with four successive versions). SOAP didn’t need a new addressing model, it already had URIs. It just needed a message correlation mechanism. But what we got is many useless headers (like wsa:Action) and the awful EPR construct which solves a problem that didn’t exist and creates many very real new ones. One can imagine nifty hacks that would be enabled by a templating mechanism for SOAP (I indulged myself and sketched one to facilicate mash-up style integrations with SOAP) but if that’s what we’re after then there is no reason to limit it to headers.

XSD in SML

The words “Microsoft” and “bully” often appear in the same sentence, but invariably “Microsoft” is the subject not the object of the bullying. Well, to some extent we have a reverse example here, as unlikely as it may seem. Microsoft created an XML-based meta-model called SDM that included capabilities that looked like parts of XSD. When they opened it up to the industry and floated the idea of standardizing it, they heard back pretty loudly that it would have to re-use XSD rather than “re-invent” it. So they did and that ended up as SML. Except it was the wrong choice and in retrospect I think it would have been better to improve on the original SDM to create a management-specific meta-model than swallow XSD (SML does profile out a few of the more obscure features of XSD, like xs:redefine, but that’s marginal). Syntactic validation of documents is very different from validation of IT models. Of course this may all be irrelevant anyway if SML doesn’t get adopted, which at this point still looks like the most likely outcome (due to things like the failure of CML to produce any model element so far, the ever-changing technical strategy for DSI and of course the XSD-induced complexity of SML).

XPath in CMDBf

I have already covered this in my review of CMDBf 1.0. The main problem is that while XML is a fine interchange format for the CMDBf specification, one should not assume that it is the native format of the data stores that get connected. Using XPath as a selector language makes life difficult for those who don’t use XML as their backend format. Especially when it is not just XPath 1.0 but also the much more complex XPath 2.0. To make matters worse, there is no interoperable serialization format for XPath 1.0 nodesets, which will prevent any kind of interoperability on this. That omission can be easily fixed (and I am sure it will be fixed in DMTF) but that won’t address the primary concern. In the context of CMDBf, XPath/XQuery is an excellent implementation choice for some situations, but not something that should be pushed at the level of the protocol. For example, because XPath is based on the XML model, it has clear notions of order of elements. But what if I have an OO or an RDF-based backend? What am I to make of a selector that says that the “foo” element has to come after the “bar” element? There is no notion of order in Java attributes and/or RDF properties.

Revisionism?

My name (in the context of my previous job at HP) appears in all three management specifications listed above (in increasing level of involvement as contributor for WS-Management, co-author for SML and co-editor for CMDBf) so I am not a neutral observer on these questions. My goal here is not to de-associate myself from these specifications or pick and choose the sections I want to be associated with (we can have this discussion over drinks if anyone is interested). Some of these concerns I had at the time the specifications were being written and I was overruled by the majority. Other weren’t as clear to me then as they are now (my view of WS-Addressing has moved over time from “mostly harmless” to “toxic”). I am sure all other authors have a list of things they wished had come out differently. And while this article lists deficiencies of these specifications, I am not throwing the baby with the bathwater. I wrote recently about WS-Management’s potential for providing consistency for resource manageability. I have good hopes for CMDBf, now in the DTMF, not necessarily as a federation technology but as a useful basis for increased interoperability between configuration repositories. SML has the most dubious fate at this time because, unlike the other two, it hasn’t (yet?) transcended its original supporter to become something that many companies clearly see fitting in their plans.

[UPDATED 2008/3/27: For an extreme example of purposely abusing XML technologies (namely XPath in that case) in a scenario in which it is not the right tool for the job (graph queries), check out this XPath brain teasers article.]

4 Comments

Filed under CMDB Federation, CMDBf, Everything, IT Systems Mgmt, Microsoft, SML, SOAP, SOAP header, Specs, Standards, Tech, WS-Management, XOM

November 28, 2007

CMDBf now in the hands of the DMTF

It’s now official, the CMDBf specification has been submitted to the DMTF and will be standardized there. Here is the press release and here is the specification (unchanged) republished on the DMTF site. The CMDBf working group was created a while ago at the DMTF but I didn’t report it since it wasn’t clear to me whether that was public information or not. The press release makes this clear now.

As a side note, this is one of my ongoing frustrations with the DMTF. Almost everything happens in private with no publicly-accessible URL until a press release comes out and of course lots of interesting things happen that don’t get a press release. I have heard many times that the DMTF is working on opening up the process, but I still haven’t seen much change. If this had been OASIS or W3C, the call for formation of the new working group would have been publicly accessible even before the group was created. OK, end of ranting.

As always, there isn’t much useful information to be gleaned from the text of the press release. Only that, as expected, the authors addressed the question of how this relates to CIM, since for many DMTF=CIM. So the press release proactively declares that the CMDBf work will not be limited to CIM-modeled configuration data. What this means in practice will be seen later (e.g. will there be CIM-specific extensions?).

Having seen how executive quotes for press releases get generated I hate to read too much into them, but another thing I can’t help noticing in the press release is that none of the quotes from the companies submitting the specification tout federation, but simply “integration” or “sharing”. For example: “integration and interoperability” (BMC), “share data” (CA), “sharing of information” (HP), “view, track and change information” (IBM), “exchange data” (Microsoft). This more realistic assessment of what the specification does stands in contrast to the way the DMTF presents it in the press release : “this specification provides a standard way to federate management data stored in multiple different data models”. At this point, it doesn’t really provide federation and especially not across different models.

All in all, it’s as good thing for this work to be moved to a standards organization. I may join the CMDBf group at the DMTF to track it, but I don’t plan to engage very much as this area isn’t my focus anymore now that I am at Oracle. But of course everything is linked at some level in the management field.

[UPDATE on 2007/11/30: two days after posting this message I got the monthly DMTF newsletter which touches on points I raise here. So here are the relevant links. First, Mike Baskey, DMTF Chairman, shares his view on what CMDBf means for DMTF. Second, as if to respond to my rant on the opacity of the DMTF, Josh Cohen, DMTF Vice-chairman, gives an update on process improvements. Some progress indeed, but still a far cry from opening up mailing list archives so that observers can see in real time what issues are addressed and can go back in time to understand how a specific technical decision was made and what were the considerations.]

Comments Off on CMDBf now in the hands of the DMTF

Filed under CMDB, CMDB Federation, CMDBf, DMTF, Everything, IT Systems Mgmt, ITIL, Specs, Standards

November 6, 2007

Illustrative algorithm for CMDBf 1.0 Query operation

When I posted an algorithm for the server side implementation of a CMDBf Query call for version 0.95 of the specification, the interoperability testing session based on that version was over and I was pretty sure no-one but those of us who participated in that session would write an implementation of 0.95. But I published the algorithm anyway since I thought it was helpful to anyone who wanted to understand the specification in depth, even if they were not implementing it. Now that 1.o is out, there is a much higher probability of people implementing the specification, so I figured it would be worth updating the algorithm to take into account the changes from 0.95 to 1.0. So here it is.

One caveat. This algorithm assumes that the query request does not make use of the xpathExpression element because, as I have explained in my review of CMDBf 1.0, I don’t think interoperability is achievable on this feature in the current state of the specification.

As a note of caution, the previous version of the algorithm was backed by my implementation of CMDBf 0.95 for the interoperability testing, so I felt pretty confident about it. For this version of the algorithm I have not written a corresponding implementation and I have not done interoperability testing with anyone, it’s just based on my reading of the specification. The handling of depthLimit in particular is a little tricky and needs to be validated by implementation (what with creating a bunch of dummy item and relationship templates with temporary names and later going back to the original template names), please let me know if you find it flawed.

And, as previously, this is in no way an optimal implementation strategy. It is the most direct and obvious set of steps that I can come up with to implement the Query call in a way that exactly conforms to the specification. There are lots of ways to make this go faster, such as the ones I mentioned in a previous post (e.g. breaking out of loops once an instance has been removed, or not recalculating L1 and L2 over and over again for relationships in the same working set that share a source/target) plus new ones such as being smarter than my brute-force approach to handling depthLimit (in step 2).

All this said, here is the algorithm:

1) for each itemTemplate, calculate the set of all items (including relationships since they are a subclass of item) that obey the instanceIdConstraint and recordConstraint elements in the template (if present). Call this the working set for the itemTemplate.
2) for each relationshipTemplate RT that has a depthLimit element:

2.1) for i ranging from 1 to the value of maxIntermediateItems for RT:

2.1.1) create an itemTemplate that is an exact copy of the itemTemplate referenced by RT’s sourceTemplate, except that it has a new, unique temporary id (keep a record linking that new id to the id of the original source itemTemplate).
2.1.2) create an itemTemplate that is an exact copy of the itemTemplate referenced by RT’s targetTemplate, except that it has a new, unique, temporary id (keep a record linking that new id to the id of the original target itemTemplate).
2.1.3) for j ranging 1 from i:

2.1.3.1) create an itemTemplate that is an exact copy of the itemTemplate referenced by RT’s intermediateItemTemplate, except that it has a new, unique, temporary id (keep a record linking that new id to the id of the original intermediary itemTemplate).
2.1.3.2) create a relationshipTemplate that is an exact copy of RT, except that its source is the itemTemplate created in the previous iteration of the current loop (or the itemTemplate created in step 2.1.1 if j=1), its target is the itemTemplate created in the previous step and it has a new, unique, temporary id (keep a record linking that new id to RT’s id).

2.1.4) create a relationshipTemplate that is an exact copy of RT, except that its source is the last itemTemplate created in the 2.1.3 loop, its target is the itemTemplate created in 2.1.2 and it has a new, unique, temporary id (keep a record linking that new id to RT’s id).

3) for each relationshipTemplate calculate the set of all relationships that obey the instanceIdConstraint and recordConstraint elements in the template (if present). Call this the working set for the relationshipTemplate.
4) set need_to_loop = true
5) while (need_to_loop == true)

5.1) set need_to_loop = false
5.2) for each relationshipTemplate RT

5.2.1) let ITsource be the itemTemplate that is referenced as sourceTemplate by RT. Calculate the set of all items (including relationships since they are a subclass of item) that obey at least one of the instanceIdConstraint elements in ITsource (assuming there is at least one such element) and all the recordConstraint elements in ITsource. Call this the working set for ITsource.
5.2.2) let ITtarget be the itemTemplate that is referenced as targetTemplate by RT. Calculate the set of all items (including relationships since they are a subclass of item) that obey at least one of the instanceIdConstraint elements in ITtarget (assuming there is at least one such element) and all the recordConstraint elements in ITtarget. Call this the working set for ITtarget.
5.2.3) for each relationship R in the working set for RT

5.2.3.1) if the source of R is not in the working set for ITsource, then remove R from the RT working set
5.2.3.2) if the target of R is not in the working set for ITtarget, then remove R from the RT working set
5.2.3.3) if RT has a source/@minimum or a source/@maximum attribute

5.2.3.3.1) find the list L1 of all relationships in the working set for RT that have the same source as R
5.2.3.3.2) if RT has source/@minimum and the cardinality of L1 is less than this minimum then remove all relationships in L1 from the RT working set
5.2.3.3.3) if RT has source/@maximum and the cardinality of L1 is more than this maximum then remove all relationships in L1 from the RT working set

5.2.3.4) if RT has a target/@minimum or a target/@maximum attribute

5.2.3.4.1) find the list L2 of all relationships in the working set for RT that have the same target as R
5.2.3.4.2) if RT has target/@minimum and the cardinality of L2 is less than this minimum then remove all relationships in L2 from the RT working set
5.2.3.4.3) if RT has target/@maximum and the cardinality of L2 is more than this maximum then remove all relationships in L2 from the RT working set

5.3) for each itemTemplate IT:

5.3.1) let sourceRTset be the set of all relationshipTemplates that references IT as its sourceTemplate
5.3.2) let targetRTset be the set of all relationshipTemplates that references IT as its targetTemplate
5.3.3) for each item I in the IT working set

5.3.3.1) for each relationshipTemplate sourceRT in sourceRTset, if there is no relationship in the working set for sourceRT that uses I as its source, remove I from the IT working set and set need_to_loop to true
5.3.3.2) for each relationshipTemplate targetRT in targetRTset, if there is no relationship in the working set for targetRT that uses I as its source, remove I from the IT working set and set need_to_loop to true

6) process the eventual contentSelector elements and/or the @suppressFromResult attributes on the templates that have matching items/relationships in the response to remove or pair down items and relationships as requested
7) package the resulting items and relationships in a way that conforms to the CMDBf response message format (including putting each item in the <nodes> element with the appropriate @templateId attribute and putting each relationship in the <edges> element with the appropriate @templateId).
8) replace all the temporary template ids (from step 2) that appear in templateId attributes in the response with the original ids of the items and template based on the records that were kept in step 2.

Just to clarify things, what I do in step 2 is simply make explicit all the itemTemplates and relationshipTemplates that are made implicit by the depthLimit element, so that we can provide with a simpler algorithm after that assumes that all relationshipTemplate correspond to direct relationships (no intermediary). And in step 8 I hide the fact that this took place.

[UPDATED 2009/5/1: For some reason this entry is attracting a lot of comment spam, so I am disabling comments. Contact me if you’d like to comment.]

8 Comments

Filed under CMDB, CMDB Federation, CMDBf, Graph query, IT Systems Mgmt, Pseudo-algorithm, Query, Specs, Standards, Tech

October 28, 2007

Review of the CMDBf specification version 1.0

Having read the recently released CMDBf 1.0 specification over the weekend, I see several improvements since 0.95, including:

the introduction of depthLimit
the lastModified metadata element
the ability to specify more than one instanceId in a template
the ability to advertise what parts of the specification you implement
the definition of faults

But while 1.0 is more complete than 0.95, I think it makes it harder to achieve interoperability. Here are the main friction points for interop:

New role for XPath

The xpathExpression element (which replaces xpath1Selector) changes in two very important ways. First, rather than being limited to XPath 1.0, it now also allows XPath 2.0. Support for this is a lot harder to achieve for people who don’t use XML as the backend format for their data. Considering the current state of adoption of XPath 2.0 and the low level of XML complexity exposed by most CMDB models, I don’t think it was opportune to bring this into CMDBf yet. And my guess is that most implementations will stay away from this. But there is a second change, less obvious but even more problematic. XPath is not just another constraint mechanism for a CMDBf template anymore, one that returns a boolean result indicating whether the instance meets the constraint or not, as it used to be in 0.95. It is now an alternative selection and filtering mechanism that lives in parallel to all the other elements in a template (and can’t mix with them). Overall, I think this change goes too far in the direction of turning a shared agreement to exchange data in XML into an assumption that the internal data models are all based on XML. And the killer with regards to interoperability is that the specification says nothing about how the resulting node sets are serialized in the response. There may be a serialization for the XPath 2.0 model, but there is no such thing for XPath 1.0 and I don’t see in the current state of the specification how two implementations have any chance to interoperate when using this feature.

Introduction of linkDepth

As I mentioned earlier, linkDepth is a very useful addition (even though it pales in comparison to the inferencing capabilities that could have been derived from basing CMDBf on RDF). But it is also a complicated feature. The intermediateItemTemplate attribute is a good re-use of the existing plumbing, but it needs at least a detailed example. I trust that the group will generate one once they’ve caught their breath from putting out the specification.

Service capability metadata

There is a new section (#6) to provide ways to describe what CMDBf features an implementation supports. But it is a very granular representation. Basically, for every feature you can describe if you support it or not. So someone may describe that they support everything inside propertyValue, except for the “like” operator. And someone else might support all the operators but not the caseSensitive modifier. That might be ok for human consumptions, but automated scenarios rely on pre-programmed queries and that is made very hard by all the possible combinations of options. What we need is a few well-defined profiles that people implement fully. Starting of course with a profile that rules out xpathExpression.

Record metadata

This new version introduces metadata on records. While recordId and lastModified are probably well understood and interoperably usable I am a bit more dubious about whether baselineId and snapshotId are going to be interoperable across vendors based on their limited description in the specification. The nice thing is that this metadata can not only be returned but also searched on. Well, at least that’s the intent. But this goes through the recordMetadata attribute on propertyValue which, while present in the pseudo-schema, is missing in the XSD…

The contentSelector element

This new element is more flexible that the propertySubsetDirective element that it replaces. In addition to specifying what properties you want returned it also allows you to specify that you only want certain record types and/or that you only want the record(s) that were used to satisfy constraints in the template. Those are nice additions, but the way the second part is implemented (through the use of the matchedRecords attribute) seems to assume that only one record in the instance was used to match all the constraints in the template. This is not necessarily the case, an instance can be selected by having different records match the different constraints in the template as long as it has at least one matching record per constraint (line 765 says “the item satisfies all the constraints”, not “a record of the item satisfies all the constraints” and you can also see this in the example in section 4.2 where the records mentioned on lines 637 and 639 don’t have to be the same). So do you return all records that have a role in matching the template, or only those (if there is any) that matches all the constraints on their own as the text seems to imply? And if several record combinations inside an instance can be used to match the constraints in a template, do I return all of them or can I just pick any subset that matches? Also, how can I say that I want all records that established the template match, independently of their type? There doesn’t seem to be a way to do this, or is it by putting a contentSelector element with no child element and the matchedRecords attribute set to false? There won’t be much interoperability on this feature until all this is clarified.

Relationships as items

A major change between 0.95 and 1.0 is that now a relationship can match an itemTemplate. For example, if you ask for all items that were modified during the last 24 hours you will get all the items and all the relationships that meet that criteria while in the previous version you’d have to explicitly request the relationships with a relationshipTemplate if you wanted to get them too). There is a good case to be made for either view and the one that works best largely depends on your backend implementation technology (RDF, objects, SQL, CIM…). But the important thing is for the spec to be clear and on this point I think the change wasn’t made explicit enough in the query section of the specification. If Van hadn’t called my attention to this on his blog, I would have missed this important change.

Security boilerplate

There is a person at IBM (probably located in a well-stoked underground bunker in upstate NY) who has instilled the fear of god in all IBM employees (at least all those who author publicly available specifications) and forces them to include a boilerplate “security considerations” section everywhere. I have co-authored several documents with IBM employees and it never fails, even thought it doesn’t add anything useful to the specification. You should see the look of fear on the face of the IBM employees when someone else suggests doing without it. We somehow managed to sneak one such slimmer specification past the IBMers with CMDBf 0.95 but I see that this has been “corrected” in 1.0. I hope that whatever painful punishment Scott, Jacob, Andrew and Mark (or their families and pets) were subjected to in the process by the IBM security ogre wasn’t too cruel. Sure, this doesn’t really impact interoperability, but now that I don’t work for a company that makes money from ink anymore, I have even less patience for this bloating.

OK, that’s enough back seat driving for now. Hopefully the standards group that will take over the specification will address all these questions. In the context of the entire specification, these are pretty small issues and mostly easy to fix. And the CMDBf group can go on to address the hard issues of federation (including security-related issues that abound in this field if one really wants to tackle them). The current specification is a useful graph-oriented query language that is a good match for CMDB data. But it’s really just a query language (plus a simple registration system).

[UPDATE: while updating the CMDBf query algorithm, I noticed another small error: maxIntermediateItems is an attribute in the pseudo-schema but an element in the schema. Something else to fix in the next version.]

3 Comments

Filed under CMDB, CMDB Federation, CMDBf, Everything, Graph query, IT Systems Mgmt, ITIL, Query, Specs, Standards, Tech

October 25, 2007

CMDBf 1.0 specification released

The CMDBf committee has just released version 1.0 of the specification. Van Wiles has an overview of the changes between 0.95 and 1.0. I left HP soon after 0.95 was released and that’s when my participation in CMDBf ended, so Van’s summary is very useful to me. The changes he lists are not surprising and some of them already existed in draft form before 0.95 publication. I need to spend some intimate time with the specification to review the changes to the template mechanism in more details. Some of the changes have the potential to make the specification quite a bit harder to implement. This is especially the case for the introduction of “depthLimit” (but it’s probably a needed feature anyway). And the fact that relationships can now match item selectors will make things either easier or harder to implement, depending on your implementation choice (e.g. straight-to-SQL/XML or through an OO or RDF model). Congrats to the group. We should soon hear about submission for standardization.

Comments Off on CMDBf 1.0 specification released

Filed under CMDB Federation, CMDBf, Everything, IT Systems Mgmt, Query, Specs, Standards, Tech

August 3, 2007

Tutorial and pseudo-algorithm for CMDBF Query operation

[UPDATE: an updated version of the algorithm that complies to version 1.0 of the specification (and not 0.95 as in this post) is now available]

The CMDBF Query operation (section 4 of the CMDBF specification) quickly becomes very intuitive to use, but it can first look a little strange to people used to SQL-style queries, because of its graph-based nature. I hope the normative text and the examples in the spec mitigate this. But just in case, here is some additional information that doesn’t belong in the spec but can be useful. Think of it as a very first draft of a primer/tutorial about that Query interface.

The easiest way to think about this interface is to think graphically. Imagine that you’re not writing your query in XML, but instead creating it in a GUI. You want to find all Windows XP machines that are owned by someone in the marketing department. First you create a circle in the GUI that represents the machine (through a Visio-like drag-and-drop into the query composer window). You right-click on that circle and in the right-click menu you select the option called “type” and you set it to “computerSystem”. Then you right-click to select “add property constraint”. You enter “OS_Version” as the property name (if your GUI tools is any good it will present you with a list to choose from, based on the previously selected type) and “WindowsXP” as the value. Already you’ve created a query that selects all Windows XP machines. Not a bad start.

But you only want the machines that are owned by marketing people. So go ahead and create another circle to represent a person. Use similar right-click actions to set the type to “person” and to set the “department” property to “marketing”.

If you submit the query at this point, you’ll get a list of all Windows XP machines and all people in the marketing department. So, rather than reducing the result (by removing machines not owned by marketing people), you have expanded it (by adding records for the marketing people). Oops.

The next step is to create a relationship that constrains the machine to belong to someone in marketing. This is done very simply in our handy GUI tool by drawing an arrow that goes from the “person” circle to the “machine” circle. This requires that there be a relationship between the two. If we want to further ensure that this relationship is of type “owns” (and not “uses” for example), we do this by right-clicking on the arrow (like we do on circles), selecting “type” and setting its value to “owns”.

If we run the query now, we get the list of all Windows XP machines owned by marketing people. We also get the list of the marketing people who own these machines and we get the relationships between people and machines. So we now have want we wanted. But maybe a little more. Maybe we only care about the list of machines, we don’t want to retrieve all the data about the marketing people. As long as we know the machines are owned by marketing people, that’s all that we care about. We don’t need to know what specific person owns what specific machine. We could simply ignore the people and relationships in the response. Or we could enrich the query to specify that the people and relationship need not be returned (but they are still part of the query in the sense that they limit what machines get returned).We do this by right-clicking on the “person” circle, and selecting the “suppress” option. Similarly, select the “suppress” option on the relationship (the arrow) too.

This query will return a list of all Windows XP machines that are owned by someone in marketing, and nothing else.

Here is what the query could look like graphically (here I assume that the GUI tools represents the fact that the arrow and the “person” circle have the “suppress” option selected on them by turning their solid lines into dotted lines and their text into italics):

The most intuitive way to think about what happens when the query gets processed is that the program looks for all instances of the patterns described by the query. In other words, it tries to superimpose the requested graph everywhere on the graph of available data and selects all the instances where the requested graph “fits”.

What does the GUI tool do behind the scene to turn this query into the proper XML, as described by the spec?

For each circle, it creates an <itemTemplate> element. For each arrow, it creates a <relationshipTemplate> element and sets its <source> and <target> elements to the right item templates. For each constraint on a circle or arrow (i.e. when we set the type or when we set the value or a give property) it creates the appropriate selector and embeds it in the <itemTemplate> or <relationshipTemplate> that corresponds to this circle or arrow. Finally, it sets the @dropDirective attribute to “true” on all the <itemTemplate> and <relationshipTemplate> elements that corresponds to circles and arrows on which the “suppress” option was selected.

Here is what the resulting query looks like in XML:

<query xmlns="http://schemas.cmdbf.org/0-9-5/datamodel">
  <itemTemplate id="machine">
    <propertyValueSelector namespace="http://example.com/computerModel" localName="OS_Version">
      <equal>Windows XP</equal>
    </propertyValueSelector>
  <recordTypeSelector namespace="http://example.com/computerModel" localName="computerSystem"/>
  </itemTemplate>
  <itemTemplate id="person" dropDirective="true">
    <propertyValueSelector namespace="http://example.com/peopleModel" localName="department">
      <equal>marketing</equal>
    </propertyValueSelector>
    <recordTypeSelector namespace="http://example.com/peopleModel" localName="person"/>
  </itemTemplate>
  <relationshipTemplate id="administers" dropDirective="true">
    <recordTypeSelector namespace="http://example.com/computerModel" localName="owns"/>
    <source ref="person"/>
    <target ref="machine"/>
  </relationshipTemplate>
</query>

Note: like all query language, the actual query depends of course on the underlying model. In this example, I assumed that the OS version is represented as a property of the machine. More commonly, the OS will be a node of its own that has a relationship with the machine. So you’d have another circle for the OS. With a property constraint on that circle (version=”WindowsXP”) and a line representing a “runs” relationship between the machine circle and the OS circle. Similarly, “marketing” could be a node of its own that people have a relationship with, rather than just a property of each person. None of this changes the logic behind the Query operation.

Now, this is nice for the user of the query, but what about the poor developer who gets the 50-pages spec thrown on his/her desk and has 2 weeks to make sense of it and implement the server side of the query? I’ve said above that the program “tries to superimpose the requested graph everywhere on the graph of available data and selects all the instances where the requested graph fits” but that’s a lot easier to write as a sentence than to implement. So here is a pseudo-algorithm to help.

1) for each itemTemplate calculate the set of all items that obey all the selectors in the template. Call this the working set for the itemTemplate.
2) for each relationshipTemplate calculate the set of all relationships that obey all the selectors in the template. Call this the working set for the relationshipTemplate.
3) set need_to_loop = true
4) while (need_to_loop == true)

4.1) set need_to_loop = false
4.2) for each relationshipTemplate RT

4.2.1) let ITsource be the itemTemplate that is referenced as source by RT
4.2.2) let ITtarget be the itemTemplate that is referenced as target by RT
4.2.3) for each relationship R in the working set for RT

4.2.3.1) if the source of R is not in the working set for ITsource, then remove R from the RT working set
4.2.3.2) if the target of R is not in the working set for ITtarget, then remove R from the RT working set
4.2.3.3) if RT has a source/@minimum or a source/@maximum attribute

4.2.3.3.1) find the list L1 of all relationships in the working set for RT that have the same source as R
4.2.3.3.2) if RT has source/@minimum and the cardinality of L1 is less than this minimum then remove all relationships in L1 from the RT working set
4.2.3.3.3) if RT has source/@maximum and the cardinality of L1 is more than this maximum then remove all relationships in L1 from the RT working set

4.2.3.4) if RT has a target/@minimum or a target/@maximum attribute

4.2.3.4.1) find the list L2 of all relationships in the working set for RT that have the same target as R
4.2.3.4.2) if RT has target/@minimum and the cardinality of L2 is less than this minimum then remove all relationships in L2 from the RT working set
4.2.3.4.3) if RT has target/@maximum and the cardinality of L2 is more than this maximum then remove all relationships in L2 from the RT working set

4.3) for each itemTemplate IT

4.3.1) let sourceRTset be the set of all relationshipTemplates that references IT as its source
4.3.2) let targetRTset be the set of all relationshipTemplates that references IT as its target
4.3.3) for each item I in the IT working set

4.3.3.1) for each relationshipTemplate sourceRT in sourceRTset, if there is no relationship in the working set for sourceRT that uses I as its source, remove I from the IT working set and set need_to_loop to true
4.3.3.2) for each relationshipTemplate targetRT in targetRTset, if there is no relationship in the working set for targetRT that uses I as its source, remove I from the IT working set and set need_to_loop to true

5) process all directives (dropDirective or propertySubsetDirective) to remove or pair down items and relationships as requested
6) package the resulting items and relationships in a way that conforms to the CMDBF response message format (including putting each item in the <nodes> element with the appropriate @templateId attribute and putting each relationship in the <edges> element with the appropriate @templateId).

There are all kinds of optimizations possible here (like breaking out of loops once an instance has been removed, or not recalculating L1 and L2 over and over again for relationships in the same working set that share a source/target), but this is the most basic form or the algorithm. The goal is to illuminate the spec, not to provide an optimal implementation strategy.

In this post, I have focused on describing and illustrating the topological aspects of the query language. The other concepts that come into play are the Selector and the Directive mechanisms. But these are a lot more familiar to people used to SQL and I think they are sufficiently explained in the spec. So I have assumed here (in steps 1, 2 and 5 of the pseudo-algorithm) that they are well understood.

4 Comments

Filed under CMDB Federation, CMDBf, Everything, Graph query, Pseudo-algorithm, Query, Specs, Standards, Tutorial

August 2, 2007

First release of the CMDBF specification

The CMDBF (CMDB Federation) group just released a first public draft of the specification. Here is a direct link to it (PDF, 1MB). That’s a very nice achievement for a group that was a bit slow to find its pace but has been very productive since the beginning of 2007. Having the interop test drive our efforts had a lot to do with it, this is an approach to repeat the next time around.

This spec will look a lot more familiar to people used to reading WS-* specs than to people used to reading ITIL manuals. The concepts and use cases are (hopefully) consistent with ITIL, but the meat of the spec is about defining interoperable SOAP-based message exchanges that realize these use cases. The spec is about defining SOAP payloads, not IT management best practices. Please adjust your expectations accordingly and you’ll like the spec a lot more.

The most useful and important part (in my mind at least), is the definition of the Query service (section 4). This is used in many interactions. It is used by clients to query a CMDB that federates many MDRs (Management Data Repositories). It is used by the clients to go interact directly with the MDRs is they choose to. And it is used by the federating CMDB to retrieve data from the MDRs. Even in the more static scenarios, in which data is replicated from the MDRs into the CMDB (instead of true federation with no replication), the Query service is still the way for clients to access federated data from the CMDB.

So, yet another query language? Indeed. But one that natively supports concepts that are key to the kind of queries most useful for CMDB scenarios, namely relationships traversal and types. This is a topological query language. I hope the simple example in section 4.2 gives a good example of what this means.

Neither SQL nor XPath/XQuery has this topology-friendly approach (which is not to say that you can’t create useful queries on CMDB data with these query languages). On the other hand, there is one query language that is inherently relationship-oriented, that has native support for the notion of class and that has received a lot more attention, interop testing and implementation experience than our effort. One that I would have loved for us to leverage in CMDBF. It’s SPARQL. But semantic web technologies seem once again to be doomed by the perception that they are too much “out there” despite all the efforts of its proponents to make them connect with XML and other non-RDF views of the world.

Final caveat, this is a first draft. It is known to be incomplete (you’ll find text boxes that describe known gaps) and not all features in the spec were tested at the interop. We need more interop, review and development before it is robust. And most importantly, a lot of the difficult aspects of federation aren’t sufficiently addressed (reconciliation, model differences, source tracing, administrative metadata…) But it is at a point where we think it gives a good idea of how we are approaching the problem.

Equipped with this foreword, I wish you a pleasant read.

3 Comments

Filed under CMDB Federation, CMDBf, Everything, Specs, Tech

June 25, 2007

CMDBF interoperability testing (alpha edition)

Last week, a bunch of us from the CMDBF author companies got together in a room for our first interoperability testing event. It was based on a subset of the spec. As usual with these kinds of events, the first hurdle was to get the network setup right (we had a mix of test endpoints running on remote servers and on our laptops; getting all laptops to talk to one another on a local network was easy; getting them all to talk to the remote endpoints over the internet was easy too; but getting both at the same time took a bit of work).

Once this was taken care of, the interop tests went pretty smoothly. A few problems were found but they were fixed on the fly and by the end we had happy MDRs (Management Data Repositories) talking to happy CMDBs who themselves were accessed by happy client applications. All this using the CMDBF-defined query and update interfaces.

Next steps are to update the spec with the lessons from the interop and to complete it with a few additional features that we put out of scope for the interop. Stay tuned.

Comments Off on CMDBF interoperability testing (alpha edition)

Filed under CMDB Federation, CMDBf, Everything, Implementation, Specs, Standards

June 11, 2007

Standards are good for customers… right?

Standards are good for customers. They avoid vendor lock-in. They protect the customer’s investment. Demanding standards compliance is a tool customers have to defend their interests when dealing with vendors. Right?

Well, in general yes. Except when standards become tools for vendors to attempt to confuse customers.

In the recent past, I have indirectly witnessed vendors liberally using the “standard” word and making claims of compliance with (and touting the need to conform to) specifications…

that have barely been submitted for standardization (SML),
that haven’t even been published in any form (CMDBF), or
that don’t even exist as a draft (CML – no link available, and for a reason).

Doesn’t something sound fishy when the logic goes through such self-negating statements as: “standards are good for you because they give you a choice of vendor. And we are the only vendor who supports standard X so you need to buy from us.” Especially when if it was true that the vendor in question implemented standard X, then it would not be their software that I would want to buy from them but their time machine.

All this doesn’t negate the fundamental usefulness of standards. And I don’t mean to attack the three specifications listed above either. They all have a very good potential to turn out to be useful. HP is fully engaged in the creation of all three (I am personally involved in authoring them, which is generally why wind of these exaggerated vendor claims eventually get back to me).

Vendors who are used to creating proprietary environments haven’t all changed their mind. They’ve sometimes just changed their rhetoric and updated their practices to play the standards game (changing the game itself in the process, and often not for the better). Over-eagerness should always arouse suspicion.

Comments Off on Standards are good for customers… right?

Filed under Business, CMDB Federation, CMDBf, CML, Everything, SML, Standards

February 16, 2007

CMDB Federation white paper released

As reported earlier, some of movers and shakers in IT management got together last year to standardize the way to federate configuration repositories. Since then the only link available has been to a press release, which is embarrassing to say the least. Well, cmdbf.org recently came up and it is now serving a white paper that describes in more details the vision that we (the companies involved) are pursuing by this collaboration.

By linking to them from the same page, we have (by some definition) successfully federated the press release and the white paper. Way to go!

Comments Off on CMDB Federation white paper released

Filed under CMDB Federation, CMDBf, Everything, Standards

April 11, 2006

Federated CMDB, one more step towards “Google maps for IT”

In July last year I gave a short presentation at the IEEE ICWS 2005 conference in Miami in which I used an analogy with Google Maps (since then assimilated into Google Local) to explain that we needed to do a better job at federating disparate instance model repositories for management. After the conference, I wrote up this blog entry to summarize my message. I got mostly positive feedback on this, with the one caveat that people were confused by the terminology. When I told them to replace “model instance” with “configuration”, things went a lot better. I realized I was guilty of that cardinal sin in our industry, lack of buzzword compliance. So here it is: I should have called the whole thing a Federated CMDB.

Between then and now, a bunch of major players in IT management got together to address this objective. Today we announced (along with our partners BMC, Fujitsu and IBM) a collaboration to produce a specification to federate configuration data repositories. And this time we are fully buzzword-compliant, so the work is described in terms of CMDB and support for ITIL best practices. Lesson learned. And of course you can expect plenty of SOA goodness sprinkled in the spec.

Stay tuned for more specifics on this soon. Before anyone sarcastically points it out, yes, this is the second announcement that we put out in a few weeks that is not backed by publicly available work (the other one is the WS-Management/WSDM convergence roadmap). And it might not even be over quite yet. Clearly, announcements are cheap (actually not so cheap if you see the work they take) compared to doing the real work. But there is real work going on behind this.

[UPDATE: a few days after I wrote this, Google went back to using the “Google maps” name instead of “Google local”.]

1 Comment

Filed under CMDB Federation, CMDBf, Everything, Tech