This paper focuses on querying semi structured data such as RDF data, using a proposed query language for the non-expert user, in the context of a lack knowledge structure. This language is inspired from the semantic regular path queries. The problem appears when the user specifies concepts that are not in the structure, as approximation approaches, operations based on query modifications and concepts hierarchies only are not able to find valuable solutions. Indeed, these approaches discard concepts that may have common meaning, therefore for a better approximation; the approach must better understand the user in order to obtain relevant answers. Starting from this, an approximation approach using a new query language, based on similarity meaning obtained from WordNet is proposed. A new similarity measure is then defined and calculated from the concepts synonyms in WordNet, the measure is then used in every step of the approach for helping to find relations between graph nodes and user concepts. The new proposed similarity can be used for enhancing the previous approximate approaches. The approach starts by constructing a graph pattern ( ) from the query and finalized by outputting a set of approximate graph patterns containing the results ranked in decreasing order of the approximation value level.
In recent years, the amount of information on the web grows increasingly and the classic information retrieval is not able to find the answer which satisfies the user queries, therefore, the semantic search may be a proposed solution for such situations. Most users have not much knowledge about the querying language in the semantic web, they are not aware of target knowledge base; so the user query does not match necessary the data structure. It is very hard and difficult to understand intend of naïve users.
In this paper we propose an approach for answering a new query language
inspired from the conjunctive regular path queries [
We consider the problem of querying the semi-structured data such RDF data which is modeled by a graph , and an ontology , . Where each node in is labeled with a constant and each edge is labeled with a label drawn from a finite set of symbols , contains nodes representing entity classes or instances or data values (values of properties), the blank nodes are not considered, the edges between the class nodes and the instance nodes is labeled by ‘type’, represents the relations between the nodes in , and .
Users specify their request by a proposed language inspired from the conjunctive regular path queries CRP which have the next format:
1 … – 1 1 1, … , • Each Yi or Zi is a variable or a constant. The variable is specified by? , we make a simple modification to the constants for specifying the choices so the user is able to specify constants which are not necessarily appearing in G and he is able to use many constants by using the symbol ‘|‘so Yi or Zi is a variable or a constant or expression (in our approach). • Regular path expressions {R1,…,Rn}, which are defined by the grammar: : å | | _ | | 1. 2 | 1|2 | , Where ε is the empty string, “a” is a label constant, “_” denotes any label and L is a label variable. • 1 …
are head variables and the result is returned in these variables.
In this paper, for helping the naïve users, we propose a new simple query language, we focus on the regular expression which has a simple format (using only the ‘.’ and the ‘|’), the query 1 is an example of the proposed language, We construct from the user query a graph patterns for finding a set of sub graphs in (approximate graph patterns) whose nodes matches the nodes in and its paths have a level of approximation to the paths in .
Example1. We assume that a user writes a query 1 for finding the publications and the authors in ‘California’ university or ‘Harvard’ university in the ‘ESWC 2012’conference: ? , ? ? , , ? , ? , _. | , |,
? , . , 2012.
Figure 1 shows a constructed from 1 , the separate points between symbols
represented by non-labeled nodes, the query paths 1 2 3 correspond to user paths 1 2 3
of 1 . The variable nodes are specified with ‘?’ to indicate that only these nodes are
shown in the answer. In our work, the answers for the query is a set of approximated
graph patterns ranked in order of decreasing the approximation level value, every one
contains nodes that correspond to the user variables, the paths in every approximate
graph pattern are an approximation of the paths in (every path in is
corresponding to a single conjuncts query [
In section 2 related works are discussed and Section 3 presents WordNet and the new proposed similarity meaning. In section 4 the approximation approach is detailed. Section 5 is dedicated to the approach implementation and experimentation, whereas the conclusion and future works are presented in section 6. 2
Many approaches, methods and query language are proposed for the search in the
semantic web search, and may be classified as follows:
1. Approaches consider structured query languages, such as: Corese [
Keyword-based approaches, such as QUICK [
In this work we are interested by using the regular path queries with simple
regular expression, this helps the naive users to use the query language as they are able to
write simple regular expression. Our approach combines the two previously cited
classes, so the naïve user queries the system using simple structure and the user
constants are seen as keywords. Many works are proposed for the approximation such as
[
WordNet [
Let _ 1 2 compared, the cardinality of _ the following measure: In this section we define a new WordNet meaning similarity, this measure is used in the process of discovering the nodes mapping from the user query and graph data. the set of common senses between 1 and 2 to be
is : ë _ | 1 2 | , we use
Let min|Sync1|, | Sync2| be the minimum cardinality between the two sets
Syn(c1) and Syn(c2) for the concept c1 and c2 respectively, thus our similarity
measure is constructed from analyzing of the next metric [
S_ |S | ,| S | Sync1 Sync2 ric is: This metric based on common senses of c1 and c2, it return 1.0 if c1 is synonym of c2 but if the set of senses for c1 (or c2) are including in the set of senses of c2 (or c1) so this metric return again 1.0, for example the concept “machine” has 8 senses and “motorcar” have 1 sense (included in the 8 sense of “machine”), utilizing this metric: 1 , so “machine” is the synonym of “motor1 , , car” but this is wrong because “machine” is the generalization of “motorcar”, so from this idea we propose the next new measure which is based on the different senses between two concepts: Let _ 2 – 1 2 : the set of different senses 1 between c1 and c2, so _ . |_ , the set of union is defined as: 1 2 | =|Sync1 Sync2 | , our met 2 (3) (4) (5) In this paper we use the next measure which takes advantage of Sim1 (common senses) and Sim2 (deferent senses): _ where, ù1 and ù2 are the widths associated to Sim1 and Sim2 respectively, ù1 0.5, ù2 0.5 by default i.e. same importance, we adjust ù1 and ù2 according the preference of the user.
Example 2.Table 1 shows values of similarity for some pair of concepts. We cannot find a significant similarity between these concepts if we use a metric based on syntax only, the similarity indicates that “house” and “mouse” are similar but this is wrong, this highlights the importance of the proposed measure as it is used to find relationships between terms of the semantic regular path queries and the nodes of the graph data.
Car Location House
Automobile Placement mouse 0.5 0.33 0.0 0.16 0.16 0.0 _ 0.33 0.245 0.0
9 9 9 We start by defining the problem that is: how to satisfy the user in case if he specifies concepts that do not exist in the graph data? This is a big difficulty, as the approximation is the solutions for finding results and approximating the user query. However, it must take into account the concept meaning, this is the goal of the new proposed query language and the meaning similarity. This helps to better understand the user and helps the discovery a set of concepts in the structure which are relevant to user concepts in order to begin the process of exploration and finding the responses for the variables. The proposed approach may be divided in three steps: 1- Discovering nodes which correspond to discovering user concepts in . 2- Finding for every query path its approximate paths in the graph data. 3- Generation of the results which are a set of approximate graph patterns with its approximation level value, these graph patterns contain the nodes results corresponding to the projection of the user variables.
The procedure is based on the following objectives:
Giving to ability to the naïve user to take advantage from the power of semantic search, in this case we let him specify his needs by writing simple regular paths. Understanding the naïve user query by finding relationships between the user paths and the knowledge base (RDF graph). Most user concepts do not appear in the structure, for this reason, we propose a new query language and a meaning similarity leading to a better understanding of the user needs on one hand and discovering the correspondences between the query concepts and the graph nodes on the other hand. The user, however, still plays an important role in the query answer paradigm.
The outputted answer must be understandable for the user and it should be simple. We make clear the procedures have been omitted, in the rest of the paper, because of pages limitation; we cannot describe the approach in detail so only the main steps are mentioned. 4.1
The mapping process is necessary to find the correspondences of the nodes in GP (variables and constants in the conjuncts query); these nodes are used for finding the set of the approximate paths in . Because the user have lack knowledge of the graph data structure so he is able to use concepts not necessarily appearing in the graph and the process of mapping is important for discovering the nodes matches these concepts using WordNet. In order to enhance the matching we use a similarity metrics based on syntax (characters strings) (like: Levenshtein, NGram, JaroWinkler) and our meaning similarity (using the WordNet ontology) for discovering the senses (the meaning) commons between the concepts.
Definition 1. Two concepts 1 , 2 are similar if _1, 2
(WordNet similarity), is predefined threshold, if _1, 2 0
test _1, 2 , the values of _, _ and
[
For finding the sets of node mapping the procedure __ returns for every node ( 1,2 i.e. the first or the last node in the query path ), the set contains the nodes in which are similar to using its label by the similarity based senses (or based syntax), in addition this procedure use a strategy for discovering another nodes in from the first and last edge in the query path . then we is defined in 4.2
In this section we introduce the notion of approximation level between two paths and describe the method for calculating its values_ , this section is for the computation of the approximate paths from , the finale answers (approximate graph patterns) are calculated in the next sub section. This calculation is started after the generation of the set of nodes mapping for every node .The procedure __ take as input a query path and outputting the set of tuples answer _ ,every tuple , , , _ containing two node : is first node in the approximate path , is the last node and _ is the value of the approximate level between and , the sets of tuples answer are used for constructing the approximate graph patterns for .
We consider the next points in the calculation process of _ : •
The number of edges in similar to the edges in (similarity ≠ 1), each similar edge in is a non-direct substitution for its corresponding edge in so we added the value of substitution to _ .
The number of additional edges in (_ ), not appearing in , each additional edge in is an insertion.
We also take into account the two values: similarity value between the first node in and the first in , similarity value between the last node in and the last in .
The order of edges in the query path for respecting the preference of the user. 0.90, 2 is:
Our approach considers common and similar edges, therefore common edges are not associated to a value of ‘0’ but ‘1’, as well as the similarity values for similar edges. Before starting the process of finding the approximate local answer, the procedure __ generates the set of all paths from the two sets of nodes mapping and 2.
Definition 2. Let a path in , a query path in , is an approximate path for if the value of the approximation level between and is higher than _ ( predefined threshold of approximation), _ 0,1 .
The procedure __ use the similarity obtained between two nodes and , , 2 .If is labeled with more than one term by the symbol ’|‘ so all terms are compared to the label of and only one value of similarity is returned i.e. the value.
Example 3. Figure 2 shows the computation of the approximation level _ for the paths and ’ for the query path . For : the first node is labeled with the variable ‘?pub’ and has the set of nodes mapping = {publication, pub1, pub2}, the last node is labeled with constant ‘ESWC2012’ and has the set of nodes mapping = {ESWC2012, ISWC2012}.The similar edges by discontinued line, additional edges by double line, first and last nodes by the dark circle; the values of similarity between edges and nodes are in italic, ). The common edges are represented by single continued line. In the path , number of similar or common edges is 2 (with two values of similarity: 0.95, 1), 1 ? , 2 2012, 2012 1 , the approximate level associated with (7) (8) (9) 1 ? , 0.70 , 2 so the approximate level associated with is : The tuple answer corresponding to is: 2, 2012, , 0,97 .
In the path there is one additional edge the (the edge type) so _ 1 and, number of similar or common edges is 2 (with two values of similarity: 0.95, 1), 2012, 2012 0.20 , _ than .
The tuple answer corresponding to is: , 2012, , 0,64 . for is greater than _ for so the path have a good approximation ∑ . .
1 1 1 . In this section we describe how the final answers (Approximate graph patterns) are computed from the approximate paths discovered in the previous step, The final answers for the approximation is returned in form of tuples and every tuple represented by 1, 2, … . , , _ , __ , where to ꌔ are the nodes corresponding to the nodes variable in (the nodes answers corresponding to the variables in the user query). _ is the approximate graph pattern constructed from the approximate paths returned in _ and __ is the approximation level between and i.e. the mean of the values _ of the approximate paths used for the construction of _ .
In [
For computing the final answer we must generate the set of tuples answer _ for every path , exploring the paths in every tuple and combining same paths for the generation of the graph patterns answer .
Definition 3. Let a graph pattern constructed from a regular conjunctive query , Let a graph pattern . is an approximate graph pattern for , if the value of approximate level __ between and is higher than __ (predefined threshold of approximation for ), __ 0,1 .
The procedure _ is called with the set _ and its first tuple. The procedure _ explores all tuples in any _ to generate all approximate graph patterns, added them in the final set _ with its nodes variables and its approximation level. For the process of ranking, the value __ is used to rank the tuples in _ , the tuples are outputted ranked in a decreasing order. 5
Our approach is implemented in Java and Jena API, we use JAWS (Java API For WordNet Searching) for the implementation of the proposed meaning similarity. The RDF data set used is a sub set from the SwetoDblp ontology which is large size ontology focused on bibliography data of Computer Science publications where the main data source is DBLP, it has 4 millions of triples. The used subset contains a collection of books and its book chapters. For making the execution faster, an offline phase which contains: RDF triples normalization, (getting triples that are closely to the natural language), building 2 indexes, is computed in order to allow quick finding of the approximate paths. The thresholds , _, __ are automatically initialized and updated according the query structure, this update allows the reduction of the found answers number.
For experimentation purposes and because our query language is inspired from the conjunctive path queries for helping the naïve (non-expert) users, a query benchmark is created. The benchmark contains a set of queries, with different intends that are executed over the RDF subset. For every query, from the subset; we computed, manually, the set of the relevant solutions (RS) for evaluating Precision and Recall: RS RS RS (10) (11)
In comparison with SPARQL, our work can be used by a non-expert users and it allows specifying a query paths between variables and constants for a better understanding of the user intend. It is difficult for the naïve user to use SPARQL efficiently because its complexes structure. Table 2 includes some queries, used for the evaluation whereas Figure 4 shows the precision and recall for some queries, proving the effectiveness of the approach.
0,5 1 0 1 2 3 4 5
6 5 6 5 1.0
In this paper a novel approach for query approximation based on meaning similarity from WordNet is proposed, using a proposed query language inspired from the conjuncts queries. Using this technique, the naive users are able to write simple queries that not necessarily match the data structure. Our approach can be used as an extension to other approaches for a better understanding of the user query and obtaining results that satisfies the user’s needs. It has been shown that the answers are a set of graph patterns ranked following the approximation level decreasing order. The work, is not considering only RDF graph but it can be seen as a general approach which may be applied to any semi-structured data that is modeled as graph, Future work will consist in applying the proposed approach to specific domains such as geographic, medical, biologic and bibliography, using query interface and building new indexes for scaling a huge number of triples.