Efficient Decision Procedures for Query Containment and Related Problems.
Tanara Lauschner, Marco A. Casanova, Vânia Maria Ponte Vidal, José Antônio Fernandes de Macêdo · 2009
Abstract. The subsumption problem in Description Logics (DL) refers to the question of deciding if a concept description always denotes a subset of the set denoted by another concept description. This paper explores reductions of query containment and other problems to the subsumption problem in DL. It first selects a DL dialect that is expressive enough to cover familiar classes of integrity constraints and query expressions. Then, it describes how to modify the tableau decision procedure for the subsumption problem to account for the classes of integrity constraints considered. Finally, it introduces a fast decision procedure for the subsumption problem for the dialect adopted. Resumo. O problema de subsunção em Lógica de Descrição (LD) refere-se à questão de decidir se uma expressão definindo um conceito sempre denota um subconjunto do conjunto que outra expressão denota. Este trabalho explora reduções do problema de inclusão de consultas e problemas semelhantes ao problema de subsunção em LD. Inicialmente, o trabalho introduz um dialeto de LD que é suficientemente expressivo para cobrir certas classes de restrições de integridade e expressões de consulta. Em seguida, descreve como modificar o procedimento de decisão baseado em tableau para o problema de subsunção de forma a tratar as restrições de integridade consideradas. Por fim, apresenta um procedimento de decisão eficiente para o problema de subsunção no dialeto adotado. 1.