An alternative way to represent the cogroup of a relation in the context of nested databases (Q1124381)

The paper concerns a generally known notion of BP-completeness of relational query languages. In essence, a query language is BP-complete if one can show that for all databases d and d', d' remains invariant under all the permutations on the set of values of the database that leave d invariant, if and only if there exists a query E of the language such that \(d'=(d)\). For example, the relational calculus and algebra, the nested algebra, and the powerset algebra are BP-complete. An appropriate tool to testing BP-completeness of a language is the cogroup. The cogroup of a database is a relation giving the set of all the permutations on the set of its values that leave database invariant. Unfortunately, this relation has not a fixed schema and, as a consequence, it is not expressible by instance-independent expression. The authors show how the cogroup may be expressed as a nested relation with a fixed schema and they prove that there is an expression in the powerset algebra for the cogroup undependently on the cogroup instance. The power of the powerset algebra is documented by a result which emphasizes impossibility of the such construction in the nested algebra (without powerset operator). With presented results the test of BP-completeness becomes easier. The paper gives an interesting integrating contribution to the theory of flat and nested relations, respectively.