The Research Of The Query Optimization Problem Of Constraint Relational Model

Query containment is a fundamental algorithmic problem in database optimization. In database theory, query containment problem for conjunctive queries of constraint relational model has been resolved. However, as a result of the difference between database theory and the real database systems, the exact complexity of the query containment problem for conjunctive queries under the real database systems has been an open problem for more than a decade; in fact, it is not even known whether this problem is decidable. According to the achievement of constraint relation model in database theory, it is meaningful to research the decidability of query containment problem for conjunctive queries in the real database systems.We adopt relation calculus to express queries. The difference between database theory and the real database systems is indicated by the convertion of relation calculus. Then, we convert the general query containment problem for conjunctive queries into the query containment problem for conjunctive queries with binary relation. After this, the crucial undecidability result is established by showing that Hilbert's Tenth Problem has a recursive reduction to the query-containment problem for conjunctive queries with inequalities and binary relation in the real database systems. Our reduction will use homogeneous polynomials with non-negative coefficients. Then, we identify a class of special databases and construct a family of conjunctive queries. This makes it possible to recursively reduce Hilbert's Tenth Problem to the querycontainment problem for conjunctive queries in the real database system.After this, we amend appropriately the queries used in the first stage, so that the containment holds over arbitrary databases.In this paper, we show that it can not strength the result of the constraint relational model in database theory to the actual database systems.Further more, we establish the stronger result that, in general, the query containment problem for conjunctive queries with inequalities and binary relation in the actual database system is undecidable. Actually, this problem is undecidable even if the total number of inequalities is bounded by a certain fixed value. As a result, if we identify conjunctive queries with inequalities into several classes, some classes of conjunctive queries with inequalities for which the containment problem in the real database system may be decidable.