On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules

DOI10.1007/978-3-319-45276-0_1MaRDI QIDQ5268431zbMATH OpenOpenAlexFDO

Authors Meghyn Bienvenu, Michaël Thomazo

Publication date 20 June 2017

Published in Web Reasoning and Rule Systems (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01341787/file/main.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Database theory (68P15) Logic in artificial intelligence (68T27)

Recommendations

• Evaluation and enumeration problems for regular path queries
• Complexity of conjunctive regular path query homomorphisms
• Expressiveness and static analysis of extended conjunctive regular path queries
• On decidability of boundedness property for regular path queries
• Regular path queries in lightweight description logics: complexity and algorithms
• scientific article; zbMATH DE number 1953135
• Boundedness of conjunctive regular path queries
• Regular path queries under approximate semantics
• scientific article; zbMATH DE number 2080479
• scientific article; zbMATH DE number 5808834

Cites work

• Acyclicity notions for existential rules and their application to query answering in ontologies
• Answering regular path queries in expressive description logics via alternating tree-automata
• On the complexity of single-rule datalog queries.
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• Regular path queries in lightweight description logics: complexity and algorithms
• Taming the infinite chase: query answering under expressive relational constraints
• Testing containment of conjunctive queries under functional and inclusion dependencies
• The complexity of answering conjunctive and navigational queries over OWL 2 EL knowledge bases

Cited in

(4)

• Fine-Grained Complexity of Regular Path Queries
• Can One Escape Red Chains?
• Querying the unary negation fragment with regular path expressions
• Regular path queries in lightweight description logics: complexity and algorithms

This page was built for publication: On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5268431)