Answering Regular Path Queries over SQ Ontologies

We study query answering in the description logic SQ supporting qualified number restrictions on both transitive and non-transitive roles. Our main contributions are a tree-like model property for SQ-knowledge bases and, building upon this, an optimal automata-based algorithm for answering positive existential regular path queries in 2EXPTIME.

• Publication year

  2018

• Venue

  AAAI Conference on Artificial Intelligence

• Publication date

  2018-04-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1609/aaai.v32i1.11539arXiv 2011.08816
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Query Answering in Description Logics with Number Restrictions on Transitive Roles

  2017cited by this paper
• Answering Conjunctive Regular Path Queries over Guarded Existential Rules

  2017cited by this paper
• Number Restrictions on Transitive Roles in Description Logics with Nominals

  2017cited by this paper
• Representing and querying disease networks using graph databases

  2016cited by this paper
• Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms

  2015cited by this paper
• Answering regular path queries in expressive Description Logics via alternating tree-automata

  2014influential reference
• The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases

  2014cited by this paper
• Terminating Tableaux for SOQ\mathcal{SOQ} with Number Restrictions on Transitive Roles

  2010cited by this paper
• Algorithms for effective querying of compound graph-based pathway databases

  2009cited by this paper
• Query Answering in Description Logics with Transitive Roles

  2009cited by this paper
• Regular Path Queries in Expressive Description Logics with Nominals

  2009cited by this paper
• A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

  2009cited by this paper
• Terminating Tableaux for SOQ with Number Restrictions on Transitive Roles

  2009cited by this paper
• Unions of Conjunctive Queries in SHOQ

  2008cited by this paper
• How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited

  2007cited by this paper
• Conjunctive Query Answering for the Description Logic SHIQ

  2007cited by this paper
• Using OWL to model biological knowledge

  2007cited by this paper
• Ontological and Practical Issues in Using a Description Logic to Represent Medical Concept Systems: Experience from GALEN

  2006cited by this paper
• A Little Semantic Web Goes a Long Way in Biology

  2005cited by this paper
• The Description Logic Handbook: Theory, Implementation, and Applications

  2003cited by this paper
• Practical Reasoning for Very Expressive Description Logics

  2000cited by this paper
• Containment of Conjunctive Regular Path Queries with Inverse

  2000cited by this paper
• Guarded fixed point logic

  1999cited by this paper
• Query containment for conjunctive queries with regular expressions

  1998cited by this paper
• Reasoning about The Past with Two-Way Automata

  1998influential reference
• The Complexity of the Inequivalence Problem for Regular Expressions with Intersection

  1980cited by this paper

• LD-RPQB: a benchmark for regular path queries based on length distribution

  2025cites this paper
• Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions

  2024cites this paper
• Adding Transitivity and Counting to the Fluted Fragment

  2023cites this paper
• Finite Entailment of UCRPQs over ALC Ontologies

  2022cites this paper
• Logical separability of labeled data examples under ontologies

  2020cites this paper
• Ontologies and Data Management: A Brief Survey

  2020cites this paper
• On Finite Entailment of Non-Local Queries in Description Logics

  2020cites this paper
• Finite Controllability for Ontology-Mediated Query Answering of CRPQ

  2020cites this paper
• On Finite and Unrestricted Query Entailment beyond SQ with Number Restrictions on Transitive Roles

  2019influential citation