Data Complexity of Query Answering in Description Logics
By Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Riccardo Rosati. Description Logics, 2006
499 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/33e604333b951ccd6465e630c60b7cd7e20fa4df
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Diego Calvanese
- Ian Horrocks
- Giuseppe De Giacomo
- Domenico Lembo
- U. Sattler
- Riccardo Rosati
- Roman Kontchakov
- Maurizio Lenzerini
In Computer Networks and Communications
- Diego Calvanese
- Roman Kontchakov
- Domenico Lembo
- Riccardo Rosati
- Giuseppe De Giacomo
- Ian Horrocks
- Maurizio Lenzerini
- Michael Zakharyaschev
Citations in the corpus
- Knowledge-based Systems (2009, unknown): “The best-performing approach is the sequential combination of three proposed methods ( 𝑀𝑂 , 𝑀𝐶 , and 𝑇𝐵 ): V a l u e s”
- Ontology-Based Data Access: A Survey (2018, background): “Ontology languages for which not all OMQs are uniformly FO-rewritable (because of L OG S PACE -hardness) were first studied in 2006 [ Calvanese et al. , 2013 ] , recasting also early results by Schaerf [ 1993 ] on DLs with CO NP-hard query answering.”
- Data integration: the teenage years (2006, background): “, [19]) where the focus is on marrying the expressive power of Description Logics with the ability to manage large amounts of data.”
- The MASTRO system for ontology-based data access (2011, methodology): “Even though very slight extensions of the expressive abilities of our system lead beyond this complexity bound [3], also queries that are more powerful than UCQs can be processed in MASTRO via a similar SQL encoding.”
- Conjunctive Query Answering for the Description Logic SHIQ (2007, background): “(1999) and is also required (although not mentioned) for the algorithm proposed by Calvanese et al. (1998a). The new rewriting steps (split, loop, and forest rewriting) are only required for and applicable to non-simple roles and, when replacing a role atom, only transitive sub-roles of the replaced”
- Bridging the gap between OWL and relational databases (2007, background): “, DL-lite [9] or EL+ + [2]), provided that the “difficult” axioms are treated as constraints.”
- Description Logic Knowledge and Action Bases (2014, methodology): “We follow the usual assumption in DL-Lite , according to which a TBox may contain neither ( funct P ) nor ( funct P − ) if it contains R (cid:118) P or R (cid:118) P − , for some role R (Poggi et al., 2008; Calvanese et al., 2013).”
- Linking Data to Ontologies (2008, methodology): “Recent research has shown that OWL, the W3C Web Ontology Language for the Semantic Web3, if not restricted, is not suited as a formalism for representing ontologies with large amounts of instance assertions in the ABox [7,26,17], since reasoning in such a logic is inherently exponential (coNPhard) w”
- The DL-Lite Family and Relations (2009, methodology): “As was already observed by Calvanese et al. (2006), such a combination increases data complexity of instance checking from membership in LogSpace to 5.”
- Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family (2007, methodology): “In particular, the results reported in [14] imply that for the DL that includes all the constructs of the two logics studied in the paper, specifically, both inclusion assertions between roles and functionality assertions, query answering is PTime-hard, thus ruling out the possibility of using off-t”