Balisage Paper: Extending XQuery with pattern matching over XML, HTML and JSON, and its usage for data mining

Basic node matching

Due to the intuitiveness goal the pattern itself has to be a well-formed XML document (resp. fragment). We can therefore define the basic "matching" as recursive relation between a node of the pattern and a node of the input as follows:

An exact definition for "matching string values" is given below. The property "in order" of the last point means: if a child C of E matches a descendant X of F and another child D of E matches a descendant Y of F, C precedes D in the pattern if and only if X precedes Y in the document.

Trivial examples are the pattern <foo/> matching an identical input document <foo/> or a text node pattern foo matching an identical text node foo. A more meaningful example is the pattern

<element foo="bar">cat<meow/></element>

<element foo="bar">cat<meow/></element>

<element foo="bar" att="value"><p>cat<call><meow loudness="60 dB"/></call></p></element>

<element>cat<meow/></element>

<element foo="bar" xmlns="elsewhere">cat<meow/></element>

<element foo="bar"><meow/>cat</element>

We have not considered a syntax to match comment or processing-instruction nodes, since such nodes rarely contain data that should be returned by a query and cannot contain a selector expression (see below) as a child to select this data. Also the most natural way to match a comment node would be to include an <!-- .. --> XML comment node in the pattern, which is problematic in our application, because we use standalone patterns outside of XQuery, where we prefer to use XML comments as actual comments that are ignored by the matching process. There is also no syntax to match document nodes, since it is always possible to match the root node of the document instead.

That a child in the pattern is allowed to match any descendant in the input, not only another child, follows the principle of ignoring additional data to keep the pattern minimal.

Requiring that the descendants have to be in the same order as the children, instead accepting any order, has a few benefits. First, it follows the idea of patterns as XML regular expressions, which also match their letters ordered. Second, XQuery itself is good at selecting unordered elements, but very difficult [Fischer2010] to use to select ordered elements^[2], so the combination of XPath and patterns provides a simple and powerful solution for both cases. Third, the advanced pattern syntax contains natural, unrelated features that can directly be used for unordered matching. It is doubtful that unordered matching could be used for ordered matching in such a way.

The conditions for text node matching could be relaxed to accept any node that has a matching string value, not just other text nodes. This might be useful, if the input data could sometimes contain markups like <em> within the text and sometimes not. However, we have not seen such a use case, and therefore have implemented the faster way to match text nodes only to text nodes.

String values are matched against a string using one of six different modes: eq, matches, starts-with, ends-with, contains and list-contains. eq checks for an exact match, like the eq operator. list-contains treats the string value as space separated list (e.g. like the class attribute of HTML elements) and matches, if the value of the pattern occurs in that list. The other modes match, if the call to the corresponding XQuery function, e.g. fn:starts-with($value, $pattern), returns true. Additionally the matching can be case-sensitive or case-insensitive, in latter case, the values are first converted to lowercase resp. the i flag is passed to fn:matches.

Which mode is chosen depends on the node whose string value is matched and the local settings. Due to legacy reasons, the default modes of our implementation are starts-with for text nodes, list-contains for class-attributes and eq for all other attributes^[3]. These modes can be changed within a pattern, similarly to the options described below.

There is no difference between matching a pattern to an XML document and matching it against a HTML document, except that node names are compared case sensitive for XML and case insensitive for HTML.

Selecting data

So far we have only described how a pattern can be used to test if an input document has a certain structure. To become a real replacement for standard XPath selectors, we need a way to select specific data from the matches in the input document. In regular expressions such selecting can be done with capture groups, an idea we need to transfer to the pattern syntax.

For this we allow the embedding of arbitrary XQuery expressions which will be evaluated in the context of local matches and whose return values become the return values of the pattern matching. So in case someone needs a query that does not just copy the matched data from the input document, but needs to perform certain calculations with the data, he can do it with all the power of XQuery.

We have decided to allow the following ways to embed a query in a pattern:

A selector expression is evaluated with the context item . set to the node matched by the parent node of the selector expression (more precisely the parent node of the {} text node or the parent node of the <t:s/> node containing the query). This definition is well-defined, since as so far described every node of the pattern has exactly one corresponding match in the data, once the matching has succeeded. The results of all evaluated selector expressions are returned as result of the pattern matching.

