Consider the bib.xml document of the bookstore example from Section \ref{sec:examples:bookstore}. The following two are query terms for this database:

    
bib {
  book {
    title { "Boken Om Vikingarna" }
  }
}

      
bib {{
  book {{
    title {{ "Boken Om Vikingarna" }}
  }}
}}

Consider the bib.xml example of Section \ref{sec:examples:bookstore}. Recall that in this example the list of authors for each book uses an ordered term specification. The following two query terms show the difference between ordered and unordered term specifications in query terms:

    
bib {{
  book {{
    authors [[
      author { 
        first [ "Björn" ], 
        last [ "Ambrosiani" ]  },
      author { 
        first [ "Sven" ], 
        last [ "Nordqvist"]    }
    ]]
  }}
}}

    
bib {{
  book {{
    authors {{
      author { 
        first [ "Björn" ], 
        last [ "Ambrosiani" ]        },
      author { 
        first [ "Sven"], 
        last [ "Nordqvist"]    }
    }}
  }}
}}

The following query term matches with a text document (like the one introduced in Section \ref{sec:examples:text}), if at arbitrary depth below the root term, the data term representing the text document contains a section term with a title subterm containing the string ``Data Terms'', i.e. either a section, a subsection, a sub-subsection, etc.

report {{
 desc section {{
    title {{ "Data Terms" }},
  }}
}}

Consider in the following the student database example introduced in Section \ref{sec:examples:studentdb}. The following query term retrieves student names (variable Name) and student ids (variable MatrNr). If both exist, both are returned. If only the name exists, the evaluation does not fail (i.e. the query term still matches), but binds only the variable Name. If there is no name in the data term, the query term fails to match it.

students {{
  student {{
    name { var Name },
    optional matrnr { var MatrNr }
  }}
}}

In the student database (Section \ref{sec:examples:studentdb}), the query term given on the left hand side matches the variable Name with the student name and variable Email with the email address. The right hand side lists different substitutions that yield ground instances of the query term that match with the data term given in students.xml.

students {{
  student {{
    name  {{\varc var Name }}
    email {{\varc var Email }}
  }}
}}

Note in particular that Goofy is listed twice as the data term contains two possible email addresses that can be bound to the variable Email.

The following query terms for the bib.xml database of Section \ref{sec:examples:bookstore} illustrate the difference between variables without and with pattern restrictions.

bib {{
  book {{
    var X,
    authors {{ var AUTHOR }}
  }}
}}

bib {{
  book {{
    var X -> title {{ }},
    authors {{ var AUTHOR }}
  }}
}}

The use of the keyword var to introduce a variable is not strictly necessary. It is often possible to determine from the context whether a term is a variable or not. In particular, extensions of the Xcerpt syntax are investigated that allow to declare variables in a context block. However, using the keyword var simplifies the syntax in particular for the programmer, as it allows to easily identify variables without having to look at the context. Label variables are useful to retrieve structural information that is unknown in advance, e.g. when transforming an XML document into an HTML representation displaying the structure of the XML document (as e.g. in the implementation of the visual language visXcerpt \cite{sacha-da,visxcerpt-vldb,visxcerpt-ppswr}).

students {{
  student {{
    var X {{ "Goofy" }},
  }}
}}

Position Specification and Positional Variables

In some applications it is desirable to query subterms only at a certain position while still being able to use partial query patterns, or to query the position of subterms in the database. For example, a query to a report in XML format could select the second paragraph of all sections.

In query terms, subterms of the form position X t denote that the query term only matches with data terms that have at position X a subterm t' that is matched by t. The position specification X is either a positive number, or a negative number, or a variable:

• a positive number specifies the position of the matched subterm below its parent term, where 1 is the position of the first subterm
• a negative number specifies the position relative to the last subterm of the parent, where -1 is the position of the last subterm.
• a variable matches with a subterm with any position and binds the variable to the position of this subterm as a positive integer number.

Position specification is admissible in all kinds of term specifications, i.e. ordered and unordered as well as total and partial query terms. Note, however, that it is possible to express patterns that are contradictory and thus impossible to match, as position specifications might conflict with ordered or total term specifications (e.g. f[[position 2 a, position 1 b]] or f{position 2 a}).

