MINDS - Maths INsiDe SPARQL

A translator of mathematical formulas into SPARQL bindings


General Info.

MINDS is a tool which is able to translate mathematical expressions into SPARQL 1.1 bindings. In a nutshell, it provides a python script which is able to parse mathematical formulas and then translates recursively the discovered patterns into SPARQL compliant sequences.

The translator has been currently tested with python version 3.6.9. In addition, it requires the use of external scripts (which are all embedded locally inside this repository) for specific tasks:

How-To?

Practically, MINDS is an external software which can be run when designing SPARQL queries. It is developed in Python and its core currently represents about 500 lines of code. Technically, the given formula is parsed using a dedicated implementation of the popular Lex and Yacc tools for Python named PLY. Then, once the formula is split into tokens, the translating rules are applied recursively to generate the final result. For instance, 2020-?Y is translated into: 

#math2sparql > 2020-?Y
BIND ( ( FLOOR((2020-xsd:double(?Y))*100)/100 ) AS ?result )

Even for such a simple formula, the bindin already implies specifities. First, the binding specifies that \texttt{?Y} should be considered as a double using the SPARQL standardized syntax using the xsd prefix which makes the links with XML; and second, it truncates the result to keep only two digits of precision with the FLOOR keyword of the language. Actually, this precision parameter can be set by the user: 

#math2sparql > precision = 5
#math2sparql > 2020-?Y
BIND ( ( FLOOR((2020-xsd:double(?Y))*100000)/100000 ) AS ?result )

Therefore, MINDS is still relevant to handle even simple expressions that are cumbersome to express in SPARQL such as a square Euclidean distance: 

#math2sparql > (?x1-?x2)**2 + (?y1-?y2)**2
BIND(
 (
  FLOOR(
   (
    (1*(xsd:double(?x1)-xsd:double(?x2))*(xsd:double(?x1)-xsd:double(?x2)))+
    (1*(xsd:double(?y1)-xsd:double(?y2))*(xsd:double(?y1)-xsd:double(?y2)))
   )*100
  )/100
 ) AS ?result
)

Moreover, our solution also provides several translation rules to deal with mathematical functions e.g. trigonometric functions and even with functions of multiple variables e.g. atan2. Nonetheless, these additional functions are not part of the standard and have to be expressed only using allowed SPARQL operators: MINDS is then able to compute approximations to translate into bindings these functions. Indeed, it uses when necessary a series decomposition and technically a new binding is generated for each series so that the query evaluator might be able to store the sub-result. For instance, considering x**2 + exp(y+3z) which involved the computation of the exponential of a linear expression, MINDS returns: 

#math2sparql > ?X**2 + exp (?Y + 3 * ?Z)
BIND ((0+(1)/1.0                              # $1$
  +(1*(xsd:double(?Y)+3*xsd:double(?Z)))/1.0  # y+3z
  +(1*(xsd:double(?Y)+3*xsd:double(?Z))
     *(xsd:double(?Y)+3*xsd:double(?Z)))/2.0  # (y+3z)^2/(2!)
  +(1*(xsd:double(?Y)+3*xsd:double(?Z))
     *(xsd:double(?Y)+3*xsd:double(?Z))
     *(xsd:double(?Y)+3*xsd:double(?Z)))/6.0  # (y+3z)^3/(3!)
  +(1*(xsd:double(?Y)+3*xsd:double(?Z))
     *(xsd:double(?Y)+3*xsd:double(?Z))
     *(xsd:double(?Y)+3*xsd:double(?Z))
     *(xsd:double(?Y)+3*xsd:double(?Z)))/24.0 # (y+3z)^4/(4!)
)AS ?sub1)
BIND ( ( FLOOR(( 
    (1*xsd:double(?X)*xsd:double(?X)) +?sub1  # x**2 + sub_1
)*100)/100 ) AS ?result )

As expected, MINDS automatically converts the exponential part into an approximation using the classic series of the exponential; in this case only the first five terms of the series where considered. Moreover, it is also important to mention that MINDS allows query designers to choose as a parameter this number of terms, for example: 

#math2sparql > terms = 7

Moreover, it is able to understand any kind of combination using its recognized keywords and it generates recursively the sub-bindings when necessary.

Technical Details

We describe below the grammar which is syntaxically understood by MINDS. In particular, our translator is able to deal with the four basic operators of SPARQL (i.e. + - * /) extended with the power operator (** in MINDS) while respecting conventional priorities. Moreover, our solution also provides several translation rules to deal with mathematical functions e.g. trigonometric functions and even with functions of multiple variables e.g. atan2. 

Expression = Expression BinOp Expression
           | Expression ** [:digit:]
           | LeftOp Expression
           | BiParamOp Expression , Expression
           | ( Expression )
           | ?[:Alphanum:]
           | [:digit:].[:digit:]
     BinOp = + | - | * | /
    LeftOp = ln  | exp | sqrt
           | sin | cos | atan | tan
           | -
 BiParamOp = atan2

Practical Examples

We present here several practical queries using popular opened SPARQL endpoints. Actually, since widely used SPARQL endpoints are based on famous engines (e.g. Virtuoso or JenaFuseki), we consider the possibility of directly demonstrate the power and the accuracy of MINDS approach using their own interfaces. Indeed, the idea here is to evaluate mathematical formulas for several values using (when possible) the provided built-in functions of these evaluators and compare the results with various MINDS approximations i.e. when series are involved various number of terms are presented.

Practically, to compare various SPARQL engines, we consider these public SPARQL endpoints:

The considered mathematical formulas are the following:

  1. A basic addition ?x + 4. Try with [DBpedia][FactForge][ZBW Labs].
  2. An addition between two variables ?x + ?y. Try with [DBpedia][FactForge][ZBW Labs].
  3. A power function ?x**4. Try with [DBpedia][FactForge][ZBW Labs].
  4. A natural logarithm ln(?x). Try with [DBpedia][FactForge][ZBW Labs].

Team

Minds has been developed by the ADAPT Centre from the Trinity College Dublin, the Smart Data Analytics group from the Univeristy of Bonn and the Fraunhofer IAIS.