SPARQL Query Generator (SQG)

The work described in this paper resulted from our involvement in the development of applications for cognitive radio networks where individual radios (“RF devices,” or “nodes”) are equipped with various kinds of capabilities such as sensing, transmitting, receiving and computing. A node may provide and request services to and from other nodes in the network. Additionally, applications may request services on nodes in the network and the network then can match the radio capabilities against the requests. In all such scenarios, matching the requests against the device capabilities need to be performed in order to derive decisions on which devices should be used to satisfy a specific request.

While the majority of the software-defined radios in use today are configured and described in languages based on XML, vendors started to claim that their reasoners are based on the semantic languages, OWL in particular. Customers who want to choose a specific reasoner are then faced with the problem—which reasoner to choose?

Testing of such reasoners would need to include their capabilities to represent communication networks and derive facts that are not explicitly represented but are derivable via the inference rules of the OWL language. This kind of testing requires (1) generation of large collections of facts describing the networks (in OWL) and (2) generation of large and versatile collections of queries (in SPARQL) for retrieving information from such representations. In such a setting, both the generation and the retrieval processes must be based on the ontologies. Since the inference depends on the axioms of OWL, the testing must ensure that the whole power of OWL inference, i.e., all the types of the OWL axioms that appear in the ontology, is used in both descriptions and queries.

We have described a description generator in [9]. In this paper, we are focusing on the query generator. We are dealing with a more general use case that is not limited to cognitive networks, but to any systems where reasoners are used to infer facts from OWL encoded descriptions, and then, SPARQL is used to query the fact base.

To ensure that the evaluation results carry a high level of credibility, it is required to use large numbers of requests of different types for matching against large pools of device descriptions.

The queries must have sufficient semantics so that the device capability matching system can precisely retrieve devices of a desired type. The collections of queries must be highly diversified to be representative of the whole tested space of the requests.

Theoretically, the problem could be resolved using real queries, or at least queries collected from real radio networks. Unfortunately, this kind of queries is not readily available due to various reasons. So the only practical solution is to use synthetic queries, instead. A wide literature search for software for this purpose has been performed. However, none of the tools and published approaches satisfy our requirements (stated in the next section). Consequently, a SPARQL query generator (SQG) program was developed taking into account the various lessons learned from the related work. The inputs to SQG are a domain ontology encoded in OWL and an OWL class selected from this ontology (we call it the “root class”) that represents the type of objects of interest to the user. In our RF domain use case, the SDR ontology [32] and the RFSystem class were used in these roles.

In this paper, SQG is described and the evaluation of its features is presented. The generation approach focuses on OWL axioms coverage and diversity coverage such that the generated queries are highly diversified and aim at matching both explicit and implicit descriptions of objects of a specific type in a domain ontology. While our main objective is to use it for generating requests for services against descriptions of RF device capabilities based on an RF domain ontology, we believe that it is also applicable to other domain ontologies. To support this expectation, the results of using SQG for generating SPARQL queries against the datasets based on five other ontologies are also provided.

The rest of this paper is structured as follows. Section 2 reviews related work on SPARQL query generation. Section 3 formalizes basic concepts need to define the SPARQL query generation process. Section 4 presents an overview of SQG, followed by its implementation described in Sect. 5. Evaluation of SQG and query sets is presented in Sect. 6. Finally, conclusions and discussion are in Sect. 7.

The literature search for methods of SPARQL query generation was guided by the following requirements that capture the needs of the use case described in the previous section. Various approaches to query generation have been developed in the past years. We classified the approaches into seven groups described below.

This section introduces some definitions needed to formalize the SPARQL query generation process. Note that all of the definitions originate from other papers. Definition 1 comes from [9]. Definitions 2 and 3 are based on [2] and [35], respectively. We adjusted these definitions to our objectives of restricting the graph patterns in the generated queries. Definitions 4 and 5 are based on [2] and [8], respectively. Our ultimate goal is to define SPARQL queries for descriptions of objects of a specific type.

