Containment of Simple Regular Path Queries

• URL: http://arxiv.org/abs/2003.04411v1
• Date: Mon, 9 Mar 2020 21:05:29 GMT
• Title: Containment of Simple Regular Path Queries
• Authors: Diego Figueira and Adwait Godbole and S. Krishna and Wim Martens and Matthias Niewerth and Tina Trautner
• Abstract summary: Testing containment of queries is a fundamental reasoning task in knowledge representation. We focus here on severely restricted fragments, which are known to be highly relevant in practice. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for np, pitwo, pspace or expspace.
• Score: 1.869065967043578
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Testing containment of queries is a fundamental reasoning task in knowledge representation. We study here the containment problem for Conjunctive Regular Path Queries (CRPQs), a navigational query language extensively used in ontology and graph database querying. While it is known that containment of CRPQs is expspace-complete in general, we focus here on severely restricted fragments, which are known to be highly relevant in practice according to several recent studies. We obtain a detailed overview of the complexity of the containment problem, depending on the features used in the regular expressions of the queries, with completeness results for np, pitwo, pspace or expspace.

Related papers

• Controlled Query Evaluation through Epistemic Dependencies [7.502796412126707]
  We show the expressive abilities of our framework and study the data complexity of CQE for (unions of) conjunctive queries. We prove tractability for the case of acyclic dependencies by providing a suitable query algorithm.
  arXiv  Detail & Related papers  (2024-05-03T19:48:07Z)
• Meta Operator for Complex Query Answering on Knowledge Graphs [58.340159346749964]
  We argue that different logical operator types, rather than the different complex query types, are the key to improving generalizability. We propose a meta-learning algorithm to learn the meta-operators with limited data and adapt them to different instances of operators under various complex queries. Empirical results show that learning meta-operators is more effective than learning original CQA or meta-CQA models.
  arXiv  Detail & Related papers  (2024-03-15T08:54:25Z)
• Decomposing Complex Queries for Tip-of-the-tongue Retrieval [72.07449449115167]
  Complex queries describe content elements (e.g., book characters or events), information beyond the document text. This retrieval setting, called tip of the tongue (TOT), is especially challenging for models reliant on lexical and semantic overlap between query and document text. We introduce a simple yet effective framework for handling such complex queries by decomposing the query into individual clues, routing those as sub-queries to specialized retrievers, and ensembling the results.
  arXiv  Detail & Related papers  (2023-05-24T11:43:40Z)
• Reverse Engineering of Temporal Queries Mediated by LTL Ontologies [8.244587597395936]
  In reverse engineering of database queries, we aim to construct a query from a given set of answers and non-answers. We investigate this query-by-example problem for queries formulated in positive fragments of linear temporal logic over timestamped data.
  arXiv  Detail & Related papers  (2023-05-02T08:27:39Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
  We consider the query language, unions of conjunctive regular path queries (UCRPQs) We show a tight 2EXP bound for entailment of UCRPQs using the description logic ALC. There is a novel automata-based technique introducing a stratification of interpretations induced by the deterministic finite automaton underlying the input automaton.
  arXiv  Detail & Related papers  (2022-04-29T17:38:13Z)
• 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)
• Graph Enhanced BERT for Query Understanding [55.90334539898102]
  query understanding plays a key role in exploring users' search intents and facilitating users to locate their most desired information. In recent years, pre-trained language models (PLMs) have advanced various natural language processing tasks. We propose a novel graph-enhanced pre-training framework, GE-BERT, which can leverage both query content and the query graph.
  arXiv  Detail & Related papers  (2022-04-03T16:50:30Z)
• A Benchmark for Generalizable and Interpretable Temporal Question Answering over Knowledge Bases [67.33560134350427]
  TempQA-WD is a benchmark dataset for temporal reasoning. It is based on Wikidata, which is the most frequently curated, openly available knowledge base.
  arXiv  Detail & Related papers  (2022-01-15T08:49:09Z)
• Answering Fuzzy Queries over Fuzzy DL-Lite Ontologies [0.2741266294612776]
  We study the problem of answering conjunctive queries and threshold queries in fuzzy DL-Lite. For the idemdent G"odel t-norm, we provide an effective method based on a reduction to the classical case.
  arXiv  Detail & Related papers  (2021-11-23T10:45:54Z)
• Answering Counting Queries over DL-Lite Ontologies [0.0]
  We introduce a general form of counting query, relate it to previous proposals, and study the complexity of answering such queries. We consider some practically relevant restrictions, for which we establish improved complexity bounds.
  arXiv  Detail & Related papers  (2020-09-02T11:10:21Z)

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.