Reformulating queries: theory and practice

Conference item

We consider a setting where a user wants to pose a query against a dataset where some background knowledge, expressed as logical sentences, is available, but only a subset of the information can be used to answer the query. We thus want to reformulate the user query against the subvocabulary, arriving at a query that is equivalent to the user’s query assuming the background theory, but using only the restricted vocabulary. We consider two variations of the problem, one where we want any such reformulation and another where we restrict the size. We first present a classification of the complexity of the problem, showing that distinct techniques are needed for the two variations above. We then present algorithms for solving the problems in practice and evaluate their performance.

Authors: Benedikt, M; Kostylev, E; Mogavero, F; Tsamoura, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IJCAI
• Host title: IJCAI International Joint Conference on Artificial Intelligence 2017, Melbourne, Australia
• Journal: IJCAI International Joint Conference on Artificial Intelligence
• Pages: 837-843
• Publication date: 2017-08-25
• Acceptance date: 2017-04-24
• DOI: 10.24963/ijcai.2017/116
• ISSN: 1045-0823