Note that a term containing a subterm with position specification can never match against a data term with unordered term specification, as in such cases there is no information available about the position of elements.

<table>
  <th>
    <td>No.</td>
    <td>Title</td>
    <td>Price</td>
  </th>
  <tr>
    <td>3675</td>
    <td>Vikinga Blot</td>
    <td>5.95</td>
  </tr>
  <tr>
    <td>6743</td>
    <td>Boken Om Vikingarna</td>
    <td>22.95</td>
  </tr>
</table>

table [
  th [
    td ["No."], 
    td ["Title"], 
    td ["Price"]
  ],
  tr [
    td ["3675"], 
    td ["Vikinga Blot"], 
    td ["5.95"]
  ],
  tr [
    td ["6743"], 
    td ["Boken Om Vikingarna"], 
    td ["22.95"]
  ]
]

table {{
  td {{
    position 2 td { var Title },
    position 3 td { var Price }
  }}
}}

table {{
  th {{
    position var TPos td { "Title" },
    position var PPos td { "Price" }
  }},
  td {{
    position var TPos td { var Title },
    position var PPos td { var Price }
  }}
}}

Subterm Negation: without

Subterms of the form without t denote so-called subterm negation. Subterm negation allows to express that a data term should not contain subterms matching a certain query pattern. It is only applicable to subterms and may not be used at the root level. Furthermore, subterm negation is only reasonable in partial term specifications, and order does not have influence on the negated subterms (only on all positive subterms).

This kind of negation is useful in semistructured data, as the schema of such data often allows to omit subterms. For example, a query might ask for "all students that did not submit their homework" (i.e. all student elements that do not contain an element indicating that they submitted their homework). Note that in relational database systems, this negation is very similar to querying for NULL values.

students {{
  var S -> student {{
    without exercise {{ number { 2 } }}
  }}
}}

Subterms negated by without may contain variables, but such an occurrence can never yield variable bindings, i.e. it is not possible to retrieve all subterms that do not occur. Accordingly, all variables that occur in the scope of a without have to appear elsewhere outside the scope of a negation construct (cf. Section \ref{sec:range-restrictedness}). Nonetheless, using variables in negated subterms can be useful, as shown in the following example.

report {{
  desc var Citation -> cite { 
    attributes { ref { var Ref } }
  },
  desc bibliography {{
    without entry {{
      attributes {{ id { var Ref } }}
    }}
  }}
}}

var Citation =  cite { attributes { ref{"rdf"} } }

Subterm negation is an existential negation: As long as there exists at least one term which does not contain the negated subterm (and matches with the remainder of the pattern), all other terms are irrelevant. There might be terms that contain the negated subterm, those simply do not match. Note that although subterm negation might appear less expressive than full negation as failure, it does in fact share the same problems if it occurs in combination with the all construct introduced below.

Regular Expressions

Query terms provide advanced text processing capabilities using regular expressions (abbreviated: RE). In language theory, a regular expression is a means to define a regular language (see e.g. \cite{hopcroft-ullman}) and matches with a character sequence, if the character sequence is a word of the language defined by the regular expression. In Xcerpt, regular expressions may be used either in place of strings or in place of subterm labels, and take the form

/<regexp>/

where <regexp> is a regular expression based on the syntax defined in POSIX (Portable Operating System Interface) with some Xcerpt-specific extensions (see below). POSIX regular expressions are very widespread (they are e.g. used in the languages Perl, Python, and Java) and thus well known to many programmers.

report {{
  desc var S -> section {{
    title {{ /.*XML.*/ }}
  }}
}}

POSIX Regular Expressions

As POSIX regular expressions are very well-known, this thesis only provides a brief summary over the major constructs used for building regular expressions. The language definition is available here, and many introductory books into programming languages provide a thorough treatment of the topic.

In POSIX, an underlying character set is assumed (e.g. Unicode). Valid characters are all characters of the character set, where an ordinary (i.e. not special) character usually matches only itself, and the special character . matches all characters.

