Complexity to determine containment among inequality tableau queries
Tomoyuki Terada, Kenichi Hagihara, Nobuki Tokura · Systems and Computers in Japan · 1986
Abstract Tableau queries are known as abstract models of queries for relational databases. When two tableau queries are given, the problem of determining whether the result of one of the tableau queries always contains that of the other (containment decision problem), is of fundamental importance in obtaining the optimization procedure of tableau queries. The tableau queries defined by Aho et al. can express joins, projections and selections by equalities in the relational algebra. Under this definition, Aho et al. have shown that the containment decision problems are generally NP‐complete and that there exist a class of problems which can be decided in a polynomial time. In this paper, we classify the tableau queries which are obtained so as to be able to express the selections by inequalities into two groups by whether or not they are totally ordered. We show that if inequality selections are added to problems which can be solved in a polynomial time without inequality selection, then the containment decision problems are NP‐complete even though the tableau queries are totally ordered. Also, for queries which are not totally ordered, it is shown that even if stronger restriction is added, the containment decision problems are co‐NP‐complete.