With this definition we can for example already write

<a><b>{.}</b></a>

<a><b>foo<br/>bar</b></a>

<a><b><t:s>.</t:s></b></a>

<a><b><template:s>.</template:s></b></a>

An example for the attribute variant is

<a href="{.}"/>

<html>Some text<p><a href="http://balisage.net/">title</a></p></html>

A combined example is the pattern

<a href="{.}">{concat("=> ", .)}</a>

Someone who is familiar with XQuery's handling of sequences might now wonder what happens when a pattern has multiple selector expressions that all return sequences. Does the pattern return multiple sequences? Is that even possible? Does it return a single sequence of all sequences flattened together?

We prefer former case, because it makes it possible to combine multiple patterns to a single one, regardless of the results of the combined patterns. However, multiple sequences cannot really be handled with standard XQuery data types, so we have decided to extend the XQuery syntax to create some kind of named return values.

Thus we have added variable assignments $variable := expression which evaluate the expression on the right hand side and assign it to a global variable on the left hand side. The priority of the := operator is set to be lower than the priority of every existing operator. More formally, we have introduced these extensions to the XQuery EBNF:

ExprSingle         ::= FLWORExpr | QuantifiedExpr | SwitchExpr | TypeswitchExpr | IfExpr | TryCatchExpr | VarAssignmentExpr
VarAssignmentExpr  ::= (VarRef ":=" )* OrExpr
VarRef             ::= "$" VarName   

This leaves the question, what happens, when there are multiple assignments to the same variable. We will later see that in loops every selector expression is evaluated multiple times, so the most reasonable way is to return two different variables with the same name. Although in most of the XQuery syntax extension this is not possible, we prefer to do it, whenever possible. So e.g. {$x := (1,2), $x := (3,4)} also returns two different sequences. This is easier to understand, when the variable assignments are not considered as creating actual variables, but as creating a name+value pair (like a map with one element) and adding it to a sequence. Since the pairs are not sequences themselves, they are not flattened^[6].

However, always writing {$var := expr} would be cumbersome, especially after seeing the {.} examples above. So we have added two abbreviations^[7]:

Another example is

<root><a>{$a}</a><b>{$b}</b></root>

