2005/07/22 by de la Fuente, M. Magdalena Ortiz, Diego Calvanese, Calvanese, Diego +4
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Data Quality and Management #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.cs/0507059
openalex publication_date 2005/07/22 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
An algorithm for answering conjunctive queries over SHIQ knowledge bases that is coNP in data complexity is given. The algorithm is based on the tableau algorithm for reasoning with individuals in SHIQ. The blocking conditions of the tableau are weakened in such a way that the set of models the modified algorithm yields suffices to check query entailment. The modified blocking conditions are based on the ones proposed by Levy and Rousset for reasoning with Horn Rules in the description logic ALCNR.