We now observe that, for every partition of $R'$ into two sets, there is a comparability relation going from one set to the other. Hence, $R'$ cannot be written as the union of two non-empty po-relations. Yet, $R'$ has width $n$, as witnessed by the $id_i''$, and it has ia-width $n$, as witnessed by the $id_i'$.

This illustrates that, when performing duplicate consolidation on the union of a constant-width po-relation and of a constant-ia-width po-relation, we cannot hope that the result has constant width, or constant ia-width, or can be written as the union of two relations where each has one of these properties.

### E.4.2 Proof of Theorem 45: POSS and CERT After Removing Duplicates

**▶ Theorem 45.** For any PosRA query $Q$, POSS and CERT for `dupElim(Q)` are in PTIME.

**Proof.** Let $D$ be an input po-relation, and $L$ be the candidate possible world (a list relation). We compute the po-relation $\Gamma'$ such that $pw(\Gamma') = Q(D)$ in PTIME using Proposition 3 and the po-relation $\Gamma := \text{dupElim}(\Gamma')$ in PTIME using Theorem 41. If duplicate elimination fails, we vacuously reject for POSS and CERT, following the remark at the beginning of Appendix E.4. Otherwise, the result is a po-relation $\Gamma$, with the property that each tuple value is realized exactly once, by definition of `dupElim`. Note that we can reject immediately if $L$ contains multiple occurrences of the same tuple, or does not have the same underlying set of tuples as $\Gamma$; so we assume that $L$ has the same underlying set of tuples as $\Gamma$ and no duplicate tuples.

The CERT problem is in PTIME on $\Gamma$ by Theorem 14, so we need only study the case of POSS, namely, decide whether $L \in pw(\Gamma)$. Let $\Gamma_L$ be a po-relation that represents $L$. As $\Gamma_L$ and $\Gamma$ have no duplicate tuples, there is only one way to match each identifier of $\Gamma_L$ to an identifier of $\Gamma$. Build $\Gamma''$ from $\Gamma$ by adding, for each pair $id_i <_L id_{i+1}$ of consecutive tuples of $\Gamma_L$, the order constraint $id_i'' <_L id_{i+1}''$ on the corresponding identifiers in $\Gamma''$. We claim that $L \in pw(\Gamma)$ iff the resulting $\Gamma''$ is a po-relation, i.e., its transitive closure is still antisymmetric, which can be tested in PTIME by computing the strongly connected components of $\Gamma''$ and checking that they are all trivial.

To see why this works, observe that, if the result $\Gamma''$ is a po-relation, it is a total order, and so it describes a way to achieve $L$ as a linear extension of $\Gamma$ because it doesn't contradict any of the comparability relations of $\Gamma$. Conversely, if $L \in pw(\Gamma)$, assuming to the contrary the existence of a cycle in $\Gamma''$, we observe that such a cycle must consist of order relations of $\Gamma$ and $\Gamma_L$, and the order relations of $\Gamma$ are reflected in $\Gamma_L$ as it is a linear extension of $\Gamma$, so we deduce the existence of a cycle in $\Gamma_L$, which is impossible by construction. Hence, we have reached a contradiction, and we deduce the desired result. ◀

## E.5 Alternative Semantics for Duplicate Elimination

A main downside of our proposed semantics for `dupElim` is the fact that complete failure is allowed. We conclude by briefly considering alternative semantics that avoid failure, and illustrate the other problems that they have.

A first possibility is to do a *weak* form of duplicate elimination: keep one element for each *maximal id-set*, rather than for each value, and leave some duplicates in the output:

**▶ Example 90.** Letting $A \neq B$ be two tuples, let us consider a po-relation $\Gamma_L$ representing the list relation $L := (A, B, B, A)$. With weak duplicate elimination, we would have $\text{dupElim}(\Gamma_L) = (A, B, A)$.
However, when generalizing this semantics from totally ordered relations to po-relations, we notice that the result of dupElim on a po-relation may not be representable as a po-relation, since possible worlds differ in their tuples and not only on their order:

**► Example 91.** Consider the po-relation $\Gamma = (\{a_1, b, a_2\}, T, <)$ with $T(a_1) = T(a_2) = A$ and $T(b) = B$, where $A \neq B$ are tuples, and $<$ defined by $a_1 < b$ and $a_1 < a_2$. We have $pw(\Gamma) = \{(A, B, A), (A, A, B)\}$ and $dupElim(\Gamma) = \{(A, B, A), (A, B)\}$ for weak duplicate elimination: we cannot represent it as a po-relation (the underlying relation is not certain).

A second possibility is to do an *aggressive* form of duplicate elimination: define $dupElim(L)$ for a list relation $L$ as the set of *all* totally ordered relations that we can obtain by picking one representative element for each value, even when the representatives are not indistinguishable. In other words, we do not fail even if we cannot reconcile the order between duplicate tuples:

**► Example 92.** Applying *aggressive* dupElim to $\Gamma_L$ from Example 90 yields $\{(A, B), (B, A)\}$.

However, again dupElim($\Gamma_L$) may not be representable as a po-relation, this time because the set of possible orders may not correspond to a partial order:

**► Example 93.** Consider a po-relation $\Gamma_L$ representing the list relation $L := (A, C, B, C, A)$ with distinct tuples $A, B, C$. Then $dupElim(\Gamma_L)$ is $\{(A, C, B), (A, B, C), (B, C, A), (C, B, A)\}$. No po-relation $\Gamma$ satisfies $pw(\Gamma) = dupElim(L)$, because no comparability pair holds in all possible worlds, so $\Gamma$ must be unordered, but then all permutations of $\{A, B, C\}$ are possible worlds of $\Gamma$, which is unsuitable because some of the six permutations of $\{A, B, C\}$ are not possible worlds.

We leave for future work the question of designing a practical semantics for duplicate consolidation that can be incorporated in our framework and avoids failure.

## F Proofs for Section 8 (Comparison With Other Formalisms)

**► Proposition 46.** For any PosRA query $Q$ and a po-relation $D$, $bag(Q(D)) = Q(bag(D))$ where $Q(D)$ is defined according to our semantics and $Q(bag(D))$ is defined by $BALG_+^1$.

*Proof.* There is an exact correspondence in terms of the output bags between additive union and our union; between cartesian product and $\times_{\text{DIR}}$ and $\times_{\text{LEX}}$ (both our product operations yield the same bag as output, for any input); between our selection and that of $BALG_+^1$, and similarly for projection (as noted before the statement of Proposition 46 in the main text, a technical subtlety is that the projection of $BALG$ can only project on a single attribute, but one can encode “standard” projection on multiple attributes). The proposition follows by induction on the query structure. ◀

We formally prove that the output of a PosRA query can be arbitrary:

**► Proposition 94.** For any po-relation $\Gamma$, there is a PosRA query $Q$ with no inputs s.t. $Q() = \Gamma$.

To prove the result, we will need the notion of a *realizer* of a poset:

**► Definition 95.** [Sch03] Letting $P = (V, <)$ be a poset, we say that a set of total orders $(V, <_1), \dots, (V, <_n)$ is a *realizer* of $P$ if for every $x, y \in V$, we have $x < y$ iff $x <_i y$ for all $i$.

We will use this notion for the following lemma. This lemma is given as Theorem 9.6 of [Hir55], see also [Øre62]; we rephrase it in our vocabulary, and for convenience we also give a self-contained proof.
**► Lemma 96.** Let $n \in \mathbb{N}$, and let $(P, <_P)$ be a poset that has a realizer $(L_1, \dots, L_n)$ of size $n$. Then $P$ is isomorphic to a subset $\Gamma'$ of $\Gamma = [\leq l] \times_{\mathrm{DIR}} \cdots \times_{\mathrm{DIR}} [\leq l]$, with $n$ factors in the product, for some integer $l \in \mathbb{N}$ (the order on $\Gamma'$ being the restriction on that of $\Gamma$).

