Answering Regular Path Queries Over SQ Ontologies

• URL: http://arxiv.org/abs/2011.08816v1
• Date: Tue, 17 Nov 2020 18:27:20 GMT
• Title: Answering Regular Path Queries Over SQ Ontologies
• Authors: V\'ictor Guti\'errez-Basulto and Yazm\'in Ib\'a\~nez-Garc\'ia and Jean Christoph Jung
• Abstract summary: We study query answering in the description logic $mathcalSQ$. Our main contributions are a tree-like model property for $mathcalSQ$ knowledge bases and, building upon this, an optimal automata-based algorithm for answering positive existential regular path queries in 2ExpTime.
• Score: 9.03029278078007
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study query answering in the description logic $\mathcal{SQ}$ supporting qualified number restrictions on both transitive and non-transitive roles. Our main contributions are a tree-like model property for $\mathcal{SQ}$ knowledge bases and, building upon this, an optimal automata-based algorithm for answering positive existential regular path queries in 2ExpTime.

Related papers

• RConE: Rough Cone Embedding for Multi-Hop Logical Query Answering on Multi-Modal Knowledge Graphs [30.94793132285142]
  Multi-hop query answering over a Knowledge Graph involves traversing one or more hops from the start node to answer a query. We propose RConE, an embedding method to capture the multi-modal information needed to answer a query. We are the first to introduce logical constructs in querying MMKGs and to answer queries that involve sub-entities of multi-modal entities as the answer.
  arXiv  Detail & Related papers  (2024-08-21T11:02:35Z)
• Open-Set Knowledge-Based Visual Question Answering with Inference Paths [79.55742631375063]
  The purpose of Knowledge-Based Visual Question Answering (KB-VQA) is to provide a correct answer to the question with the aid of external knowledge bases. We propose a new retriever-ranker paradigm of KB-VQA, Graph pATH rankER (GATHER for brevity) Specifically, it contains graph constructing, pruning, and path-level ranking, which not only retrieves accurate answers but also provides inference paths that explain the reasoning process.
  arXiv  Detail & Related papers  (2023-10-12T09:12:50Z)
• Reasoning over Hierarchical Question Decomposition Tree for Explainable Question Answering [83.74210749046551]
  We propose to leverage question decomposing for heterogeneous knowledge integration. We propose a novel two-stage XQA framework, Reasoning over Hierarchical Question Decomposition Tree (RoHT) Experiments on complex QA datasets KQA Pro and Musique show that our framework outperforms SOTA methods significantly.
  arXiv  Detail & Related papers  (2023-05-24T11:45:59Z)
• Ontology-Mediated Querying on Databases of Bounded Cliquewidth [10.880181451789262]
  We study the evaluation of ontology-mediated queries (OMQs) on databases of bounded cliquewidth. Our main contribution is a detailed analysis of the dependence of the running time on the parameter, exhibiting several interesting effects.
  arXiv  Detail & Related papers  (2022-05-04T17:13:08Z)
• Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
  We propose a query embedding method to answer complex logical queries on knowledge graphs with missing edges. The answer entities are selected according to the similarities between the entity embeddings and the query embedding. A complex KG query answering method, Q2P, is proposed to retrieve diverse answers from different areas over the embedding space.
  arXiv  Detail & Related papers  (2022-04-27T11:16:08Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard [11.193504036335503]
  In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking. For knowledge bases in the basic description logic ALC, the computational complexity of conjunctive query (CQ) answering is well known to be ExpTime-complete. We show that even extending ALC by just the Self operator increases the complexity of CQ entailment to 2ExpTime.
  arXiv  Detail & Related papers  (2021-06-29T08:12:03Z)
• Logic Embeddings for Complex Query Answering [56.25151854231117]
  We propose Logic Embeddings, a new approach to embedding complex queries that uses Skolemisation to eliminate existential variables for efficient querying. We show that Logic Embeddings are competitively fast and accurate in query answering over large, incomplete knowledge graphs, outperform on negation queries, and in particular, provide improved modeling of answer uncertainty.
  arXiv  Detail & Related papers  (2021-02-28T07:52:37Z)
• CQE in Description Logics Through Instance Indistinguishability (extended version) [0.0]
  We study privacy-preserving query answering in Description Logics (DLs) We derive data complexity results query answering over DL-Lite$_mathcal$$. We identify a semantically well-founded notion of approximated confidentiality answering for CQE.
  arXiv  Detail & Related papers  (2020-04-24T17:28:24Z)
• Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings [84.0206612938464]
  query2box is an embedding-based framework for reasoning over arbitrary queries on incomplete knowledge graphs. We show that query2box is capable of handling arbitrary logical queries with $wedge$, $vee$, $exists$ in a scalable manner. We demonstrate the effectiveness of query2box on three large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.
  arXiv  Detail & Related papers  (2020-02-14T11:20:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.