A New Algorithm for the Containment Problem of Conjunctive Queries with Safe Negation

Many queries about real databases have a particular form, e.g., the negated part consists of one single literal or they contain just a single binary relation, etc. For a particular class of queries, it is useful to construct algorithms for the containment problem, that are better than those for the whole class of queries. The paper is about the problem of query containment for conjunctive queries with safe negation property. A new algorithm to test the containment problem of two queries is given. Several aspects of the time complexity for the proposed algorithm are specified. From this point of view, the new algorithm proves to be better than the previous for some classes of queries.