QDEF and Its Approximations in OBDM

Given an input dataset (i.e., a set of tuples), query definability in Ontology-based Data Management (OBDM) amounts to find a query over the ontology whose certain answers coincide with the tuples in the given dataset. We refer to such a query as a characterization of the dataset with respect to the OBDM system. Our first contribution is to propose approximations of perfect characterizations in terms of recall (complete characterizations) and precision (sound characterizations). A second contribution is to present a thorough complexity analysis of three computational problems, namely verification (check whether a given query is a perfect, or an approximated characterization of a given dataset), existence (check whether a perfect, or a best approximated characterization of a given dataset exists), and computation (compute a perfect, or best approximated characterization of a given dataset).

• Publication year

  2021

• Venue

  arXiv.org

• Publication date

  2021-08-23

• Fields of study

  Computer Science

• Identifiers
  arXiv 2108.10021
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Abstraction in Ontology-based Data Management

  2022cited by this paper
• Abstraction in Data Integration

  2021cited by this paper
• Non-Monotonic Ontology-based Abstractions of Data Services

  2020cited by this paper
• Query Expressibility and Verification in Ontology-Based Data Access

  2020cited by this paper
• Ontology-Mediated Queries from Examples: a Glimpse at the DL-Lite Case

  2019influential reference
• Semantic Characterization of Data Services through Ontologies

  2019influential reference
• Reverse engineering database queries from examples: State-of-the-art, challenges, and research opportunities

  2019cited by this paper
• Reverse Engineering Queries in Ontology-Enriched Systems: The Case of Expressive Horn Description Logic Ontologies

  2018cited by this paper
• DL-Learner Structured Machine Learning on Semantic Web Data

  2018cited by this paper
• DLFoil: Class Expression Learning Revisited

  2018cited by this paper
• New Trends on Exploratory Methods for Data Analytics

  2017cited by this paper
• Preliminary Results on Ontology-based Open Data Publishing

  2017cited by this paper
• Learning Join Queries from User Examples

  2016cited by this paper
• The complexity of reverse engineering problems for conjunctive queries

  2016cited by this paper
• pFOIL-DL: learning (fuzzy) EL concept descriptions from crisp OWL data using a probabilistic ensemble estimation

  2015cited by this paper
• The Product Homomorphism Problem and Applications

  2015cited by this paper
• Query reverse engineering

  2014cited by this paper
• Definability problems for graph query languages

  2013cited by this paper
• OWL 2 Web Ontology Language Primer (Second Edition)

  2012cited by this paper
• Query Processing under GLAV Mappings for Relational and Graph Databases

  2012cited by this paper
• Principles of Data Integration

  2012cited by this paper
• Ontology-based data management

  2011cited by this paper
• The DL-Lite Family and Relations

  2009cited by this paper
• Taming the Infinite Chase: Query Answering under Expressive Relational Constraints

  2008cited by this paper
• Linking Data to Ontologies

  2008cited by this paper
• Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family

  2007influential reference
• The Description Logic Handbook: Theory, Implementation, and Applications

  2003cited by this paper
• Data exchange: semantics and query answering

  2003cited by this paper
• Data integration: a theoretical perspective

  2002cited by this paper
• Exact complexity of Exact-Four-Colorability

  2001influential reference
• Navigational Plans For Data Integration

  1999cited by this paper
• Foundations of Databases

  1994influential reference
• On Truth-Table Reducibility to SAT

  1991cited by this paper
• Bounded Query Classes

  1990cited by this paper
• More Complicated Questions About Maxima and Minima, and Some Closures of NP

  1986cited by this paper
• A Note on Succinct Representations of Graphs

  1986influential reference
• The complexity of facets (and some facets of complexity)

  1982cited by this paper
• Some Simplified NP-Complete Graph Problems

  1976influential reference
• Query-by-example: the invocation and definition of tables and forms

  1975cited by this paper

• Separability and Its Approximations in Ontology-based Data Management

  2023influential citation
• Query Definability and Its Approximations in Ontology-based Data Management

  2021cites this paper