ComputingComputer ScienceAlgorithmsKnowledge RepresentationNatural Language ProcessingDescription LogicsFormal OntologyOntology EngineeringQuery OptimizationQuery ProcessingAxiomsKnowledge CompilationOntologiesOntology ReasoningPolynomial Time ComplexityQuery AnsweringSemantic Web
Efficient query answering over ontologies is one of the most useful and important services to support Semantic Web appli-cations. Approximation has been identified as a potential way to reduce the complexity of query answering over OWL DL ontologies. Existing approaches are mainly based on syntac-tic approximation of ontological axioms and queries. In this paper, we propose to recast the idea of knowledge compila-tion into approximating OWL DL ontologies with DL-Lite ontologies, against which query answering has only poly-nomial data complexity. We identify a useful category of queries for which our approach guarantees also complete-ness. Furthermore, this paper reports on the implementa-tion of our approach in the ONTOSEARCH2 system and pre-liminary, but encouraging, benchmark results which compare ONTOSEARCH2’s response times on a number of queries with those of existing ontology reasoning systems.
9
LUBM: A benchmark for OWL knowledge base systems
Yuanbo Guo, Zhengxiang Pan, Jeff Heflin · Journal of Web Semantics · 2005 · 1.3K citations
DL-Lite: tractable description logics for ontologies
Diego Calvanese, Giuseppe De Giacomo, Domenico Lemho et al. · National Conference on Artificial Intelligence · 2005 · 347 citations
Knowledge compilation and theory approximation
Bart Selman, Henry Kautz · Journal of the ACM · 1996 · 303 citations · Full text
Reducing SHIQ - description logic to disjunctive datalog programs
Ullrich Hustadt, Boris Motik, Ulrike Sattler · 2004 · 212 citations
Tractable reasoning via approximation
Marco Schaerf, Marco Cadoli · Artificial Intelligence · 1995 · 174 citations