Semantic query reformulation in deductive databases

A method is proposed for identifying relevant integrity constraints (ICs) for queries involving joins/unions of base relations and defined relations by use of graphs. The method does not rely on heavy preprocessing or redundancy. To effectively select those ICs that are relevant to a given query, the relationship between the predicates in the query is identified using an AND/OR tree where an AND mode represents a join operation and an OR node represents a union operation. Ways of collecting ICs are described that are not directly related to the query but can be useful in query optimization