Here is an explanation of the above definitions. First of all, SPARQL supports four query types—SELECT, CONSTRUCT, ASK and DESCRIBE. Their main differences are in the format of the query results. Each type defines query patterns in a WHERE clause and returns a multiset of variable bindings, an RDF graph or a Boolean value. DESCRIBE queries can also take a single URI and return an RDF graph. In our problem, all the requests are about finding objects of a specific type. Therefore, the only query type of interest to us is SELECT.

Second, DISTINCT, REDUCE, LIMIT, OFFSET and ORDER BY alter the result set which is returned by a query. The DISTINCT modifier is required to avoid duplicate matching results. The REDUCE modifier is not needed since it simply permits duplicate solutions to be removed if possible, but not mandatory. The rest of the modifiers are not required since no other operations are needed.

SQG consists of two steps: Process Ontology and Generate Queries (see Fig. 1).

Process Ontology takes three kinds of input: an OWL ontology, an RDF graph of object descriptions and a root class that represents the type of objects of interest. It constructs a Java model using the OWL API [18]. The RDF dataset is generated by the RODG program [9].

Generate Queries takes the Java model as input and generates a number of SPARQL queries for matching objects. A typical query consists of five parts: query prologue, query form, result variable, query body and result modifiers. The queries are programmatically built using Jena ARQ [4]. The generation process involves two steps. First, generate a graph pattern as the query body. The graph pattern is progressively built starting from the root class. It recursively generates subgraph patterns that include triple patterns associated with the root class and then merges the sub graph patterns in the graph pattern recursively with randomly selected operators from {AND, UNION, OPTIONAL, MINUS, FILTER NOT EXISTS, FILTER EXISTS}. The query prologue is progressively built during the graph pattern generation process. At last, a SPARQL query that combines all the parts into a single query is built.

In this section, we describe only the algorithms for query body generation. The full implementation of SQG is available online [38].

The process is invoked by a boot strap procedure represented in Algorithm 1. It invokes Algorithm 2, which recursively calls the sub-algorithms, as shown in Fig. 2.

The algorithm descriptions use the following notations:Algorithm 1 takes three kinds of input—a model M, a root class R and a vector of probabilities P. It then invokes Algorithm 2 passing to it a class expression \(C_0\) and a variable name. The algorithm returns graph pattern gp.

Example 1: As an example, a small fragment of an OWL API model of the SDR ontology (introduced in Sect. 6) is shown in Fig. 3. The model example is represented as an object diagram, where a rectangle represents an object of a specific class, and a link between two objects shows the corresponding Java model associations between the classes. RFDevice:OWLClass represents the root class. The association between this class and USRPB200:OWLClass is shown as subClass/superClass. ObjectAllValuesFrom represents a class expression that involves an objectPropertyExpression (an ObjectProperty hasProducer) and a classExpression (the Producer class). The right side of the graph can be interpreted in a similar way. In this example, USRPB200 is selected as \(C_0\) and passed to Algorithm 2.

Algorithm 2 (GGPN(M,\(C_0\),\(?v_0\),P)) implements the generation of graph patterns from the OWL named class \(C_0\). Its structure is based on the depth-first search (DFS) algorithm. Graph patterns are initialized as nil and then progressively filled and combined by traversing the model as a directed graph starting from the class \(C_0\). Initially, all OWL named classes are marked as unvisited. The algorithm first marks \(C_0\) as visited and randomly generates a class assertion triple pattern (a class assertion whose subject is a variable). Then, it traverses the restrictions of \(C_0\). The three types of restriction of \(C_0\) are anonymous class expressions \(A(C_0)\), key-value pairs \(D_{P,R}(C_0)\) and \(O_{P,R}(C_0)\). In the processing block of each type of restriction, the algorithm randomly picks exactly one restriction from class expressions/data ranges and then calls either the sub-algorithm GGPA(M,e,\(?v_0\),P) or recursively invokes itself, with appropriate parameters. A subgraph pattern is recursively built in the process of selecting the restrictions. At last, the algorithm invokes MERGE(GP,0,2,P) to combine all the three subgraph patterns in GP into one.