Special Characters

Special characters are not matched. The following special characters are used in POSIX regular expressions:

If a special character is to match instead of being interpreted, it has to be quoted using the prefix symbol \. For instance, \. matches the point and \+ matches the plus character.

Character Classes

Square brackets are used to define character classes, i.e. sets of characters. A character class matches with all characters that are part of the class. The following character classes are predefined by POSIX:

[:alnum:]   [:cntrl:]   [:lower:]   [:space:]
[:alpha:]   [:digit:]   [:print:]   [:upper:]
[:blank:]   [:graph:]   [:punct:]   [:xdigit:]

For example, the character class [:alnum:] contains all alphanumeric characters, [:upper:] contains all upper case characters, and [:blank:] contains all whitespace characters of the character set.

It is also possible to define new character classes by enclosing all matched characters in square brackets. The character class [abc] for instance matches with the characters a, b, and c. Character classes may contain range expressions using the hyphen character, like in [a-zA-Z] (matching all Latin lower/upper case letters), where the range is defined depending on the underlying character set (e.g. ASCII or Unicode).

Character classes are negated if the first character after the opening bracket is ^. For instance, [^-+] denotes all characters except - and +. Note the different meaning of ^ in regular expressions as negation of character classes and as beginning of line anchor, and in Xcerpt terms as reference to an identifier.

Subexpressions.

POSIX allows to specify subexpressions in regular expressions in order to retrieve specific parts from the matched text. A subexpression is enclosed in parentheses ( and ) (often also \( and \), e.g. in the search function of the editor Emacs). Subexpressions can later be referred to by their position. If subexpressions are nested, the position is determined by counting the opening parentheses.

([1-9][0-9]{3})-([01][0-9])-([0-3][0-9])

Backreferences

Backreferences are denoted by \n, where n is a single digit other than 0. A backreference matches a literal copy of whatever was matched by the corresponding n'th subexpression of the pattern. Note that matching with backreferences is NP-hard, as it is possible to encode the 3-SAT problem in a regular expression with backreferences.

(.*)-\1

a-a
go-go
wiki-wiki

Note that "regular expressions with backreferences" are (strictly speaking) not regular, they describe a subset of context free languages.

Xcerpt Extensions

In POSIX, the (substrings matched by) subexpressions are referred to by position after the matching is evaluated. This approach is well suited for imperative languages like Perl or Java, where the evaluation is sequential. For example, the following Perl program retrieves the year, month, and day from the string "2004-03-04" by referring to the positions of the subexpressions after the regular expression is matched. Subexpressions are addressed by counting opening braces from left to right.

if("2004-03-04" =~ /([1-9][0-9]{3})-([01][0-9])-([0-3][0-9])/) {
  $year = $1;
  $month = $2;
  $day = $3;
}

In Xcerpt, referring to subexpressions by position is not feasible: it is incompatible with pattern-matching as it requires a specific control flow and does not fit with Xcerpt's notion of variable binding. Instead, Xcerpt introduces variables (-> restrictions) into regular expression patterns, similar to the way variables are part of term patterns. With this extension, subexpressions can take the form

(<name>->...)

where ... denotes the regular expression pattern and <name> is the name of the variable restricted by this pattern. When the regular expression is matched against a character sequence, the variable is bound to the part of the character sequence that is matched by the subexpression. Note that this approach is similar to the extensions of regular expressions in the language Python, where a group may have the form (?P<name>...). The substring matched by this group is later accessible via the symbolic name <name>. For example, the following query term binds the year, month and day of a date string to the variables Y, M and D:

/(Y->[1-9][0-9]{3})-(M->[01][0-9])-(D->[0-3][0-9])/

Note that subexpressions of the form (...) are still possible as a means for structuring the expression, but the character sequences they matched with cannot be retrieved.

in {
  resource { "file:students.xml" },
  students {{
    student {{
      name { var Name},
      email {
        /?(var User ->[?@]+)@(var Domain ->[a-zA-Z0-9.-]+)/
      }
    }}
  }}
}