An OpenMath Content Dictionary with symbols for pattern matching of tree-like structures is presented. Furthermore, a mapping to RDF and SPARQL is introduced that allows to execute search queries against an OpenMath RDF representation. Structural search on mathematical expressions can be useful in the field of mathematical knowledge management, in diferent engineering disciplines and also in modeling and simulation environments, e.g., for refactoring of existing formulas. Searching tree-like structures is usually not possible with common text-based search engines, so specialized systems were developed in the past. One of these systems is MathWebSearch that implements formula search by using substition tree indexing [1, 2, 3]. Another system is Sewelis, a tool for guided exploration and editing of RDF graphs, that was extended with query operators for tree-like structures to enable search in mathematical expressions [4]. Both systems use some kind of pattern language to express search queries. MathWebSearch uses Content MathML as internal query language which is extended by additional tags (mq:query, mq:and, mq:or and mq:not) and attributes (mq:target, mq:generic, mq:anyorder and mq:anycount). <math xmlns="http://www.w3.org/1998/Math/MathML"> <apply><csymbol cd="calculus1">int</csymbol> <bind><csymbol cd="fns1">lambda</csymbol> <bvar><ci mq:generic="x">x</ci></bvar> <apply><csymbol cd="arith1">power</csymbol> <ci mq:generic="x">x</ci><cn type="integer">0</cn> </apply> </bind> </apply> </math>
Sewelis defines an extended Turtle [
SELECT ?e WHERE { ?e is ...math:Power(?x,2)... .
math:Integral(?e,?x) . }
Both approaches use some kind of mathematical notation and combine it with boolean, binding or more complex operators, for example, to match containment relationships. While the resulting query languages are powerful, they use proprietary extensions for MathML or SPARQL to express patterns and search operations.
OpenMath and its extension mechanism allows to define mathematical symbols for the representation of search patterns as mathematical expressions. This makes it possible to exchange patterns as normal objects with OpenMath or Strict Content MathML.
The following section introduces the newly developed OpenMath Content Dictionary that defines a basic set of operators to represent search patterns as mathematical objects.
The patterns Content Dictionary defines symbols to encode simple queries for mathematical objects with OpenMath. The symbols and their proposed textual representations (extended POPCORN syntax) are shown in Table 1. Most symbols are application symbols and can be used in the form (1, . . . , ) (1) where is the particular symbol and 1, . . . , are one or more OpenMath objects that may also recursively contain patterns. The only exceptions are the symbol any, that can be used as a constant to match an arbitrary expression, and the attribution symbol bind for binding of result values to named variables.
By using symbols of the patterns Content Dictionary, for example, the following pattern can be defined: patterns:root(patterns:descendant(
patterns:any_of(arith1:sum, arith1:product) )) This pattern finds mathematical expressions that contain sums or products at any nesting level. The rather long names of the symbols (like descendant or any_of) hinder the readability of such expressions. Therefore we propose shorthand notations as defined by Table 1 that would allow to express the pattern as:
Symbol all_of any any_of argument descendant none_of
root self_or_descendant .& ? .| ., ..+ .! .
...
variable. When used with an Openmath variable the value of bind is ignored, the variable is interpreted as placeholder and the target variable name is used for binding of result values.
bind
bind
Patterns with named placeholders as used by the examples given in the introduction can be expressed as follows: patterns:root( calculus1:int($x{patterns:bind -> 1} ->
patterns:self_or_descendant($x{patterns:bind -> 1}^2) )
) A possible short form of the previous pattern could be: .^(calculus1:int(?x -> ...(?x^2))) The term ?x is the short form of $x{patterns:bind -> 1} and represents a placeholder that matches variables with arbitrary names.
If the OpenMath objects are encoded in OpenMath-RDF then the query language SPARQL can be used to evaluate the patterns. This is similar to the approach followed by Sewelis. The transformation of the patterns to SPARQL reuses the transformation operator that translates OpenMath-XML to OpenMath-RDF. This approach is possible since SPARQL uses the Turtle syntax for graph patterns whereby OpenMath-RDF can be directly represented in SPARQL.
Table 2 shows additional rules that are necessary to support all patterns as defined in Table 1. The SPARQL representation uses extended functions of the query language like complex path expressions and filters to traverse parent-child relationsships as well as argument lists.
By using shorthands for the symbols the previous example search pattern for sums and products can be compactly represented as: .^(..+(.|(sum, product)))
This expression can be translated to SPARQL by applying the rules from Table 2. The result is the following SPARQL query:
SELECT ?result WHERE { {
?n0 (<>)? <http://www.openmath.org/cd/arith1#sum> . } UNION {
?n0 (<>)? <http://www.openmath.org/cd/arith1#product> . } ?result (math:arguments|math:symbol|...|rdf:rest)+ ?n0 .
FILTER NOT EXISTS {
[] math:arguments|math:symbol|...|rdf:rest ?result . }
} The generated query represents the alternative (.|) between the symbols sum and product by using the UNION set operator. Furthermore, path expressions are used to determine the descendants (..+) and to filter any non-root nodes .^ with the FILTER NOT EXISTS SPARQL operator. As can be seen, the OpenMath-based representation of the search pattern is considerably more compact and understandable as the equivalent SPARQL query.
Besides the unpredictable execution time for complex search patterns another limitation should be considered if OpenMath-RDF and SPARQL are used to execute search queries: SPARQL uses names (URIs or blank node identifiers) to compare nodes of an RDF graph and not their structural equality. Therefore it is necessary to preprocess the RDF data if patterns with named variables, that use the patterns:bind annotation, should be matched via SPARQL. A possible algorithm is the Universal RDF Dataset Canonicalization Algorithm 20151 that generates stable content-based identifiers for blank (anonymous) nodes of an RDF graph. After applying the algorithm blank nodes of an RDF graph have the same name if they recursively share the same properties with the same values. This allows to use a simple comparison of node names to reason about their structural equality. 1https://json-ld.github.io/rdf-dataset-canonicalization/spec/ (09.07.2021)
For verifying the functionality of the developed Content Dictionary a prototypical web application was created that allows to execute search queries on available OpenMath Content Dictionaries. A screenshot of the application is shown in Figure 1.
The upper part contains an input field for the search pattern. This pattern is parsed into an OpenMath-XML representation and then converted to SPARQL by applying the rules from Example(This represents the summation of the reciprocals of all the integers between 1 and 10 inclusive., ∑x1=01 x1) meta:Example("This represents the summation of the reciprocals of all the integers between\n 1 and 10 inclusive.", su m(interval1:integer_interval(1, 10), $x -> 1 / $x))
n Bell(n) = ∑Stirling2(n, k)
k=0 combinat1:Bell($n) = sum(interval1:integer_interval(alg1:zero, $n), $k -> combinat1:Stirling2($n, $k)) Examples SPARQL describe
XML describe
XML describe
XML Stirling1(n, m) = n∑−m −1k × (nn−− m1++kk) × (n2−nm− −mk) × Stirling2(n, m)
k=0 combinat1:Stirling1($n, $m) = sum(interval1:integer_interval(alg1:zero, $n - $m), $k -> -(alg1:one) ^ $k * binomial ($n - alg1:one + $k, $n - $m + $k) * binomial(2 * $n - $m, ($n - $m) - $k) * combinat1:Stirling2($n, $m))
A Content Dictionary to express search patterns for mathematical expressions with OpenMath was presented. This enables the exchange of such patterns in a standardized way as OpenMath objects.
Furthermore, a mapping of patterns to RDF and SPARQL was given as an option to execute search patterns against an OpenMath RDF representation. Although the scalability of this 2The RDF version of the Content Dictionaries is available at https://github.com/numerateweb/openmath-cd (29.06.2021) approach has to be investiged it is a proof of concept to use general purpose graph databases for storage and retrieval of mathematical formulas.