In order to guarantee the diversity of the query patterns, random generation of triple patterns and selection of objects are used. This is implemented by setting the probability thresholds P[] for various types of triple pattern generation or element selection. If a randomly generated value is greater than the threshold, the random selection/generation will take place. For instance, a class assertion triple pattern is included when a randomly generated value \(0 \le p \le 1\) is greater than the class assertion probability threshold P[0]. A triple pattern may be randomly replaced with another triple pattern (we term it as a relevant triple pattern of the triple pattern) depending on the probability thresholds. For instance, if an object property assertion triple pattern (\(?v_0\), p, \(?v_1\)) is considered, a relevant triple pattern (\(?v_1\), \(p'\), \(?v_0\)), where \(p'\) is an inverse property of p, may be the ultimate triple pattern to be included. The details of these procedures are not shown in the algorithms.

Example 2: Figure 4 shows the progression of SQG through the algorithms. For simplicity, the figure only includes the fragments that are traversed by the algorithms for the query body generation that was started in Example 1. Step 1 shows the generation of a class assertion triple pattern (?v1 rdf:type USRPB200) generated in line 3 of Algorithm 2. Then, Algorithm 2 invokes Algorithm 3 to generate a nested graph pattern (step 2), followed by processing key-value pairs \(O_{P,R}(C_0)\) to generate a nested graph pattern that includes a triple pattern (?v1 supportsTransmitting I1) (step 3). At last, Algorithm 4 is invoked to merge the two graph patterns with keyword OPTIONAL (step 4).

Algorithm 3 (GGPA(M,\(C_{anon}\),\(?v_0\),P)) implements sub-procedures of generation of graph patterns. Graph patterns are computed by traversing the model starting from an anonymous class expression passed as \(C_{anon}\). The result depends on the type of anonymous class expression. The algorithm covers all types of OWL 2 anonymous class expressions described in [28]. Due to the space limitation, only the processing of ObjectIntersectionOf, ObjectUnionOf and cardinality-based object property restriction (ObjectSomeValuesFrom, ObjectAllValuesFrom, ObjectMinCardinality, ObjectMaxCardinality or ObjectExactCardinality) is shown. Specifically, if \(C_{anon}\) is a ObjectIntersectionOf or ObjectUnionOf, the algorithm first initializes graph patterns GP, looks for the class expressions they operate on and then either recursively calls the algorithm itself or calls back to Algorithm 2 (GGPN(M,\(C_{0}\),\(?v_0\),P)), depending on whether they are anonymous or not. Elements of GP are progressively generated by the function calls. After all the elements are built, they are merged by calling Algorithm 4 (MERGE(GP,0,\(length(GP)-1\),P); if \(C_{anon}\) is a ObjectComplementOf, the algorithm gets the class expression it operates on and then either recursively calls the algorithm itself or calls back to Algorithm 2 (GGPN(M,\(C_{0}\),\(?v_0\),P)), depending on whether the class expression is anonymous or not; if \(C_{anon}\) is a ObjectOneOf, the algorithm terminates; if \(C_{anon}\) is a ObjectHasValue or DataHasValue, the algorithm gets the filler (an OWL individual or an OWL literal) and then generates a property assertion triple pattern accordingly; if \(C_{anon}\) is a ObjectHasSelf, the algorithm generates an object property assertion triple pattern with the same subject and object; if \(C_{anon}\) is a cardinality-based object property restriction, the algorithm gets the property p and the filler as OWL class expression \(C_{exp}\) referenced by \(C_{anon}\). If \(C_{exp}\) is anonymous, the algorithm generates a variable \(?v_1\) and calls itself. Otherwise, it randomly picks an OWL named individual \(I_0 \in I(C_{exp})\) or generates a variable \(?v_1\) and calls back to Algorithm 2 (GGPN(M,\(C_{exp}\),\(?v_1\),P)) or simply generates a variable \(?v_1\) or randomly picks a variable \(?v_1 \in V(C_1)\), depending on the probability thresholds and the visit status of \(C_1\). In any case, an object property assertion triple pattern (\(?v_0\), p, \(?v_1\)) or (\(?v_0\), p, \(I_0\)) is generated and added into gp in the end; if \(C_{anon}\) is a cardinality-based data property restriction (DataSomeValuesFrom, DataAllValuesFrom, DataMinCardinality, DataMaxCardinality or DataExactCardinality), the algorithm gets the property p and the filler as data range r referenced by \(C_{anon}\) and generates a variable \(?v_1\). Then, a data property assertion triple pattern (\(?v_0\), p, \(?v_1\)) is generated and added into gp. The algorithm may also randomly generate a filter expression with the function \(getFilterExp(r,?v_1)\) and add it into gp in the end.

Algorithm 4 (MERGE(GP,i,j,P)) merges graph patterns indexed by m in GP, where \(i \le m \le j\). The algorithm is a divide and conquer algorithm. Lines 1-2 test for the base case, where GP has just one column. Lines 3-7 handle the recursive case. First, an index k, where \(i \le k \le j - 1\), is randomly selected, and then, the problem is divided into two sub-problems. The algorithm recursively resolves each sub-problem and gets the results as \(gp_l\) and \(gp_r\). At last, \(gp_l\) and \(gp_r\) are combined using a randomly selected operator from {AND, UNION, OPTIONAL, MINUS, FILTER NOT EXISTS, FILTER EXISTS} based on the probability thresholds P.

The run time complexity of the comb() operation is constant (O(1)). So the run time complexity of the MERGE algorithm is O(n), where \(n = j-i+1\) is the number of columns in GP.

In this section, we present an evaluation of SQG with respect to a number of metrics. Since one of our objectives was to show that SQG can be used on different ontologies, we reused the same set of ontologies for evaluating RODG [9], i.e., the SDR ontology [32] developed by us, and five existing ontologies in different domains: the eDIANA ontology [12], the IoT ontology [19, 21], the Smart Appliances REFerence (SAREF) ontology [10, 36], the Univ-Bench ontology [41] and the WM30 ontology [39]. Table 2 summarizes the basic characteristics of each ontology, including the number of classes, object properties, data properties, class axioms, object property axioms and data property axioms.

For quantitative evaluation, we selected metrics related to: (1) Scalability—how does the query generation time increase with the the number of queries and object descriptions? (2) Coverage of OWL axioms—what is the percentage of OWL axiom types included in the queries? This aspect is the most important one since it addresses the main objective of developing SQG. (3) Coverage of SPARQL—what is the coverage of the SPARQL language in the generated queries?

Experimental Setup: All the experiments were run on the MacBook Pro 2016 computer. The system specification is given below:

This paper describes SQG—a generic SPARQL query generator, which is able to generate relatively large numbers of random SPARQL queries for retrieving descriptions of objects of a specific type from RDF/OWL datasets. The intent behind the development of SQG was to provide a benchmark for testing systems that rely on the inference based on the OWL semantics. Apart from applying SQG to our specific use case of generating requests for RF devices in SPARQL, we believe that it may be applicable to the application scenarios where large synthetic SPARQL queries with similar query patterns and characteristics are needed for testing systems that implement Semantic Web solutions. SQG and the generated benchmark query sets were evaluated on six ontologies with benchmark datasets in terms of the scalability/performance and the coverage of the OWL axioms and query characteristics. The evaluation results demonstrate that SQG is generic, scalable, and the generated queries are of high diversity—covering both the axioms of OWL and features of the SPaRQL language.

To the best of our knowledge, SQG is the first SPARQL query generator that is able to automatically generate random SPARQL queries for requesting descriptions of matching objects while taking into account the OWL semantics in the query formulations. However, we are not claiming that SQG supersedes other SPARQL query generation benchmarks that focus on generating loads that are known to be difficult to handle by the query engines. We submit that SQG provides features that are complementary to such benchmarks.