Bag containment of conjunctive queries

A table contains the row (a, b) twice and (a, c) once. A query that keeps just the first column returns a three times. A second query chooses two rows with the same first column and returns that column once for each ordered pair. Rows may be reused, so it returns a nine times. Both answers contain only the value a, but their repetition counts differ.

Can a program always decide whether one such query returns each answer no more often than another, on every possible finite table, including tables with duplicate rows?[1]

Can a terminating procedure compare two queries on every duplicate-containing database, deciding whether the first always returns each answer at most as often as the second? Checking one table cannot establish that universal statement.

A conjunctive query describes a pattern of table rows with shared variables. Projection hides some variables, so several choices of hidden values can yield the same answer. Under bag semantics, each choice contributes the product of the participating tuple multiplicities, and those contributions are added. For the table with two copies of (a, b) and one of (a, c), one table atom followed by projection gives $2+1=3$ copies of a. Two atoms sharing the first variable give $(2+1)^2=9$.

The unknown concerns arbitrary pairs of these pure queries and finite input bags. Under bag-set semantics, input tables have no duplicate tuples but answers may repeat. On the corresponding two-row set, the example counts become two and four, so changing input semantics changes the comparison being studied.[1] [2]

The general decision problem remains open.[2]

Undecidability for extensions with unions or inequalities does not settle pure conjunctive queries.[2]

It matters when query rewrites must preserve repeated answers, rather than merely the set of answers.[1]

The sum-of-products rule turns a query into a counting expression over possible matches of its variables. That connects containment with inequalities between counts of pattern-preserving maps, rather than only with whether a match exists.

It also explains the practical meaning of the universal quantifier: a rewrite correct on a sample database may fail once row multiplicities change. A proof of equal counts requires both directed inequalities on all databases, while the general decision question asks whether such comparisons can always be settled algorithmically.[1] [2]