Multi-Query Optimization in RDF Q/A System

Abstract

In this paper, we present an optimization to answer a question with multiple queries by detecting all common subqueries of that question. Moreover, we apply mutual information in reducing ambiguity of queries of a question to improve the quality of common subqueries. Finally, to improve the accuracy of SPARQL query generated, we evaluate the semantic importance of each word in a question via TF-IDF during the generating queries process. Experiments show that our proposal ourperforms those single query execution.

Introduction

Overview of Our Approach

Mutual Information Disambiguation Consider a question \Which movies are directed by Paul Anderson? ". When we do phrase linking to the word \Paul Anderson", we may see that the RDF dataset contains a large number of entities about the word \Paul Anderson".

⟨Paul Anderson⟩ and ⟨Paul W S Anderson⟩ may be directors, but ⟨Paul S Anderson⟩ is a teacher. According to the semantics of question, we can actually know that although there are three \Paul Anderson" in RDF dataset, Movierelated ⟨Paul Anderson⟩ and ⟨Paul W. S. Anderson⟩ are what we really need. Hence, we can delete ⟨Paul S Anderson⟩.

The above example illustrates the intuition of our approach, we can deal with ambiguity by counting the number of predicates between entities in advance. However, there are too many entities in RDF graph. In this paper, we point out that collecting two types of lightweight information in RDF graphs: 1. Count the number of relationships between di erent types of entities. 2. Count the number of relationships between speci c entities and di erent types of entities.

Word Core Measurement In the challenge of Question Understanding, we try to use the SPARQL Q to accurately express the semantics of the question N. In fact, the di erent words in N are di erent in the importance of generating Q. However, there is currently no way to measure the importance of each word in N for generating Q. Question Understanding stage can be expressed by the formula:f (N ) → Q.

The natural language question N is composed of the word wi, and the SPARQL is composed of triple pattern pj , hence, we can convert the f (N ) → Q into f (w1; w2; · · · ; wn) → (p1; p2; · · · ; pm), and then by vectorizing wi and pj we can get the following formula: we de ned a loss function as follows.

f (w−→1; w−→2; · · · ; w−→n) → (−→p1; −→p2; · · · ; p−→m)

L =

m ∑(∑ −→pj − j=1 n ∑ w−→i) i=1 ( 1 ) ( 2 ) We choose transH[4] to vectorize triple patterns in SPARQL queries. By formula 2, we make the overall ⟨Ni; Qj ⟩ in the dataset as equal as possible. 3

Multi-Query Optimization

We can divide all phrases in N into two categories:

( 1 ) \The United States" in Figure 1 (c) only corresponds to the entity ⟨United States⟩ in Figure 1(d). We use symbol wo to represent this type of phrases. Dependency tree

Which actors born were in in

Transformers

The United States (a)

Super Semantic

Query Graph

Which movies Nodes

SPARQL Query Graph

( 2 ) The phrase \Transformers" in Figure 1 (c) corresponds to multiple entities ⟨Transformers ( 1,2,3 )⟩ in Figure 1(d). We use symbol wm to represent these ambiguous phrases.

From Figure 1, we can see that subquery {?actors ⟨birthPlace⟩ ⟨United States⟩} is a common subquery among all SPARQL queries. Hence, we can conclude that the SPARQL queries generated by phrases without ambiguity in a question are unique and common.

Besides, due to the large amount of data in RDF Graph, it is very likely that a phrase in N corresponds to many entities. In this case, too many SPARQL queries are generated. Hence, we present a scoring mechanism for words in question. Pay more attention to phrases that have important implications.

We introduce TF-IDF to measure the semantic importance of di erent words in a question:

Score(wi) = T F ( |wi| ) · IDF ( |w|

|N | ) |N (wi)| ( 3 ) |wi| indicates the number of occurrences of the word wi, |w| denotes the total number of words. |N | denotes the number of questions in the corpus, |N (wi)| denotes the number of questions that contain the word wi.

If the importance of a word wi is not high, but wi corresponds to a lot of items in RDF graph. We can ignore wi. In this way, we can slightly reduce the accuracy, but in return for a great increase in e ciency. 4

Experiments and Evaluation

From the data shown in Table 1, we can see that the accuracy of Our Approach is slightly higher than the original work gAnswer[2] because of the better selection of words wi in natural language question N .

As can be seen from Figure 2, the e ciency of processing multiple SPARQL queries can be improved by nding common structures between SPARQL queries. Because it avoids redundant execution of common subquery. On this basis, our method can further improve the execution e ciency of multiple SPARQL queries. Because our method can determine the common subquery in the Question Understanding phase. That is, all phrases in the question that

Processed Right 100 70 100 68 100 40 100 52 100 36 do not contain ambiguity will generate a common subquery after the question understanding stage. 5

Conclusion

In this paper, we addressed the issue of multiple query optimization in RDF Q/A system. We introduce machine learning algorithm to select the useful part of question for SPARQL query generation. At the same time, we give a speci c application of multiple SPARQL queries optimization. We hope that our work can inspire other RDF system designers to apply machine learning more in system design.

Acknowledgments

This work is supported by the National Key Research and Development Program of China (2017YFC0908401) and the National Natural Science Foundation of China (61972455,61672377). Xiaowang Zhang is supported by the Peiyang Young Scholars in Tianjin University (2019XRX-0032).

References

1. Bidoit N. , Herschel M. , Tzompanaki A .: E cient computation of polynomial explanations of why-not questions . In Proc. of CIKM 2015 , pp. 713 { 722 .

2. Hu S. , Zou L. , Yu J.X. , Wang H. , Zhao D. : Answering natural language questions by subgraph matching over knowledge graphs (extended abstract) . In Proc. of ICDE 2018 , pp. 1815 { 1816 .

3. Ren X. , Wang J . : Multi-query optimization for subgraph isomorphism search . PVLDB , 10 ( 3 ): 121 { 132 ( 2016 ).

4. Wang Z. , Zhang J., Feng J. , Chen Z.: Knowledge graph embedding by translating on hyperplanes . In Proc. of AAAI 2014 , pp. 1112 { 1119 .

5. Zou L. , O zsu M.T. , Chen L. , Shen X. , Huang R. , Zhao D . : gStore: A graph-based SPARQL query engine . VLDB J ., 23 ( 4 ): 565 { 590 ( 2014 ).