Path queries for tree-structured data

Question

Can anyone suggest documentation or tutorials for developing path queries and indices for (XML-like) tree-structured data?

Suppose data is organized hierarchically in key->value pairs, eg:

In[220]:= data = {row1 -> {key1 -> value1, key2 -> value2}, 
                  row2 -> {key1 -> value3, key2 -> value4}}

Out[220]= {row1 -> {key1 -> value1, key2 -> value2}, 
           row2 -> {key1 -> value3, key2 -> value4}}

In[221]:= row1 /. data

Out[221]= {key1 -> value1, key2 -> value2}

In[222]:= key2 /. (row1 /. data)

Out[222]= value2

This is a primitive form of tree-structured data that enables building up basic path queries out of Rule and ReplaceAll. However, it's desirable to also have wildcard functionality (e.g. like All) and range-like queries (e.g. like Span), but again where query parameters are named entities rather than Position expressions as in more common in relational data structures.

Answer 1

This is not really a full answer, but it may be a start. If you want something like a path specification with wildcards, spans and such, then you are actually very close to general pattern matching, and you might want such functionality anyway, so why not just start out with this? Replace and Replace All just extract components of this structure type, so they aren't ideal for doing the path queries.

Lets define a test structure:

data = {
  row1 -> {key1 -> 1, key2 -> value2}, 
  row2 -> {key1 -> 2, key2 -> value4}, 
  row2 -> {key1 -> 3, key2 -> value4}
};

Then to take the element identified by the symbolname row1, we do:

 Cases[data, HoldPattern[row1 -> _],1]

To do a wildcard search we do

 Cases[data, HoldPattern[_ -> _],1]

To do a range search, we need to carry out a check on the matches and only take those in range, so we take:

 Cases[data, HoldPattern[_ -> a_] /; (key1 /. a) < 3]

Similarly you can carry out arbitrary checks on the elements of the pattern you are looking for, and do arbitrary depth searches and other nice things. And if you need to manipulate the data structure, you can simply use positions to get the point to edit.

editAt = First@Position[data, HoldPattern[_ -> a_] /; ((key1 /. a) == 2), 1]
data[[Sequence @@ editAt]] = {key1 -> 22, key2 -> value4}