**Proof.** We define $\Gamma$ by taking $l := |P|$, and we identify each element $x$ of $P$ to $f(x) := (n_1^x, \dots, n_n^x)$, where $n_i^x$ is the position where $x$ occurs in $L_i$. Now, for any $x, y \in P$, we have $x <_P y$ iff $n_i^x < n_i^y$ for all $1 \leq i \leq n$ (that is, $x <_{L_i} y$), hence iff $f(x) <_{\Gamma} f(y)$: this uses the fact that there are no two elements $x \neq y$ and $1 \leq i \leq n$ such that the $i$-th components of $f(x)$ and of $f(y)$ are the same. Hence, taking $\Gamma'$ to be the image of $f$ (which is injective), $\Gamma'$ is indeed isomorphic to $P$. ◀

We are now ready to prove Proposition 94:

**Proof of Proposition 94.** We first show that for any poset $(P, <)$, there exists a PosR$\mathrm{A}_{\mathrm{DIR}}$ query $Q$ such that the tuples of $\Gamma' := Q()$ all have unique values and the underlying poset of $\Gamma'$ is $(P, <)$. Indeed, we can take $d$ to be the order dimension of $P$, which is necessarily finite [Sch03], and then by definition $P$ has a realizer of size $d$. By Lemma 96, there is an integer $l \in \mathbb{N}$ such that $\Gamma'' := [\leq l] \times_{\mathrm{DIR}} \cdots \times_{\mathrm{DIR}} [\leq l]$ (with $n$ factors in the product) has a subset $S$ isomorphic to $(P, <)$. Hence, letting $\psi$ be a tuple predicate such that $\sigma_\psi(\Gamma'') = S$ (which can clearly be constructed by enumerating the elements of $S$), the query $Q' := \sigma_\psi(\Gamma'')$ proves the claim, with $\Gamma''$ expressed as above.

Now, to prove the desired result from this claim, build $Q$ from $Q'$ by taking its join (i.e., $\times_{\mathrm{LEX}}$-product, selection, projection) with a union of singleton constant expressions that map each unique tuple value of $Q'()$ to the desired value of the corresponding tuple in the desired po-relation $\Gamma$. This concludes the proof. ◀

References for the Appendix

Dil50 R. P. Dilworth. A decomposition theorem for partially ordered sets. *Annals of Mathematics*, 1950.

Ful55 D. R. Fulkerson. Note on Dilworth's decomposition theorem for partially ordered sets. In *Proc. Amer. Math. Soc*, 1955.

GJ79 M. R. Garey and D. S. Johnson. *Computers And Intractability. A Guide to the Theory of NP-completeness*. W. H. Freeman, 1979.

Hir55 T. Hiraguchi. On the Dimension of Orders. *Sci. rep. Kanazawa Univ.*, 4(01), 1955.

Øre62 O. Øre. Partial order. In *Theory of Graphs*, chapter 10. AMS, 1962.

Pin97 J.-E. Pin. Syntactic semigroups. In *Handbook of Formal Languages*, chapter 10. Springer, 1997.

Sch03 B. Schröder. *Ordered Sets: An Introduction*. Birkhäuser, 2003.

WH84 M. K. Warmuth and D. Haussler. On the complexity of iterated shuffle. *JCSS*, 28(3), 1984.