let $a := exactly-one(((//root)[1]//a)[1]),  
    $b := exactly-one(($a/following::b)[1] intersect (//root)[1]//b)
return ...

So in the end the matching process either raises a matching error or returns a list of variable assignments

$var1 := value1
$var2 := value2
... 

Advanced patterns

The previous sections have explained the basic matching of individual elements, in which each node of the pattern is matched to exactly one node in the input data. But in practical applications it is necessary to return data that does not have a 1-1 relationship with the query itself. For this the patterns have various syntaxes which are described here:

<a>{$var}<b/></a>+

<root> <a><b>1</b></a> <a>2</a> <a><b>3</b></a></root>

$var := <a><b>1</b></a>
$var := <a><b>3</b></a>

<t:meta [text-matching="eq|matches|starts-with|ends-with|contains|list-contains"] 
        [text-case-sensitive="true|false"] 
        [attribute-matching="eq|matches|starts-with|ends-with|contains|list-contains"] 
        [attribute-case-sensitive="true|false"] 
        />

<t:meta-attribute 
        name="..."
        [matching="eq|matches|starts-with|ends-with|contains|list-contains"] 
        [case-sensitive="true|false"] />

Matching JSONiq

After having specified a pattern syntax for XML data, it appears reasonable to extend it to other data storage formats, like JSON. Recently a JSON-query language called JSONiq [JSONiq] was announced as extension to XQuery, which we have implemented and plan to extend with pattern matching.

To perform pattern matching on JSONiq types, we need to define the matching process for all new types added by JSONiq: null, objects and arrays^[12]. As well as for the standard atomic XQuery types derived from xs:anyAtomicType, because the previous sections only defined the matching for nodes.

A small problem is that none of the JSONiq types support namespaces, so we cannot do advanced matching with a t: prefix, like in the XML case, not even to include selector expressions. However, the important JSONiq types, arrays and objects, can contain XML nodes, so we can wrap the selector expressions in <t:s/>-elements and include them like that in the JSONiq item.

An example of a pattern according to above definitions is

{"a": [1,2,3], "b": null, "c": <t:s>{.}</t:s>}

{"a": [1,2,3], "b": null, "c": "foobar"}

{"a": [1,"u",2,"v",3], "b": null, "c": [7,8,9], "d": 17}

But it matches neither

{"a": [1,2,3], "b": [4,5], "c": "xyz"}

{"a": [1,2,3], "c": "foobar"}

Since writing <t:s/> is extremely cumbersome in a JSONiq pattern, it might be beneficial to allow abbreviations like {"c": .}, {"c": $result} or {"c": $result := .} in an implementation, in which the <t:s> is omitted. This syntax is mostly unambiguous, however it cannot be evaluated and stored as JSONiq type. Therefore, such an implementation must be able to partially evaluate JSONiq types, keeping it in AST form or serializing the XQuery-AST back to a reparsable query wrapped in <t:s>. Another alternative might be to use inline functions instead <t:s>, e.g function(){$result := .} replacing <t:s>$result := . </t:s>, in which case no serialization of XQuery expressions is needed. But we will not consider such extensions in the remaining paper.

As function, without syntax modification

Since every pattern is a valid XML element (or JSONiq item), it can be represented by valid values in the XQuery type schema, and it is possible to write a matching function that takes a pattern and input data as arguments and performs the matching in standard XQuery (or JSONiq). Such a function is useful to perform pattern matching in existing XQuery implementations without having to write a new implementation, and to match with dynamically constructed patterns that are not hardcoded in the query.

To use the full power of selector expressions within a pattern, the underlying implementation has to support some kind of eval function to evaluate an XQuery given as string. And of course, only the right-hand-side of := assignment can be passed to the eval-function and the variable names have to be tracked separately.

The type declaration of our matching function is:^[14]

pxp:match($pattern as item(), $data as item()*) as item()*

The first argument is the pattern that should be matched against every item in the $data sequence, thereby creating multiple assignment streams which are concatenated. Since $pattern is an ordinary value, the {...} selector expressions have to be encoded as {{...}}, if the pattern is created within the query by an element constructor.

Principally the function should return the final assignment stream, but an assignment stream is not a valid XDM instance. So we wrap the result in an XQuery map which maps variable names to a sequence of values and which can be read like a function call. For example the map $map := {"foo": "bar", "x": ("y", "z")} contains two keys which can be accessed with $map("foo") = "bar" and $map("x") = ("y", "z"). In XQuery 3.0 such a map can be implemented as an anonymous function that returns a certain value if called with the corresponding key. A theoretical alternative to a map is to wrap the data in an XML element, however, that would destroy information like the parents of the returned items^[15].

Since sequences cannot nest, assignments of sequences to variables are flattened in the returned sequence. e.g. the assignment stream $a = (1, 2), $a = 3, $a = 4 becomes a single sequence in the map {"a": (1,2,3,4)}. If the only assigment is to the default variable, we do not wrap it in a map and return the value directly.

For example

pxp:match(<root><foo>{{.}}</foo>+</root>, <root><foo>1</foo><foo>2</foo></root>)

. = <foo>1</foo>
. = <foo>2</foo>

(<foo>1</foo>, <foo>2</foo>)

Another example with variables is

pxp:match(<root attrib="{{$attrib}}"><foo>{{$var}}</foo>+</root>, <root attrib="ABC"><foo>1</foo><foo>2</foo></root>)

$attrib = "ABC"
$var = <foo>1</foo>
$var = <foo>2</foo>

{"attrib": "ABC", "var": (<foo>1</foo>, <foo>2</foo>) }

Extending Typeswitch-Expressions

XQuery has two different kinds of "switch" expression, the switch expression to test if a value is equal to one of many cases and the typeswitch expression to test if a value has the same type as one of the cases. It is not clear which "switch" expression we should extend, if we want to create the most natural syntax. On the one hand typeswitch is often used to test if an element has a certain structure (in combination with an XML schema type), the same purpose a pattern has, on the other hand a pattern does not do any type checking and instead only cares about the value (like switch or deep-equal). In the end we have decided to extend the typeswitch expression, since there a pattern can be given in a case clause, because a direct element constructor is not allowed within a typeswitch case in standard XQuery, while it is allowed to use a direct element constructor in a switch case (denoting the atomization of the constructed element and comparing it to the atomized input of the switch expression). The formal grammar of this new typeswitch-expression with patterns in the case clauses is then:

TypeswitchExpr 	   ::=  "typeswitch" "(" Expr ")" CaseClause+ "default" ("$" VarName)? "return" ExprSingle
CaseClause 	   ::=   "case" CaseClauseOperand "return" ExprSingle
CaseClauseOperand  ::=  ("$" VarName "as")? SequenceTypeUnion | PatternExpr

A pattern given in a case clause is not evaluated before the matching. So writing <x>{$y}</x> is sufficient for a pattern that assigns <x/> to $y and it does not have to be encoded as <x>{{$y}}</x>. So the variables that could be created by the pattern are statically known, and can be added to the static context of the expression in the corresponding return clause.

We define PatternExpr to be either an XML pattern with an optional loop marker (e.g. +) or a JSONiq constructor:

LoopIndicator   := OccurrenceIndicator | "{" Digits "}" | "{" Digits "," Digits "}" 
PatternExpr     := DirectConstructor LoopIndicator? | ObjectConstructor | ArrayConstructor 

This syntactical definition is broader than the semantically allowed values (e.g. function calls would not be allowed), hence some expressions are rejected during evaluation.

The typeswitch expression is then evaluated as follows:

All case clauses are processed in order.

So for example, either

typeswitch (<y>123</y>) 
  case <x>{$data}</x> return "The x-data is " || $data
  case <y>{$data}</y> return "The y-data is " || $data
  default return "foo"

typeswitch (<y>123</y>) 
  case <x>{.}</x> return "The x-data is " || .
  case <y>{.}</y> return "The y-data is " || .
  default return "foo"

If multiple values have been added to a single variable, like in <x>{$var}</x>+ they are all flattened to a variable containing a sequence. However, if the assignment was to the context item, an exception is thrown, since . cannot be a sequence.

So we can use the following example to count all links on a webpage:

typeswitch ($inputdata) 
  case <a>{$a}</a>+ return "There are " || count($a) || " links on the webpage"
  case <html/> return "There are no links on the webpage"
  default return "Invalid input"

Extending Flowers

Before we can extend the flower expressions, we need to extend the tuple stream, so it behaves more like an assignment stream. In XQuery implementations this stream assigns certain values to certain variables. Since our patterns also allow assignments to a default variable with {.} which is then mapped to the context item ., the tuple stream has to be able to not only store normal variables, but also this default variable. We will write such assignments

(. = 1)
(. = 2)

We then could write for . in $sequence return expression ... meaning the same as $sequence ! expression ... or let . := $value return expression meaning the same as exactly-one($value) ! expression ... in a query^[16].

MatchLetClause         ::=    	"let" PatternLetBinding ("," PatternLetBinding)*      
LetBinding             ::=    	PatternExpr ":=" ExprSingle

let <a>{.}</a> := <root><a>123</a></root> return .

(. = <a>123</a>)

MatchForClause         ::=    	"for" PatternForBinding ("," PatternForBinding)*
PatternForBinding      ::=    	PatternExpr "in" ExprSingle

for <a>{.}</a>+ in <root><a>1</a><a>2</a><a>3</a></root> return .

(. = <a>1</a>)
(. = <a>2</a>)
(. = <a>3</a>)

for  <html><h2>Title A</h2><p>{.}</p>+<h2>Title B</h2></html> in $input-data return .

for <root><a>{$a}</a><b>{$b}</b><a>{$a := (., .)}</a></root> in <root><a>1</a><b>2</b><a>3</a></root> return .

($a = <a>1</a>,             $b = ()),
($a = (),                   $b = <b>2</b>)
($a = (<a>3</a>, <a>3</a>), $b = ())