To combine and query ordered data from multiple sources, one needs to
handle uncertainty about the possible orderings. Examples of such
“order-incomplete” data include integrated event sequences such as
log entries; lists of properties (e.g., hotels and
restaurants) ranked by an unknown function reflecting relevance or
customer ratings; and documents edited concurrently with an uncertain order
on edits. This
paper introduces a query language for order-incomplete data, based on
the positive relational algebra with order-aware accumulation. We use
partial orders to represent order-incomplete data, and study possible
and certain answers for queries in this context. We show that these
problems are respectively NP-complete and coNP-complete, but identify
tractable cases depending on the query operators or input partial

§ INTRODUCTION

Many applications need to combine and transform ordered data (e.g., temporal
data, rankings, preferences) from
multiple sources. Examples include sequences of readings from
multiple sensors, or log entries from different applications or
machines, that must be combined to form a complete picture of
events; rankings of restaurants and hotels published by
different websites, their ranking function being often
proprietary and unknown; and concurrent edits of shared documents,
where the order of contributions made by different users needs to be
merged. Even when the order of items from each individual source is
known, the order across sources is often uncertain.
For instance, even when sensor readings or log entries have
timestamps, these may be ill-synchronized across sensors or
machines; different websites may follow different rules
and rank different hotels, so there are multiple ways to create a
unified ranked list; concurrent document editions may be
ordered in multiple ways. We say that the resulting
information is order-incomplete.

This paper studies query evaluation over order-incomplete data in
a relational setting [1]. Our running example is that of restaurants
and hotels from travel websites, ranked according to proprietary
functions. An example query could compute the union of ranked lists of restaurants from distinct
websites, or ask for a ranked list of pairs of a restaurant and a
in the same district. As we do not know how the proprietary order is
defined, the query result may become uncertain:
there may be multiple reasonable orderings of
restaurants in the union result, or multiple orderings of
restaurant–hotel pairs. We also study the application of
order-aware accumulation to
the query result, where each possible order may yield a different value:
e.g., extracting only the highest ranked pairs,
their names, or assessing the
attractiveness of a district based on its
best restaurants and hotels.

Our approach is to handle this uncertainty through the classical notions
of possible and certain answers. First, whenever there is a
certain answer to the query – i.e., there is only one possible order on query results or one accumulation result –
which is obtained no matter the order on the input and in intermediate
results, we should present it to the user, who can then browse through
the ordered query results (as is typically done in absence of
uncertainty, using constructs such as SQL's ).
Certain answers can arise even in non-trivial cases
where the combination of input data admits
many possible
orders: consider user queries that select only a small interesting subset of the
data (for which the ordering happens to be certain), or a short summary
obtained through accumulation over large data. In many other cases, the
different orders on input data or the uncertainty caused by the query may
lead to several possible answers. In this case, it is still of
interest (and non-trivial) to verify whether an answer is
possible, e.g., to check whether a given ranking of hotel–restaurant pairs is consistent with a combination of other rankings (the latter done through a query). Thus, we study the problems of deciding whether a given answer is
certain, and whether it is possible.

As users may wish to focus on the position of some tuples of
interest (e.g., “is it possible/certain that a particular restaurant–hotel pair
is ranked first?”, or “is it possible/certain that restaurant
$A$ is ranked above restaurant $B$?), we show that these questions may be expressed in our framework through proper choices of accumulation functions.

Main contributions.

We introduce a query
language with accumulation
for order-incomplete data,
generalizes the positive relational algebra [1] with aggregation as
the outermost
We define a bag semantics for this language, without assuming that a single choice of order can be
made (unlike, e.g., rank aggregation [15]): we use partial orders
to represent
all orders that are consistent with the  input data.
We then
the first general study of the
complexity of possible and certain answers for queries over
such data.
We show that these problems are respectively NP-complete and coNP-complete,
the main difficulties being the existence of
duplicate tuple values in the data and the use of order-aware accumulation.
Fortunately, we can show realistic tractable cases: certainty is in PTIME
without accumulation, and both problems are tractable under reasonable
restrictions on the input and on the query.

The rest of this paper is organized as follows.
In Section <ref>, we introduce our data model and our query language.
We define and exemplify the problems of possible and certain answers in Section <ref>.
We then study their complexity, first in the general case (Section <ref>),
then in restricted settings that ensure tractability
(Sections <ref> and <ref>).
We study extensions to the language, namely duplicate elimination and group-by, in Section <ref>.
We compare our model and results with related work in Section <ref>, and conclude in Section <ref>.

Full proofs of all results are given in an extensive appendix, for lack
of space. Please note that this version of the paper removes some erroneous
results relative to an earlier arXiv version and the conference proceedings
version: see Appendix <ref> for details.

§ DATA MODEL AND QUERY LANGUAGE

We fix a countable set of values $\calD$
that includes $\Nat$ and infinitely many values not in $\Nat$.
A tuple $t$ over $\calD$ of arity $\arity{t}$ is an
element of $\calD^{\arity{t}}$, denoted $\langle v_1, \dots,
v_{\smash{\arity{t}}}\rangle$. The simplest notion of ordered relations are then
list relations [11, 12]: a list relation
of arity $n \in \Nat$
is an ordered list of tuples over $\calD$ of arity $n$ (where
the same tuple value may appear multiple times).
List relations impose a single order over tuples, but when one
combines (e.g., unions) them, there may be multiple plausible ways
to order the results.

We thus introduce partially
ordered relations (po-relations). A po-relation  $\OR =
(\ID, T, <)$ of arity $n \in \Nat$ consists of a finite set of
identifiers $\ID$ (chosen from some infinite set
closed under product), a strict partial order $<$ on $\ID$, and a (generally non
injective) mapping $T$ from $\ID$ to $\calD^n$.
The actual identifiers do not matter, but
we need them to
refer to occurrences of the
same tuple value. Hence, we always
consider po-relations up to isomorphism, where $(\ID, T, <)$ and $(\ID',
T', {<'})$ are isomorphic iff there is a bijection $\phi: \ID \to \ID'$
such that $T'(\phi(\id)) = T(\id)$ for all $\id \in \ID$, and $\phi(\id_1) {<'}
\phi(\id_2)$ iff $\id_1 < \id_2$ for all $\id_1, \id_2 \in \ID$.

A special case of po-relations
are unordered po-relations (or bag relations), where $<$ is empty:
we write them $(\ID, T)$. The underlying bag relation of
$\OR = (\ID, T, <)$ is $(\ID, T)$.

The point of po-relations is to represent sets of list relations.
Formally, a linear extension $<'$ of $<$ is a total order on $\ID$ such
that for each $x<y$ we have $x <' y$. The
possible worlds $\pw(\OR)$ of $\OR$ are then defined as follows:
for each linear extension ${<'}$ of $<$, writing $\ID$ as $\id_1 <' \cdots <'
\id_{\card{\ID}}$,
the list relation $(T(\id_1), \ldots, T(\id_{\card{ID}}))$ is
in $\pw(\OR)$. As $T$ is generally not injective, two different linear extensions may yield the
same list relation.
Po-relations can thus model uncertainty over the order of
tuples (but not on their value: the underlying bag relation is always

$\!\!$b]l@  c
restname     distr

Gagnaire     8     0.9emfroma

TourArgent     5     -0.3emtoafromatoa

2c(a) $\mathit{Rest}$ table

b]l@ c
hotelname     distr

Mercure     52  0.9emfromb

Balzac     82  0.9emdummy

Mercure     12  -0.3emtobfrombtob

2c(b) $\mathit{Hotel}$ table

b]l@ c
hotelname     distr

Balzac     82  0.9emfromc

Mercure     52  0.9emdummyd

Mercure     12  -0.3emtocfromctoc

2c(c) $\mathit{Hotel}_2$ table

Running example: Paris restaurants and hotels
(GM) at (0,-2) $\langle\textup{G},8,\textup{M},5\rangle$;
(TAM) at (1,-1) $\langle\textup{TA},5,\textup{M},5\rangle$;
(GB) at (-1,-1) $\langle\textup{G},8,\textup{B},8\rangle$;
(TAB) at (0,0) $\langle\textup{TA},5,\textup{B},8\rangle$;
[->] (GM) – (GB);
[->] (GB) – (TAB);
[->] (GM) – (TAM);
[->] (TAM) – (TAB);

Example <ref>

[yscale=.8,every node/.style=align=center,outer sep=0,inner
(n13) at (0, 0) fr
(n20) at (1, 0) it
(n37) at (0, 1) fr
(n42) at (1, 1) it
(n100) at (0, 2) jp
(n102) at (1, 2) jp
[->] (n13) – (n37);
[->] (n20) – (n37);
[->] (n37) – (n100);
[->] (n42) – (n100);
[->] (n42) – (n102);

Example <ref>

Query language.

We now define a bag semantics for
positive relational algebra operators, to manipulate po-relations with queries. The positive relational
written , is a standard query language for relational
data [1].
We will extend later in this section with
and add further extensions in Section <ref>.
Each operator applies to po-relations and computes a new po-relation; we
present them in turn.

The  operator restricts
the relation to a subset of its tuples, and the order is
the restriction of the input order. The tuple predicates
allowed in selections are Boolean combinations of
equalities and inequalities, which can use tuple attributes and values in

selection: For any po-relation
$\OR = (\ID, T,<)$
and tuple predicate $\psi$,
we define the selection $\sigma_{\psi}(\OR) \defeq (\ID', T_{|\ID'}, <_{|\ID'})$
where $\ID' \defeq \{\id \in \ID \mid \psi(T(\id))\text{~holds}\}$.

The  operator changes tuple values in the usual way, but
keeps the original tuple ordering in the result, and retains all copies of duplicate
tuples (following our bag semantics):

projection: For a po-relation
$\OR = (\ID,T,<)$ and attributes $A_1, \ldots, A_n$,
we define the projection $\Pi_{A_1, \ldots, A_n}(\OR) \defeq
(\ID,T', {<})$ where $T'$ maps each $\id \in \ID$ to
$\Pi_{A_1, \ldots, A_n}(T(\id))$.

As for , we impose the minimal order constraints that are
compatible with those of the inputs.
We use the
parallel composition [7] of two partial orders $<$
and $<'$ on disjoint sets $\ID$ and $\ID'$, i.e., the partial order $<''
\defeq ({<}
\mathbin{\parallel} {<'})$
on $\ID \cup \ID'$ defined by:
every $\id \in \ID$ is incomparable for $<''$ with every
$\id' \in \ID'$;
for each $\id_{1}, \id_{2}\in ID$, we have $\id_{1} <'' \id_{2}$ iff $\id_{1} < \id_{2}$;
for each $\id_{1}', \id_{2}' \in ID'$, we have $\id_{1}'<'' \id_{2}'$ iff
$\id_{1}'<' \id_{2}'$.

union: Let $\OR = (\ID,T,<)$ and $\OR' = (\ID',T',<')$ be two po-relations of
the same arity. We assume that the identifiers of $\OR'$ have been renamed
if necessary to ensure that $\ID$ and $\ID'$ are disjoint.
We then define $\OR \cup \OR'
\defeq (\ID \cup \ID', T'', {<} \mathbin{\parallel} {<'})$, where $T''$
$\id \in \ID$ to $T(\id)$ and
$\id' \in \ID'$ to $T'(\id')$.

The union result $\OR \cup \OR'$ does not depend on how we renamed $\OR'$,
i.e., it is unique up to isomorphism.
Our definition also
implies that $\OR \cup \OR$ is different from $\OR$, as per bag semantics.
In particular, when $\OR$ and $\OR'$ have only one possible world,
$\OR \cup \OR'$ usually does not.

We next introduce two possible  operators. First, the
direct product [40] ${<_{\ptw}} \defeq
({<} \times_\ptw {<'})$ of two partial orders $<$ and $<'$ on
sets $\ID$ and $\ID'$ is defined by $(\id_{1}, \id_{1}') <_{\ptw} (\id_{2},
\id_{2}')$ for
each $(\id_{1},  \id_{1}'), (\id_{2}, \id_{2}') \in \ID \times \ID'$ iff
$\id_{1} < \id_{2}$ and $\id_{1}' <'
\id_{2}'$.
We define the  operator over po-relations
accordingly: two identifiers in the product are comparable only
if both components of both identifiers compare in the same

direct product: For any po-relations $\OR = (\ID, T,<)$ and
$\OR' = (\ID', T',<')$,
remembering that the sets of possible identifiers is closed under product,
we let $\OR \times_\gen \OR' \defeq
(\ID \times \ID', T'', \allowbreak {< \times_{\ptw} <'})$,
where $T''$ maps each $(\id, \id') \in \ID \times \ID'$ to the
concatenation $\langle T(\id), T'(\id') \rangle$.

Again, the direct product result often has multiple possible worlds even when
inputs do not.

The second product operator uses the  (or ordinal
product [40])
${<_\lex} \defeq ({<} \times_\lex {<'})$
of two partial orders $<$ and $<'$,
defined by $(\id_{1}, \id_{1}') <_{\lex} (\id_{2}, \id_{2}')$ for all $(\id_{1},
\id_{1}'), (\id_{2}, \id_{2}') \in \ID \times \ID'$ iff
either $\id_{1} < \id_{2}$, or $\id_{1} = \id_{2}$ and $\id_{1}' <' \id_{2}'$.

lexicographic product:
For any po-relations $\OR = (\ID, T,<)$ and $\OR' = (\ID', T',<')$,
we define
$\OR \times_\lex \OR'$ as $(\ID
\times \ID', T'', < \times_\lex <')$ with $T''$ defined like for direct

Last, we define the constant expressions that we allow:

const: •for any tuple $t$, the singleton po-relation $\singleton{t}$
has only one tuple with value $t$;
•for any $n \in \Nat$, the po-relation $\ordern{n}$ has arity $1$
and has
$\pw(\ordern{n}) = \{(1, \ldots, n)\}$.

§.§ Proof of Theorem <ref>

A natural question is then to determine whether any of our operators is subsumed
by the others, but we show that this is not the case:

No  operator can be expressed through a combination of the

We actually prove a stronger result, namely
Theorem <ref>, where we add the $\dupelim$ operator
to operators. We
consider each operator in
turn, showing it cannot be expressed through a combination of the others.

We first consider constant expressions. We will show differences in
expressiveness even when setting the input po-database to be empty.

* For $\singleton{t}$, consider the query $\singleton{\langle0\rangle}$.
The value $0$ is not in the database,
and cannot be produced by the $\ordern{n}$ constant
expression, and so
this query has no equivalent that does not use the $[t]$ constant

* For $\ordern{n}$, observe that $\ordern{2}$ is a po-relation with
a non-empty order, while any query involving the other operators
will have empty order (none of
our unary and binary operators turns unordered po-relations into an ordered
one, and the $\singleton{t}$ constant expression produces an
unordered po-relation).

Moving on to unary and binary operators, all operators but products are easily shown to be

For any constant $a$ not
in $\mathbb{N}$, consider the po-database $D_a$ consisting of a
single unordered po-relation with name $R$ formed of
two unary tuples $\langle 0\rangle$ and
$\langle a\rangle$. Let
$Q=\sigma_{.1\neq\text{``0''}}(R)$. Then, $Q(D_a)$ is the po-relation
consisting only of the tuple $\langle a\rangle$. No PosRA query
without selection has the same semantics, as no other operator than
selection can create a po-relation containing the constant $a$ for
any input $D_a$, unless it also contains the constant $0$.

projection. $\Pi$ is the only operator that can decrease the arity of an
input po-relation.

union. $[\langle 0\rangle]\cup[\langle 1\rangle]$ (over the empty
po-database) cannot be simulated by any combination of operators, as
can be simply shown by induction: no other operator will produce a
po-relation which has in the same attribute the two elements $0$ and

duplicate elimination.
For any constant $a$ not
in $\mathbb{N}$, consider the po-database $D_a$ consisting of a
single unordered po-relation with name $R$ formed of
two identical unary tuples $\langle a\rangle$ and
$\langle a\rangle$. Let
$Q=\dupelim(R)$. Then, $Q(D_a)$ is the po-relation
consisting of the single tuple $\langle a\rangle$. No PosRA query
without duplicate elimination has the same semantics, as no other operator than
duplicate elimination can create a po-relation containing only once the constant $a$ for
any input $\Gamma_a$.

Observe that product operators are the only ones that can
increase arity, so taken together they are non-redundant with the other
There remains to prove that each of $\times_\gen$ and $\times_\lex$ is not
As in Section <ref>, we use the name for the fragment of
where $\times_\lex$ is not used; and for the fragment of
where $\times_\gen$.

§.§.§ Transformations Not Expressible in + dupElim

We rely on Propositions <ref> and <ref>: the
result of any query (possibly with $\dupelim$), when it does not completely fail, has a
width (see Definition <ref> in Section <ref>) bounded by a function of
the width of the original po-database. On
the other hand, consider the query $Q=R\times_\gen R$ and an input
po-database $D_n$ where $R$ is mapped to $\ordern{n}$ (an input relation
of width $1$) for an arbitrary $R_n$.
Then $Q(D_n)$ is a po-relation of width $n$, which shows $Q$ is not
expressible with the operators of and $\dupelim$.

§.§.§ Transformations Not Expressible in + dupElim

We now show the converse, that expresses some transformations that
cannot be expressed in . To do this, we introduce the
concatenation of po-relations:

The concatenation
$\OR \cupcat \OR'$ of two po-relations $\OR$ and $\OR'$
is the series composition of their two partial
orders. Note that $\pw(\OR \cupcat \OR') = \{L \cupcat L' \mid L \in \pw(\OR),
L' \in \pw(\OR')\}$, where $L \cupcat L'$ is the concatenation of two list
relations in
the standard sense.

We show that concatenation can be captured with .

For any arity $n \in \mathbb{N}$ and distinguished relation names $R$ and $R'$,
there is a query $Q_n$ such that, for any two
po-relations $\OR$ and $\OR'$ of arity $n$, letting $D$ be the
database mapping $R$ to $\OR$ and $R'$ to $\OR'$, $Q_n(D)$ is
$\OR \cupcat \OR'$.

For any $n \in \mathbb{N}$ and names $R$ and $R'$,
consider the following query (using again numerical attribute names for

\[Q_n(R, R') \defeq
\Pi_{3\dots n+2} \left(\sigma_{.1= .2} \left(\ordern{2}
\times_\lex ((\singleton{1}\times_\lex R) \cupgen
(\singleton{2}\times_\lex R'))\right)\right)\]

It is easily verified that $Q_n$ satisfies the claimed property.

By contrast, we show that concatenation cannot be captured with and $\dupelim$.

For any arity $n \in \mathbb{N}_+$ and distinguished relation names $R$ and $R'$,
there is no query $Q_n$ (possibly with $\dupelim$) such that, for any
po-relations $\OR$ and $\OR'$ of arity $n$, letting $D$
be the
po-database that maps $R$ to $\OR$ and $R'$ to $\OR'$, the query result $Q_n(D)$
is $\OR \cupcat \OR'$.

To prove Lemma <ref>, we first introduce the following concept:

Let $v \in \calD$. We call a
po-relation $\OR = (\ID, T, <)$ $v$-impartial if, for any
two identifiers $\id_1$ and $\id_2$ and $1 \leq i \leq \arity{\OR}$ such that exactly
one of $T(\id_1).i$, $T(\id_2).i$ is $v$, the following holds: $\id_1$ and
$\id_2$ are incomparable, namely, neither $\id_1 < \id_2$ nor $\id_2
< \id_1$ hold.

Let $v \in \calD \backslash \mathbb{N}$ be a value. For any query
$Q$, possibly with $\dupelim$,
for any
po-database $D$ of $v$-impartial
po-relations, the po-relation $Q(D)$ (when duplicate elimination does
not completely fail) is

Let $v \in \calD \backslash \mathbb{N}$ be such a value.
We show the claim by induction on the query $Q$.

The base cases are the following:

* For the base relations, the claim is vacuous by our hypothesis on $D$.

* For the singleton constant expressions, the claim is trivial as
they contain less than two tuples.

* For the $\ordern{i}$ constant expressions, the claim is
immediate as $v \notin \mathbb{N}$.

We now prove the induction step:

* For selection, the claim is shown by noticing that, for any
po-relation $\OR$,
letting $\OR'$ be the image of $\OR$ by any selection, $\OR'$
is itself $v$-impartial. Indeed, considering two identifiers $\id_1$ and
$\id_2$ in
$\OR'$ and $1 \leq i \leq \arity{\OR}$ satisfying the condition, as $\OR$ is
$v$-impartial, $\id_1$ and $\id_2$ are incomparable in $\OR$, so they are also
incomparable in $\OR'$.

* For projection, the claim is also immediate as the property to prove
is maintained when reordering, copying or deleting attributes. Indeed,
considering again two identifiers $\id_1'$ and $\id_2'$ of $\OR'$ and $1
\leq i' \leq \arity{\OR'}$, the respective preimages $\id_1$ and $\id_2$ in $\OR$ of $\id_1'$ and
$\id_2'$ before the
projection satisfy the same condition for some different $1 \leq i \leq
\arity{\OR}$ which is the
preimage of $i'$, so we again use the impartiality of the original
po-relation to conclude.

* For union, the property is preserved. Indeed, for $\OR'' \defeq \OR \cupgen
\OR'$, writing $\OR'' = (\ID'', T'', {<''})$, assume by contradiction the existence of two identifiers $\id_1,
\id_2 \in
\OR''$ and $1 \leq i \leq \arity{\OR''}$ such that exactly one of
$T''(\id_1).i$ and
$T''(\id_2).i$ is $v$ but (without loss of generality) $\id_1 < \id_2$ in
It is easily seen that, as $\id_1$ and
are not incomparable, they must come from the same relation; but then, as
that relation was $v$-impartial, we have a contradiction.

* For duplicate elimination, the property is preserved as
duplicate elimination (when it does not fail) results in a
po-relation where the order between tuples with different values is

* We now show that the property is preserved for $\times_\gen$. Consider
$\OR'' \defeq \OR\times_\gen \OR'$ where $\OR$ and $\OR'$ are
$v$-impartial, and write $\OR'' = (\ID'', T'', <'')$ as above.
Assume that there are two identifiers $\id_1''$ and $\id_2''$ of $\ID''$
and $1 \leq i \leq \arity{\OR''}$ that violate the $v$-impartiality of $\OR''$.
Let $(\id_1, \id_1'), (\id_2, \id_2') \in \ID \times \ID'$ be the
pairs of identifiers used to create $\id_1''$ and $\id_2''$.
We distinguish on whether $1 \leq i \leq \arity{\OR}$ or $\arity{\OR} < i \leq
\arity{\OR} + \arity{\OR'}$. In the first case, we deduce that exactly one of
$T(\id_1).i$ and $T(\id_2).i$ is $v$, so that in particular $\id_1 \neq
\id_2$.
Thus, by definition of the order in $\times_\gen$, it is easily seen that,
because $\id''_1$ and $\id''_2$ are comparable in $\OR''$,
$\id_1$ and $\id_2$ must compare in the same way in $\OR$, contradicting the
$v$-impartiality of $\OR$.
The second case is symmetric.

We now conclude with the proof of Lemma <ref>:

Let us assume by way of contradiction that there is $n \in \mathbb{N}_+$ and a
query $Q_n$, possibly with $\dupelim$ that captures $\cupcat$.
Let $v \neq v'$ be two distinct
values in $\calD \backslash
\mathbb{N}$, and consider the singleton
po-relation $\OR$ containing one identifier of value $t$ and $\OR'$ containing
one identifier of value $t'$, where
$t$ (resp. $t'$) are tuples of arity $n$ containing
$n$ times the value $v$ (resp. $v'$). Consider the
po-database $D$ mapping
$R$ to $\OR$ and $R'$ to $\OR'$.
Write $\OR'' \defeq Q_n(D)$.
By our assumption, as $\OR'' = (\ID'', T'', {<''})$ must be $\OR \cupcat \OR'$,
it must contain an
identifier $\id \in \ID''$ such that $T''(\id) = t$ and an identifier $\id'
\in \ID''$ such that $T''(\id') = t'$.
Now, as $\OR$ and $\OR'$ are (vacuously) $v$-impartial,
we know by Lemma <ref> that $\OR''$ is $v$-impartial.
Hence, as $n > 0$, taking $i = 1$, as $t \neq t'$ and exactly one of $t.1$ and
$t'.1$ is $v$, we know that $\id$ and $\id'$ must be incomparable in $<''$,
so there is a possible world of $\OR''$ where $\id'$ precedes $\id$.
This contradicts the fact that, as we should have $\OR'' = \OR \cupcat \OR'$,
the po-relation $\OR''$ should have exactly one possible world, namely,
$(t, t')$.

Lemma <ref> and Lemma <ref> conclude the
proof of Theorem <ref>.

We have now defined a semantics on po-relations for each operator. We define a query in the expected way, as a
query built from these operators and from relation names. Calling
schema a set $\calS$ of relation names and arities, with an
attribute name for each position of each relation, we define a
po-database $D$ as having a po-relation $D[R]$ of the correct arity
for each relation name $R$ in $\calS$. For a po-database $D$ and a query $Q$ we denote by $Q(D)$ the po-relation obtained by evaluating
$Q$ over $D$.

§.§ Proof of Proposition <ref>

The po-database $D$ in
Figure <ref> contains information
about restaurants and hotels in Paris: each po-relation has a total order
(from top to bottom) according to customer
ratings from a given travel website, and for brevity we do not represent

Let $Q \defeq \mathit{Rest} \times_\gen
\text{``12''}}(\textit{Hotel}))$.
Its result $Q(D)$ has two possible worlds:

\(
(\langle \textup{G}, 8, \textup{M}, 5\rangle , \langle \textup{G}, 8,
\textup{B}, 8\rangle , \langle \textup{TA}, 5, \textup{M}, 5\rangle
, \langle
\textup{TA}, 5, \textup{B},8\rangle ),\quad
(\langle \textup{G}, 8, \textup{M}, 5\rangle , \langle \textup{TA},
5, \textup{M}, 5\rangle ,\langle \textup{G}, 8, \textup{B}, 8\rangle
, \langle \textup{TA},5, \textup{B},8\rangle ).\)
In a sense, these list relations of hotel–restaurant pairs are
consistent with the order in $D$: we
do not know how to order two pairs, except when both the hotel
and restaurant compare in the same way.
The po-relation $Q(D)$ is represented in
Figure <ref> as a Hasse diagram
(ordered from bottom to top), again writing tuple values instead of tuple
identifiers for brevity.

Consider now $Q'\defeq\Pi (\sigma_{\mathit{Rest}.\mathit{distr} =
\mathit{Hotel}.\mathit{distr}} (Q))$, where $\Pi$
projects out $\mathit{Hotel}.\mathit{distr}$. The possible worlds of $Q'(D)$
are \((\langle \textup{G},\textup{B},8\rangle,$ $\langle
\textup{TA},\textup{M},5\rangle)\) and \((\langle
\textup{TA},\textup{M},5\rangle,$ $\langle
\textup{G},\textup{B},8\rangle)\), intuitively reflecting two
different opinions on the order of restaurant–hotel pairs
in the same district.
Defining $Q''$ similarly to $Q'$ but replacing $\times_\gen$ by
$\times_\lex$ in $Q$, we have $\pw(Q''(D)) =
{\footnotesize (\langle\textup{G},\textup{B},8\rangle,
\langle\textup{TA},\textup{M},5\rangle)}$.

We conclude by observing
that we can efficiently evaluate queries on po-relations:

For any fixed  query $Q$, given a po-database $D$, we
can construct the

$Q(D)$ in polynomial time in the size of $D$ (the polynomial degree depends on $Q$).

We show the claim by a simple induction on the query $Q$.

* If $Q$ is a relation name $R$, $Q(D)$ is obtained
in linear time.

* If $Q$ is a constant expression, $Q(D)$ is obtained in constant

* If $Q=\sigma_\psi(Q')$ or $Q=\Pi_{k_1\dots k_p}(Q')$, $Q(D)$ is
obtained in time linear in $|Q'(D)|$, and we conclude by the induction

* If $Q=Q_1\cup Q_2$ or $Q=Q_1 \times_\lex Q_2$ or
$Q=Q_1\times_\gen Q_2$, $Q(D)$ is obtained in time linear in
$|Q_1(D)|\times|Q_2(D)|$ and we conclude by the induction hypothesis.

We now enrich with order-aware accumulation as the outermost operation, inspired by
right accumulation and iteration in list programming,
and aggregation in
relational databases. We fix a monoid $(\calM, \oplus, \epsilon)$ for
accumulation and define:

For $n \in \mathbb{N}$,
$h: \calD^n \times
\mathbb{N}^* \to \calM$ be a function
called an arity-$n$ accumulation map.
We call $\accum_{h, \oplus}$ an arity-$n$ accumulation operator;
its result $\accum_{h, \oplus}(L)$
on an arity-$n$
list relation $L = (t_1, \ldots, t_n)$ is
$h(t_1, 1) \oplus \cdots \oplus h(t_n,
n)$, and it is $\epsilon$
on an
empty $L$.
For complexity purposes, we always require accumulation operators to be
PTIME-evaluable, i.e.,
given any list relation $L$, we can compute $\accum_{h,
\oplus}(L)$ in PTIME.

The accumulation operator
maps the tuples with $h$ to $\calM$, where accumulation is performed
with $\oplus$.
The map $h$ may use its second argument to take into
account the absolute position of tuples in $L$. In what
follows, we
omit the arity of accumulation
when clear from context.

The language.
We define the
language that contains all queries of the form
$Q=\accum_{h,\oplus}(Q')$, where $\accum_{h,\oplus}$ is an accumulation
operator and $Q'$ is a  query.
The possible results of $Q$ on a
po-database $D$, denoted $Q(D)$, is the set of results obtained by applying
accumulation to each possible world of $Q'(D)$, namely:

For a po-relation $\OR$,
we define:
\(\accum_{h, \oplus}(\OR)
\defeq\{\accum_{h, \oplus}(L) \mid L \in
\pw(\OR)\}\).

Of course, accumulation has exactly one result whenever the operator $\accum_{h,
\oplus}$ does not depend on the order of input tuples:
this covers, e.g., the standard sum, min, max, etc.
we focus
on accumulation operators which depend on the order of tuples (e.g.,
$\oplus$ as concatenation), so there may be more than one accumulation result:

As a first example, let
$\mathit{Ratings}(\mathit{user},\mathit{restaurant},\mathit{rating})$ be an
unordered po-relation describing
the numerical ratings given by users to restaurants, where each user rated each restaurant at most
once. Let $\mathit{Relevance}(\mathit{user})$ be a po-relation
giving a partially-known ordering of users to indicate the relevance of
their reviews. We wish to compute a total rating for each restaurant
which is given by the
sum of its reviews weighted by a
PTIME-computable weight
function $w$. Specifically, $w(i)$ gives a nonnegative weight to the rating of the $i$-th most relevant user.
\(
Q_1 \defeq
\accum_{h_1,+}(\sigma_\psi(\mathit{Relevance}\times_{\lex}\mathit{Ratings}))\)
where we set \(h_1(t,n) \defeq t.\mathit{rating} \times w(n)\), and where
$\psi$ is the tuple predicate:
\(
\mathit{restaurant}=\text{``Gagnaire''}\land\mathit{Ratings}.\mathit{user}=
\mathit{Relevance}.\mathit{user}
\).
The query $Q_1$ gives the total rating of Gagnaire, and each
possible world of $\mathit{Relevance}$ may lead to a different accumulation result.

As a second example, consider an unordered po-relation
$\mathit{HotelCity}(\mathit{hotel}, \mathit{city})$ indicating in which
city each hotel is located, and consider a po-relation
$\mathit{City}(\mathit{city})$ which is (partially) ranked by a
criterion such as interest level, proximity, etc. Now consider the
\(
Q_2 \defeq \accum_{h_2,\mathrm{concat}}(
\Pi_{\mathit{hotel}}(
Q_2'))\), where \(Q_2' \defeq \sigma_{\mathit{City}.\mathit{city} =
\mathit{HotelCity}.\mathit{city}}(
\mathit{City}\times_{\lex}\mathit{HotelCity})\), where
$h_2(t,n)\defeq t$, and where “$\mathrm{concat}$” denotes standard string concatenation.
$Q_2$ concatenates the hotel names according to the preference order on the city
where they are located, allowing any possible order between hotels of the same city and
between hotels in incomparable cities.

§ POSSIBILITY AND CERTAINTY

Evaluating a or query $Q$ on a po-database $D$ yields a set of possible
results: for , it yields an explicit set of accumulation results, and
for , it yields a po-relation that represents a set of possible worlds (list
The uncertainty among the results may be due to the order of the input relations being partial, due to
uncertainty yielded by the query, or both. In some cases, there is only one
possible result, i.e., a certain answer. In other cases, we may wish
to examine multiple possible answers. We thus define:

Let $Q$ be a query, $D$ be a po-database, and $L$ a list
relation. The possibility problem () asks
if $L \in \pw(Q(D))$, i.e.,
if $L$ is a possible result.
The certainty
problem () asks if $\pw(Q(D)) = \{L\}$,
i.e., if $L$ is the only possible result.

if $Q$ is a query with
accumulation monoid $\calM$, for a result $v
\in \calM$, the problem asks whether $v \in Q(D)$, and asks
whether $Q(D) = \{v\}$.

For , our definition follows the usual notion of
possible and certain answers in data integration
[28] and incomplete information [30].
For ,
we ask for possibility or certainty of an entire output list
instance possibility and certainty [3].
We now justify that these notions are useful and discuss more “local” alternatives.

First, as we exemplify below,
the output of a query may be certain even for complex
queries and uncertain input.
It is important to identify such cases and present the user with the certain
answer in full,
like order-by query results in current DBMSs.
Our problem is useful for this task, because we can use it to decide if a
certain output exists, and if yes, we can compute it in PTIME (by choosing any
linear extension).
However, is a challenging problem to solve, because of duplicate values
(see “” below).

Consider the po-database $D$ of Figure <ref> with the po-relations
$\mathit{Rest}$ and $\mathit{Hotel}_2$.
To find recommended pairs of hotels and restaurants in the same
district, the user can write
$Q \defeq \sigma_{\mathit{Rest}.\mathit{distr}=\mathit{Hotel}_2.\mathit{distr}}
(\mathit{Rest} \times_{\dir} \mathit{Hotel}_2)$. Evaluating $Q(D)$ yields only
one possible world, namely, the list relation $(\langle G,8,B,8\rangle,
\langle \mathit{TA},5,M,5\rangle)$, which is a certain result.

This could also happen with larger input relations. Imagine for example that
we join hotels and restaurants to find pairs of a hotel and a restaurant
located in that hotel. The result can be certain if the relative ranking of the
hotels and of their restaurants agree.

If there is no certain answer, deciding possibility of an instance may be
considered as “best effort”. It can be useful, e.g., to check if a
list relation (obtained from another source) is consistent with a query result. For
example, we may wish to check if a website's
ranking of
hotel–restaurant pairs is
consistent with the preferences expressed in its rankings for hotels and
restaurants, to detect when a pair is ranked higher than its components would

When there is no overall certain answer, or when we want to check the
possibility of some aggregate property of the relation, we can use a query.
In particular, in addition to the applications of Example <ref>,
accumulation allows us to encode alternative notions of and for  queries, and to express them as and for . For example,
instead of possibility or certainty for a full relation, we can express
possibility or certainty of the location[Remember that the existence of a tuple is not
order-dependent and thus vacuous in our setting.]
of particular tuples of interest:

With accumulation we can model
position-based selection queries. Consider for instance a top-$k$
operator on list relations, which retrieves a list relation of the first $k$ tuples. For a
po-relation, the set of results is all possible such list relations. We can
implement top-$k$ as $\accum_{h_3,\concat}$
with $h_3(t, n)$ being $(t)$ for $n \leq k$ and $\epsilon$ otherwise,
and with $\text{concat}$ being list concatenation. We can similarly compute select-at-$k$, i.e., return the
tuple at position $k$, via $\accum_{h_4,\concat}$
with $h_4(t, n)$ being $(t)$ for $n=k$ and $\epsilon$ otherwise.

Accumulation can also be used for a tuple-level comparison.
To check whether
the first occurrence of a tuple $t_1$ precedes any occurrence of
$t_2$, we define $h_5$ for all $n\in\NN$ by $h_5(t_1,n) \defeq \top$, $h_5(t_2,n) \defeq \bot$ and
$h_5(t,n)\defeq\epsilon$ for $t \neq t_1,t_2$, and a monoid operator $\oplus$ such
that $\top\oplus\top=\top\oplus\bot=\top$, $\bot\oplus
\bot=\bot\oplus\top=\bot$:
assuming that $t_1$ and $t_2$ are both present, then the result is $\top$ if
the first occurrence of $t_1$ precedes any occurrence of $t_2$, and it
is $\bot$ otherwise.

We study the complexity of these variants in Section <ref>. We now
give examples of their use:

Consider $Q=\Pi_{\mathit{distr}}(
\sigma_{\mathit{Rest}.\mathit{distr}=\mathit{Hotel}.\mathit{distr}}
(\mathit{Rest} \times_{\dir} \mathit{Hotel}))$, which computes ordered
recommendations of districts including both hotels and restaurants. Using
accumulation as in Example <ref>,
the user can compute the best district to stay in with
If $Q'$ has a certain answer,
there is a dominating
hotel–restaurant pair in this district, which answers the user's need.
If there is no certain answer, allows the user to
the possible top-$1$ districts.

We can also use and for queries to restrict attention to
tuples of interest. If the user hesitates between districts $5$ and $6$, they
can apply tuple-level comparison  to see
whether the best pair of district $5$ may be better (or is always better) than
that of $6$.

Technical difficulties.
The main challenge to solve and
for a query $Q$ on an input po-database $D$ is that the tuple values of
the desired result $L$ may
occur multiple times in the po-relation $Q(D)$, making it hard to match $L$ and
In other words, even though we may compute the po-relation $Q(D)$ in PTIME (by
Proposition <ref>) and present it to the user, they still cannot
easily “read” possible and certain answers out of the po-relation:

Consider a po-relation $\OR = (\ID, T, {<})$ with
$\ID = \{\id_{\mathrm{a}}, \allowbreak\id_{\mathrm{b}},
\allowbreak\id_{\mathrm{c}},
\allowbreak\id_{\mathrm{d}}, \allowbreak\id_{\mathrm{e}},
\allowbreak\id_{\mathrm{f}}\}$, with
$T(\id_{\mathrm{a}}) \defeq \langle\text{Gagnaire}, \text{fr}\rangle$,
$T(\id_{\mathrm{b}}) \defeq
\langle\text{Italia}, \text{it}\rangle$,
$T(\id_{\mathrm{c}}) \defeq \langle\text{TourArgent}, \text{fr}\rangle$,
$T(\id_{\mathrm{d}}) \defeq
\langle\text{Verdi}, \text{it}\rangle$, $T(\id_{\mathrm{e}}) \defeq
\langle\text{Tsukizi}, \text{jp}\rangle$,
$T(\id_{\mathrm{f}}) \defeq \langle\text{Sola}, \text{jp}\rangle$,
and with $\id_{\mathrm{a}} < \id_{\mathrm{c}}$, $\id_{\mathrm{b}} <
\id_{\mathrm{c}}$, $\id_{\mathrm{c}} <
\id_{\mathrm{e}}$, $\id_{\mathrm{d}} < \id_{\mathrm{e}}$, and
$\id_{\mathrm{d}} < \id_{\mathrm{f}}$.
Intuitively, $\OR$ describes a preference relation over restaurants,
with their name and the type of their cuisine.
Consider the query $Q \defeq \Pi(\OR)$ that projects $\OR$ on type; we
illustrate the result (with the original identifiers) in Figure <ref>.
Let $L$ be the list
relation $(\text{it}, \text{fr}, \text{jp}, \text{it}, \text{fr},
\text{jp})$, and consider
for $Q$, $\OR$, and $L$.

We have that $L \in \pw(Q(\OR))$, as shown by the linear extension
$\id_{\mathrm{d}} <' \id_{\mathrm{a}} <' \id_{\mathrm{f}} <' \id_{\mathrm{b}} <'
\id_{\mathrm{c}} <' \id_{\mathrm{e}}$
of $<$. However, this is hard to see, because
each of it, fr, jp appears more than once in the
candidate list as well as in the po-relation; there are thus multiple
ways to “map” the elements of the candidate list to those of the po-relation, and only some of these mappings lead to the existence of a corresponding linear extension.
It is also challenging to check if $L$ is a
certain answer: here, it is not, as there are other possible answers,
e.g.: $(\text{it},
\text{fr}, \text{fr}, \text{it}, \text{jp}, \text{jp})$.

For queries, this technical difficulty is even accrued because of the
need to figure out the possible ways in which the desired accumulation result
can be obtained.

§ GENERAL COMPLEXITY RESULTS

We summarize the complexity results of
Sections <ref>–<ref> in Table <ref>.

We have defined the and query languages, and defined and
motivated the problems and . We now start the study of their complexity, which is the main technical
contribution of our paper. We will always study their data complexity[In combined complexity, with $Q$ part of
the input, and are easily seen to be respectively NP-hard and coNP-hard, by reducing from
the evaluation of Boolean conjunctive queries (which is NP-hard in data
complexity [1]) even without order.],
where the query $Q$ is fixed: in particular, for , the accumulation map and
monoid, which we assumed to be PTIME-evaluable, is fixed as part of the query,
though it is allowed to be infinite. The input to and for the fixed
query $Q$ is the
po-database $D$ and the candidate result (a list relation for , an
accumulation result for ).

We start with , which we show
to be NP-complete in general.

§.§ Proofs of Theorems <ref> and <ref>

The  problem is in NP for any or query. Further, there exists a query and a query for which the problem is

The membership for in NP is clear: guess a linear extension and check that
it realizes the candidate possible result.
For hardness, as in previous work
[44], we reduce from the UNARY-3-PARTITION
problem [19]: given a number $B$ and $3m$ numbers written in unary,
decide if they can be partitioned in triples that all sum to $B$.
We reduce this to for the identity query, on an arity-1 input
po-relation where each input number $n$ is represented as a chain of $n+2$
elements. The first and last elements of each chain are respectively called
start and end markers, and elements of distinct
chains are pairwise
incomparable. The candidate
possible world $L$ consists of $m$ repetitions of the following pattern: three start markers, $B$
elements, three end markers. A linear extension achieves $L$ iff the
triples matched by $<$ to each copy of the pattern are a solution to
UNARY-3-PARTITION, hence for $Q$ is NP-hard.
This implies hardness for , when accumulating
with the identity map and concatenation (so that any list relation is mapped
to itself).

In fact, as we will later point out,
hardness holds even for quite a restrictive setting, with a more intricate proof: see
Theorem <ref>.

We show that is coNP-complete for :

The problem is in coNP for any query, and there is a
query for which it is coNP-complete.

Again, membership is immediate. We show hardness of by studying a
query $Q_{\a}$ that checks if two input
po-relations $\OR$ and $\OR'$ have some common possible world: $Q_{\a}$
does so
so by testing if one can alternate between elements of $\OR$ and
$\OR'$ with the same label, using accumulation in the
transition monoid of a deterministic finite automaton.
We show hardness of for $Q_{\a}$ (as in the previous result), and
further ensure that $Q_{\a}$ always has at most two possible
accumulation results, no matter the input. Hence, for $Q_{\a}$ reduces
to the negation of for $Q_{\a}$, so that is also hard.

For queries, however, we show
that is in PTIME.
As we will see later, this follows from the tractability of for on
cancellative monoids (Theorem <ref>).

§.§ Proof of Theorem <ref>

is in PTIME for any  query.

Let $Q$ be the query of interest,
and let $k \in \mathbb{N}$ be its arity: let $(\calM_k, \oplus)$ be the
cancellative monoid (see Definition <ref>) and $h_k$ be the accumulation map obtained from Lemma <ref>. By
Lemma <ref>, we know that for $Q$ is equivalent to for
the query $Q' \defeq \accum_{h,\oplus}$, which is clearly
constructible in PTIME.

Now, by Theorem <ref> (proven in
Appendix <ref>), we know that the problem is in
PTIME for $Q'$, because it performs accumulation in a cancellative monoid.
Hence, using the PTIME reduction above, we deduce that the problem for $Q$ is in PTIME
as well.

We next identify further tractable cases, first for  and then for .

§ TRACTABLE CASES FOR POSS ON POSRA QUERIES

We show that is tractable for queries if we restrict the allowed
operators and if we bound some order-theoretic parameters of the input po-database,
such as poset width.

We call the fragment of that disallows the
$\times_{\dir}$ operator, but allows all other operators (including
$\times_{\lex}$). We also define that disallows $\times_{\lex}$ but
not $\times_{\dir}$.

Totally ordered inputs.

§.§ Totally Ordered Inputs

We start by the natural case where the individual
po-relations are totally ordered, i.e., their order relation is a total
order (so they actually represent a list relation).
This applies
to situations where we integrate data from multiple sources that are
certain (totally ordered), and where uncertainty only results
from the integration query
(so that the result may still have exponentially many
possible worlds, e.g., the union of two total orders has
exponentially many possible interleavings).
In a sense, the $\times_\dir$ operator is the one introducing the most
uncertainty and “complexity” in the result, so we
consider the fragment of queries without
$\times_{\dir}$, and show:

§.§.§ Tractability Result: Proof of
Theorems <ref> and <ref>

The point of
restricting to queries is that they can only make the
width increase in a way that depends on the width of the input relations, but
not on their size:

Let $k \geq 2$ and $Q$ be a query. Let $k' =
For any po-database $D$ of width $\leq k$, the po-relation $Q(D)$ has width $\leq k'$.

We prove by induction on the query $Q$ that one can compute a bound on
the width of the output of the query as a function of the bound $k$ on the
width of the inputs. For the base cases:

* Input po-relations have width $\leq k$.

* Constant po-relations (singletons and constant chains) have width $1$.

For the induction step:

* Given two po-relations $\OR_1$ and $\OR_2$ with bounds $k_1$ and $k_2$, their
union $\OR_1 \cupgen \OR_2$ clearly has bound $k_1 + k_2$, as any antichain in the union must be
the union of an antichain of $\OR_1$ and of an antichain of $\OR_2$.

* Given a po-relation $\OR_1$ with bound $k_1$, applying a projection or
selection to $\OR_1$ cannot make the width increase.

* Given two po-relations $\OR_1$ and $\OR_2$ with bounds $k_1$ and $k_2$, their
product $\OR \defeq \OR_1 \times_{\lex} \OR_2$ has bound $k_1 \cdot k_2$. To show
this, consider any set $A$ of $\OR$ containing strictly more than $k_1
\cdot k_2$ identifiers, which we see as
pairs of an identifier of $\OR_1$ and an identifier of $\OR_2$. It is immediate
that one of the following must hold:

* Letting $S_1 \defeq \{u \mid \exists v, (u, v) \in A\}$, we have
$\card{S_1} > k_1$

* There exists $u$ such that, letting $S_2(u) \defeq \{v \mid (u, v) \in
A\}$, we have $\card{S_2} > k_2$

Informally, when putting $> k_1 \cdot k_2$ values in buckets (the value of
their first component), either $> k_1$ different buckets are used, or
there is a bucket containing $> k_2$ elements.

In the first case, as $S_1$ is a subset of identifiers of $\OR_1$ of cardinality
$> k_1$ and $\OR_1$ has width $k_1$, it cannot be an antichain, so it must
contain two comparable elements $u_1 < u_2$, so that, considering $v_1$
and $v_2$ such that $a_1 = (u_1, v_1)$ and $a_2 = (u_2, v_2)$ are in $A$,
we have by definition of $\times_\lex$ that $a_1 <_\OR a_2$, so that
$A$ is not an antichain of $\OR$.

In the second case, as $S_2(u)$ is a subset of identifiers of $\OR_2$ of
cardinality $> k_2$ and $\OR_2$ has width $k_2$, it cannot be an antichain,
so it must contain two comparable elements $v_1 < v_2$. Hence, considering
$a_1 = (u, v_1)$ and $a_2 = (u, v_2)$ which are in $A$, we have
$a_1 <_\OR
a_2$, and again $A$ is not an antichain of $\OR$.

Hence, we deduce that no set of cardinality $> k_1 \cdot k_2$
of $\OR$ is an
antichain, so that $\OR$ has width $\leq k_1 \cdot k_2$, as desired.

Letting $o$ be the number of product operators in $Q$ plus the number of
union operators, it is now clear that we can take $k' = k^{o + 1}$.
Indeed, po-relations with no product or union operators have width at most $k$
(using that $k \geq 1$). As projections and selections do not change the
width, the only operators to consider are product and union. If $Q_1$ has
$o_1$ operators and $Q_2$ has $o_2$ operators, bounding by induction the width
of $Q_1(D)$ to be $k^{o_1 + 1}$ and $Q_2(D) = k^{o_2 + 1}$, for $Q = Q_1 \cup
Q_2$, the number of operators is $o_1 + o_2 + 1$, and the new bound is $k^{o_1
+ 1} + k^{o_2 + 1}$, which as $k \geq 2$ is less than $k^{o_1 + 1 + o_2 + 1}$,
that is, $k^{(o_1 + o_2 + 1) + 1}$. For $\times_\lex$, we proceed in the
same way and directly obtain the $k^{(o_1 + o_2 + 1) + 1}$ bound. Hence, we
can indeed take $k' = k^{\card{Q}+1}$.

From this, we will deduce is tractable for
queries when the input po-database consists of relations of
bounded width.
prove Theorem <ref>, which clearly generalizes
Theorem <ref>. We will prove both the result for queries
and its extension to queries with finite accumulation
(Theorem <ref>).

is in PTIME for queries if
input po-relations are totally ordered.

In fact, we can show tractability for
relations of bounded
poset width:

An antichain in a po-relation $\OR=(\ID,T,<)$ is a set
$A\subseteq\ID$ of pairwise
incomparable tuple identifiers.
width of $\OR$ is the size of its largest
The width of a po-database is the maximal width of its po-relations.

In particular, totally ordered po-relations have width $1$, and
unordered po-relations have a width equal to their size (number of
tuples); the width of a po-relation can be computed in
PTIME [18].
Po-relations of low width are a common practical case: they cover, for instance,
po-relations that are totally ordered except for a few tied identifiers at each
level. We show:

For any fixed $k \in \NN$ and fixed query $Q$,
the problem for $Q$ is in PTIME when
all po-relations of the input
po-database have width $\leq k$.

As $\times_{\dir}$ is disallowed,
we can show that the po-relation $\OR \defeq Q(D)$
has width $k'$ depending only on $k$ and the query $Q$ (but not on $D$). We can then compute in PTIME a
chain partition of $\OR$
[13, 18], namely, a decomposition
of $\OR$ in totally ordered chains, with additional order constraints between
them. This allows us to
apply a dynamic algorithm to decide : the state of the algorithm is the position on
the chains. The number of states is polynomial with degree $k'$, which is
a constant when $Q$ and $k$ are fixed.

Let $\OR \defeq Q(D)$ be the po-relation obtained by evaluating the query $Q$
of interest on the input po-database $D$, excluding the
accumulation operator if any (so we are evaluating a query).
We can compute this in PTIME using
Proposition <ref>. Letting $k'$ be the constant (only depending on $Q$ and $k$)
given by Proposition <ref>, we know that
$w(\OR) \leq k'$.

We first show the tractability of and for queries with
finite accumulation, which amounts to applying directly a finite accumulation
operator to $\OR$. We then deal with queries, which amounts to solving
directly and on the po-relation $\OR$.

queries with finite accumulation.

It suffices to show the following rephrasing of the result:

For any constant $k' \in \mathbb{N}$,
and accumulation operator $\accum_{h, \oplus}$ with
finite domain, we can compute in PTIME,
for any input po-relation $\OR$ such that $w(\OR) \leq k'$,
the set $\accum_{h, \oplus}(\OR)$.

Indeed, by what precedes, we can assume that the query has already been
evaluated to a po-relation; further, once the possible results are determined, it is immediate
to solve possibility and certainty.

To take care of this task, we need the following notions:

A chain partition of a poset $P$ is a partition $\mathbf{\Lambda} =
\ldots, \Lambda_n)$ of the elements of $P$, i.e., $P = \Lambda_1 \sqcup \cdots \sqcup
\Lambda_n$, such that each $\Lambda_i$ is a total order.
(However, $P$ may feature comparability relations not present in the
i.e., relating elements in $\Lambda_i$ to elements in $\Lambda_j$ for $i \neq j$.) The
width of the partition $\mathbf{\Lambda} = (\Lambda_1, \ldots,
\Lambda_n)$ is $n$.

Given a poset $P$, an order ideal of $P$ is a subset $S$ of $P$ such that,
for all $x, y \in P$, if $x < y$ and $y \in S$ then $x \in S$.

We also need the following known results:

Any poset $P$ has a chain partition of width $w(P)$.

For any poset $P$, we can compute in PTIME a chain partition of $P$ of
minimal width.

We now prove Theorem <ref>:

Consider a po-relation $\OR=(ID,T,{<})$, with underlying
poset $P=(ID,{<})$. Using Theorems <ref>
and Theorem <ref>, compute in PTIME a chain partition $\mathbf{\Lambda}$
of $P$ of width $k'$.
For $1 \leq i \leq k'$,
write $n_i \defeq \card{\Lambda_i}$, and for $0 \leq j \leq n_i$, write
j}$ to denote the subset of $\Lambda_i$ containing the first $j$ elements of the
chain (in particular $\Lambda_i^{\leq 0} = \emptyset$).

We now consider all vectors of the form $(m_1, \ldots, m_{k'})$, with
$0 \leq m_i \leq n_i$, of which there are polynomially many (there are $\leq
\card{\OR}^{k'}$, where $k'$ is constant). To each such vector $\mathbf{m}$ we
associate the subset $s(\mathbf{m})$ of $P$ consisting of
$\bigsqcup_{i=1}^{k'} \Lambda_i^{\leq m_i}$.

We call such a vector $\mathbf{m}$ sane if $s(\mathbf{m})$ is an
order ideal. (While $s(\mathbf{m})$ is always an order ideal of the subposet
of the comparability relations within the chains, it may not be an order
ideal overall because of
the additional comparability relations across the chains that may be
featured in $P$.) For each vector
$\mathbf{m}$, we can check in PTIME whether it is sane, by materializing
$s(\mathbf{m})$ and checking that it is an ideal for each comparability
relation (of which there are $O(\card{P}^2)$).

By definition, for each sane vector $\mathbf{m}$, $s(\mathbf{m})$
is an ideal. We now observe that the converse is true, and that for every
ideal $S$ of $P$, there is a sane vector $\mathbf{m}$ such that
$s(\mathbf{m}) = S$. To see why, consider an ideal $S$, and determine for
each chain $\Lambda_i$ the last element of the chain present in the ideal; let
$m_i$ be its position in the chain. $S$ then does not include any
element of $\Lambda_i$ at a later position, and because $\Lambda_i$ is a chain it must
include all elements before, hence, $S \cap \Lambda_i = \Lambda_i^{\leq m_i}$. As
$\mathbf{\Lambda}$ is a chain partition of $P$, this entirely determines $S$. Thus we
have indeed $S = s(\mathbf{m})$, and the fact that $s(\mathbf{m})$ is sane
is witnessed by $S$.

For any sane vector $\mathbf{m}$, we now write $t(\mathbf{m}) \defeq \accum_{h,
\oplus}(T(s(\mathbf{m})))$ (recall that $T$ maps elements of the
poset to tuples, and can therefore naturally be extended to map
sub-posets to sub-po-relations). This is a subset of the
accumulation domain
$\calM$ (since the latter is finite, this subset is of constant
size). It is immediate that $t((0, \ldots, 0)) = \{\epsilon\}$, the neutral
element of the accumulation monoid, and that
$t((n_1, \ldots, n_{k'})) = \accum_{h, \oplus}(\OR)$ is our desired answer. Denoting by $e_i$ the vector
consisting of $n-1$ zeroes and a $1$ at position $i$, for $1 \leq i
\leq k'$,
we now observe that, for any sane vector $\mathbf{m}$, we have:

\begin{equation}
\label{eqn:tprop}
t(\mathbf{m}) = \bigcup_{1 \leq i \leq k'} \left\{
v \oplus h\left(T(\Lambda_i[m_i]), \sum_{i'} m_{i'}\right)
\:\middle|\: v \in t(\mathbf{m} - e_i)\right\}
\end{equation}

where the operator “$-$” is the component-by-component integer difference
on tuples,
and where we define $t(\mathbf{m} - e_i)$ to be $\emptyset$ if $\mathbf{m} -
e_i$ is not
sane or if one of the coordinates of $\mathbf{m} - e_i$ is $< 0$.
Equation <ref> holds because
any linear extension of $s(\mathbf{m})$ must end with one of the maximal
elements of $s(\mathbf{m})$, which must be one of the $\Lambda_i[m_i]$ for $1 \leq
i \leq m$ such that $m_i \geq 1$, and the preceding elements must be a linear
extension of the ideal where this element was removed (which must be an
ideal, i.e., $\mathbf{m} - e_i$ must be sane, otherwise the removed
$\Lambda_i[m_i]$ was not actually maximal because it was comparable to (and
smaller than) some $\Lambda_j[m_j]$ for $j \neq i$). Conversely, any sequence
constructed in this fashion is indeed a linear extension. Thus, the possible
accumulation results are computed according to this characterization of the
linear extensions. We store with each possible accumulation result a
witnessing totally ordered relation from which it can be computed in PTIME,
namely, the linear extension prefix considered in the previous reasoning,
so that we can use the PTIME-evaluability of the underlying monoid to ensure
that all computations of accumulation results can be performed in PTIME.

This last equation allows us to compute $t(n_1, \ldots, n_{k'})$ in PTIME by a
dynamic algorithm, enumerating the vectors (of which there are polynomially
many) in lexicographical order, and computing their image by $t$ in PTIME
according to the equation above, from the base case $t((0, \ldots, 0)) =
\epsilon$ and from the previously computed values of $t$. Hence, we have
computed $\accum_{h, \oplus}(\OR)$ in PTIME, which concludes the proof.

First note that, for queries with no accumulation, we cannot reduce and
to the case with accumulation, because the monoid of tuples under
concatenation does not satisfy the hypothesis of finite accumulation. Hence, we
need specific arguments to prove Theorem <ref> for queries with no

Recall that the problem is in PTIME for such queries by
Theorem <ref>, so it suffices to study the case of .
We do so by the following result, which is obtained by adapting the proof of
Theorem <ref>:

For any constant $k \in \mathbb{N}$,
we can determine in PTIME,
for any input po-relation $\OR$ such that $w(\OR) \leq k$
and list relation $L$,
whether $L \in \pw(\OR)$.

The proof of Theorem <ref> adapts because of
the following: to decide instance possibility, we do not need to compute
all possible accumulation results (which may be exponentially
numerous), but it suffices to store, for each sane
vector $\mathbf{m}$, whether the prefix of the correct length of the candidate
possible world can be achieved in the order ideal $s(\mathbf{m})$.
More formally, we define $t((0, \ldots, 0))
\defeq \text{true}$, and:

\[
t(\mathbf{m}) \defeq \bigvee_{1 \leq i \leq k'} \left(
t(\mathbf{m} - e_i) \wedge T(L_i[m_i]) = L\left[1 + \sum_{i'} m_{i'}\right]\right)
\]

where $L$ is the candidate possible world. We conclude by a dynamic
algorithm as in Theorem <ref>.

This concludes the proof of Theorem <ref>, and, as an
corollary, of Theorem <ref>.

We last justify our choice of disallowing the $\times_{\dir}$ product. Indeed, if we
allow $\times_{\dir}$, then is hard on totally ordered po-relations, even if we disallow

§.§.§ Hardness result: Proof of Theorem <ref>

There is a query for which the problem is NP-complete
even when the input po-database is restricted to consist only of totally ordered

Disallowing product.

§.§ Disallowing Product

We have shown the tractability of when disallowing the $\times_\gen$
operator, when the input po-relations are assumed to have bounded width.
We now show that if we disallow both kinds of product, we obtain tractability for
more general input po-relations. Specifically, we will allow input po-relations
that are almost totally ordered, i.e., have bounded width; and we will also
allow input po-relations that are almost unordered, which we measure using a new
order-theoretic notion of ia-width. The idea of ia-width is to decompose
the relation in classes of indistinguishable sets of incomparable elements:

Given a poset $P = (\ID, <)$, a subset $A \subseteq \ID$ is an
indistinguishable antichain if it is both an antichain (there are no
$x, y \in A$ such that $x < y$) and an indistinguishable set (or
interval [17]): for all
$x, y \in A$ and $z \in \ID \backslash A$,
we have $x < z$ iff $y < z$, and $z < x$ iff $z < y$.

An indistinguishable antichain partition (ia-partition) of $P$ is a
partition $\ID = A_1 \sqcup \cdots \sqcup A_n$ of $\ID$ such that each $A_i$
for $1 \leq i \leq n$ is an indistinguishable antichain. The
cardinality of the partition is $n$.
The ia-width of $P$ is the
cardinality of its smallest ia-partition.
The ia-width of a po-relation is that of its underlying poset,
and the ia-width of a po-database is the maximal ia-width of its po-relations.

Hence, any po-relation $\OR$ has ia-width at most $\card{\OR}$, with the trivial
ia-partition consisting of singleton indistinguishable antichains, and unordered
po-relations have an ia-width of 1.
Po-relations may have low ia-width in practice if order is completely
unknown except for a
few comparability pairs given by users, or when they consist of objects from a
constant number of types that are ordered based only on some order on the types.

We can now state our tractability result when disallowing both kinds of
products, and allowing both bounded-width and bounded-ia-width relations. For
instance, this result allows us to
combine sources whose order is fully unknown or irrelevant, with
sources that are completely ordered (or almost totally ordered).

§.§.§ Tractability Result: Proof of Theorem <ref>

For any fixed $k \in \mathbb{N}$
and fixed query $Q$,
the problem for $Q$ is in PTIME
when all po-relations of the input po-database
have either ia-width
$\leq k$ or width $\leq k$.

We start by making a simple observation:

Any query $Q$ without any product can be rewritten as a union of
projections of selections of a constant number of input relations and constant

This follows from the fact that, for the semantics that we have defined for
operators, the following is clear:
selection commutes with union, selection commutes with projection, and
projection commutes with union. Hence, we can perform the desired rewriting.

We can thus rewrite the input query using this lemma. The idea is that we will
evaluate the query in PTIME using Proposition <ref>, argue that
the width bounds are preserved using Proposition <ref>, and compute a
chain partition of the relations using Theorem <ref> and
Theorem <ref>. However, we first
need to show analogues of Proposition <ref>,
Theorem <ref>, and Theorem <ref> for the new notion of ia-width. We first show the
analogue of Proposition <ref> for the case without product:

Let $k \geq 2$ and $Q$ be a query. Let $k' \colonequals
\max(k,q) \times \card{Q}$, where $\card{Q}$ denote the number of
symbols of $Q$, and where $q$ denotes the largest value such that
$\ordern{q}$ appears in $Q$. For any po-database $D$ of ia-width $\leq
k$, the po-relation $Q(D)$ has ia-width $\leq k'$.

We first show by induction on $Q$ that the ia-width of the query output can be
bounded as a function of the bound $k$ on the ia-width of the query inputs.
For the base cases:

* The input relations have ia-width at most $k$.

* The constant relations have ia-width $\leq q$ with the trivial
ia-partition consisting of singleton classes.

For the induction step:

* Projection clearly does not change ia-width.

* Selection may only decrease the ia-width. Indeed, consider an
ia-partition of the input po-relation, apply the selection to each class,
and remove the classes that became empty. The number of classes has not
increased, and it is clear that the result is still an ia-partition of the
output po-relation.

* The union of two relations
with ia-width $k_1$ and $k_2$ has ia-width at most $k_1 + k_2$. Indeed, we can
obtain an ia-partition for the union as the union of ia-partitions for the
input relations.

Second, we see that the bound $k' \colonequals \max(k,q) \times \card{Q}$ is
clearly correct, because the base cases have ia-width $\leq \max(k, q)$ and
the worst operators are unions, which amount to summing the ia-width bounds on
all inputs, of which there are $\leq \card{Q}$. So we have shown the desired

We next show that, like chain partitions for bounded-width po-relations, we can
efficiently compute an ia-partition for a bounded-ia-width po-relation:

The ia-width of any poset, and a corresponding ia-partition, can be computed
in PTIME.

To show this result, we need two preliminary observations about
indistinguishable antichains:

For any poset $(\ID, <)$ and indistinguishable antichain $A$, for any $A'
\subseteq A$, then $A'$ is an indistinguishable antichain.

Clearly $A'$ is an antichain because $A$ is. We show that it is an
indistinguishable set. Let $x, y \in A'$ and $z \in \ID \backslash A'$, and show
that $x < z$ implies $y < z$ (the other three implications are symmetric). If
$z \in \ID \backslash A$, we conclude because $A$ is an indistinguishable set.
If $z \in A \backslash A'$, we conclude because, as $A$ is an antichain, $z$
is incomparable both to $x$ and to $y$.

For any poset $(\ID, <)$ and indistinguishable antichains $A_1, A_2 \subseteq
\ID$ such that $A_1 \cap A_2 \neq \emptyset$, the union $A_1 \cup A_2$ is an
indistinguishable antichain.

We first show that $A_1 \cup A_2$ is an indistinguishable set.
Let $x, y \in A_1 \cup A_2$ and
$z \in \ID \backslash (A_1 \cup A_2)$, assume that $x < z$ and show that $y <
z$ (again the other three implications are symmetric).
As $A_1$ and $A_2$ are indistinguishable sets, this is immediate unless $x
\in A_1 \backslash A_2$ and $y \in A_2 \backslash A_1$, or vice-versa. We
assume the first case as the second one is symmetric. Consider
$w \in A_1 \cap A_2$. As $x < z$, we know that $w < z$ because $A_1$ is an
indistinguishable set, so that $y < z$ because $A_2$ is an indistinguishable
set, which proves the desired implication.

Second, we show that $A_1 \cup A_2$ is an antichain.
Proceed by contradiction, and let $x, y \in
A_1 \cup A_2$ such that $x < y$. As $A_1$ and $A_2$ are antichains, we must
have $x \in A_1 \backslash A_2$ and $y \in A_2 \backslash A_1$, or vice-versa.
Assume the first case, the second case is symmetric. As $A_1$ is an
indistinguishable set, letting $w \in A_1 \cap A_2$,
as $x < y$ and $x \in A_1$, we have $w < y$. But $w \in A_2$ and
$y \in A_2$, which is impossible because $A_2$ is an antichain. We have
reached a contradiction, so we cannot have $x < y$. Hence, $A_1 \cup A_2$ is
an antichain, which concludes the proof.

We can now show Proposition <ref>:

Start with the trivial partition in singletons (which is an
ia-partition), and for every pair of items, see if their
current classes can be merged (i.e., merge them, check in PTIME if it
is an antichain, and if it is an indistinguishable set, and undo the merge if
it is not). Repeat the process
while it is possible to merge classes (i.e., at most linearly many times).
This greedy process concludes in PTIME and yields an ia-partition
$\mathbf{A}$. Let $n$ be its cardinality.

Now assume that there is an ia-partition $\mathbf{A'}$ of cardinality $m < n$.
There has to be a class $A'$ of $\mathbf{A'}$
which intersects two different classes $A_1 \neq A_2$ of
the greedy ia-partition $\mathbf{A}$, otherwise $\mathbf{A'}$ would be a refinement
of $\mathbf{A}$ so we would have $m \geq n$.
Now, by Lemma <ref>,
$A \cup A_1$ and $A \cup A_2$, and hence
$A \cup A_1 \cup A_2$, are
indistinguishable antichains.
By Lemma <ref>,
this implies that $A_1 \cup A_2$ is an indistinguishable
antichain. Now, when constructing the greedy ia-partition $\mathbf{A}$,
the algorithm has
considered one element of $A_1$ and one element of $A_2$, attempted to merge
the classes $A_1$ and $A_2$,
and, since it has not merged them in $\mathbf{A}$, the union $A_1 \cup A_2$
cannot be an indistinguishable antichain. We have reached a contradiction, so
we cannot have $m < n$, which concludes the proof.

We have shown the preservation of ia-width bounds through selection, projection,
and union (Proposition <ref>), and shown how to compute an
ia-partition in PTIME (Proposition <ref>). Let us now return
to the proof of Theorem <ref>. We use
Lemma <ref> to rewrite the query to a union of projection of
selections. We evaluate the selections and projections in PTIME by
Proposition <ref>. As union is clearly associative and commutative,
we evaluate the union of relations of width $\leq k$, yielding $\OR$, and the union of those
of ia-width $\leq k$, yielding $\OR'$. The first result $\OR$ has bounded width thanks to
Proposition <ref>, and we can compute a chain partition of it in PTIME using
Theorem <ref> and Theorem <ref>. The second result has bounded ia-width thanks to
Proposition <ref>, and we can compute an ia-partition of it in
PTIME using Proposition <ref>.

Queries with no accumulation.

We first prove Theorem <ref> for the case without
accumulation. It suffices to show the following:

For any constant $k \in \mathbb{N}$,
we can determine in PTIME,
for any input po-relation $\OR$ with width $\leq k$,
input po-relation $\OR'$ with ia-width $\leq k$,
and list relation $L$,
whether $L \in \pw(\OR \cupgen \OR')$.

Before proving this, we show a weaker result that restricts to a
bounded-ia-width input relation:

For any constant $k \in \mathbb{N}$,
we can determine in PTIME,
for any po-relation $\OR$ with ia-width $\leq k$
and list relation $L$,
whether $L \in \pw(\OR)$.

Let $\mathbf{A} = (A_1, \ldots, A_k)$ be an ia-partition of width $k$ of $\OR
= (\ID, T, <)$, which can be computed in PTIME
by Proposition <ref>. We assume that the
length of the candidate possible world $L$ is $\card{\ID}$,
as we can trivially reject otherwise.

If there is a way to realize $L$ as a possible world of $\OR$,
For any linear extension $<'$ of $\OR$, we call the
finishing order $<'$ the permutation $\pi$ of $\{1, \ldots, k\}$ obtained by
considering, for each class $A_i$ of $\mathbf{A}$, the largest position $1
\leq n_i \leq \card{\ID}$
in $<'$ to which an element of $A_i$ is mapped, and sorting the
class indexes by ascending finishing order. We say we can realize $L$ with
finishing order $\pi$ if there is a linear extension of $\OR$ that realizes
$L$ and whose finishing order
is $\pi$. Hence, it suffices to check, for every possible permutation $\pi$ of
$\{1, \ldots, k\}$,
whether $L$ can be realized from $\OR$ with finishing order $\pi$: this does not
make the complexity worse because the number of finishing orders depends only on
$k$ and not on $\OR$, so it is constant. (Note that the order relations across
classes may imply that some finishing orders are impossible to realize

We now claim that to determine whether $L$ can be realized with finishing
order $\pi$, the following greedy algorithm works. Read $L$ linearly. At any
point, maintain the set of elements of $\OR$ which have already been used
(distinguish the used and unused elements; initially all
elements are unused), and distinguish the classes of $\mathbf{A}$ in three
kinds: the exhausted
classes, where all elements are used; the open classes,
the ones where some elements are unused and all ancestor elements outside of
the class are used;
and the blocked
classes, where some ancestor element outside of the class is not used.
Initially, the
open classes are those which are roots in the poset obtained from the
underlying poset of $\OR$ by quotienting by the equivalence relation induced by
$\mathbf{A}$; and the other classes are blocked.

When reading a value $t$ from $L$, consider all open classes. If none of these
classes have an unused element with value $t$, reject, i.e., conclude that we cannot realize $L$
as a possible world of $\OR$ with finishing order $\pi$. Otherwise, take the
open class that comes first in the finishing order, and use
an arbitrary suitable element from it. Update the class to be exhausted if it
is: in this case, check that the class was the next one in the finishing
order $\pi$ (and reject otherwise), and
update from blocked to open the classes that
must be. Once $L$ has been completely read, accept: as $\card{L} = \card{\ID}$
we know that all elements are now used.

It is clear by construction that if this greedy algorithm accepts then there
is a linear extension of $\OR$ that realizes $L$ with finishing order $\pi$;
indeed, when the algorithm suceeds then it has clearly respected the finishing
order $\pi$, and whenever an identifier $\id$ of $\OR$ is marked as
used by the algorithm, then $\id$ has
the right value relative to the element of $L$ that has just been read, and
is in an open class so no order relations of $\OR$ are violated by enumerating
$\id$ at this point of the linear extension. The interesting direction is
the converse: show that if $L$
can be realized by a linear extension $<'$ of $\OR$ with finishing order $\pi$,
then the algorithm accepts when considering $\pi$.
To do so, we must show that if there is such a linear extension,
then there is such a linear extension where identifiers are enumerated as in
the greedy algorithm, i.e., we always choose an identifier with the right
value and in the open class with the smallest finishing time: we call this a
minimal identifier. (Note that we do not need to worry about which
identifier is chosen: once we have decided on the value of the identifier and
on its class, then it does not matter which element we choose, because all
elements in the class are unordered and have the same order relations to
elements outside the class thanks to indistinguishability.)
If we can prove this, then this justifies the existence of a linear extension
that the greedy algorithm will construct, which we call a greedy linear

Hence, let us see why it is always possible to enumerate minimal identifiers.
Consider a linear extension $<'$ and take the smallest position in $L$ where
$<'$ chooses an identifier $\id$ which is non-minimal. We know that $\id$ must
still have the correct value, i.e., $T(\id)$ is determined, and by definition
of a linear extension, we know that $\id$ must be in an open class. Hence, we
know that the class $A$ of $\id$ is non-minimal, i.e., there is another open
class $A'$ containing an unused element with value $T(\id)$, and $A'$ is
before $A$ in the finishing order $\pi$. Let us take for $A'$ the first open
class with such an unused element in the finishing order $\pi$, and let $\id'$
be a minimal element, i.e., an element of $A'$ with $T(\id') = T(\id)$. Let us
now construct a different linear extension $<''$ by swapping $\id$ and $\id'$,
i.e., enumerating $\id'$ instead of $\id$, and enumerating $\id$ in $<''$ at
the point where $<'$ enumerates $\id'$. It is clear that the sequence of
values (images by $T$) of the identifiers in $<''$ is still the same as
in $<'$. Hence, if we can show that $<''$ additionally satisfies the order
constraints of $\OR$, then we will have justified the existence of a linear
extension that enumerates minimal identifiers until a later position; so,
reapplying the rewriting argument, we will deduce the existence of a greedy
linear extension. So it only remains to show that $<''$ satisfies the order
constraints of $\OR$.

Let us assume by way of contradiction that $<''$
violates an order constraint of $\OR$. There are two possible kinds of
violation. The first kind is if $<'$ enumerates an element $\id''$
between $\id$ and $\id'$ for which $\id < \id''$, so that having $\id'' <''
\id$ in $<''$ is a violation. The second kind is if $<'$ enumerates an
element $\id''$ between $\id$ and $\id'$ for which $\id'' < \id'$, so that
having $\id'' <'' \id'$  in $<''$ is a violation. The second kind of violation
cannot happen because we know that $\id'$ is in an open class when $<'$
considers $\id$, i.e., we have ensured that $\id'$ can be enumerated instead
of $\id$. Hence, we focus on violations of the first kind. Consider $\id''$
such that $\id <' \id'' <' \id'$ and let us show that we do not have $\id <
\id''$. Letting $A''$ be the class of $\id''$, we assume that $A'' \neq A$, as
otherwise there is nothing to show because the classes are antichains.
Now, we know from $<'$ that we do not have $\id'
<' \id''$, and that the class $A'$ of $\id'$ is not exhausted when $<'$
enumerates $\id''$. As $<'$ respects the finishing order $\pi$, and $A'$ comes
before $A$ in $\pi$, we know that $A$ is not exhausted either when $<'$
enumerates $\id''$. Letting $\id_A$ be an element of $A$ which is still unused
when $<'$ enumerates $\id''$, we know that we do not have $\id_A < \id''$. So
as $\id'' \notin A$ we know by indistinguishability that we do not have $\id <
\id''$ either. This is what we wanted to show, so $\id''$ cannot witness a
violation of the first kind.  Hence $<''$  does not violate the order
constraints of $\OR$, and repeating this rewriting argument shows that there
is a greedy linear extension that the greedy algorithm will find,
contradicting the proof.

We now extend this proof to show Proposition <ref>:

As in the proof of Proposition <ref>, we will enumerate all possible finishing
orders for the classes of $\OR'$, of which there are constantly many, and apply
an algorithm for each finishing order $\pi$, with the algorithm succeeding iff it
succeeds for some finishing order.

We first observe that if there is a way to achieve $L$ as a possible world of
$\OR \cup \OR'$ for a finishing order $\pi$, then there is one where the subsequence of
the tuples that are matched to $\OR'$ are matched following a greedy strategy as
in Proposition <ref>. This is simply because $L$ must then be an
interleaving of a possible world of $\OR$ and a possible world of $\OR'$, and a
match for the possible world of $\OR'$ can be found as a greedy match, by what
was shown in the proof of Proposition <ref>. So it suffices to assume
that the tuples matched to $\OR'$ are matched following the greedy algorithm of
Proposition <ref>.

Second, we observe the following: for any prefix $L'$ of $L$ and order ideal
$\OR''$ of $\OR$, if we realize $L'$ by matching exactly the tuples of
$\OR''$ in $\OR$,
and by matching the other tuples to $\OR'$ following a greedy strategy, then the
matched tuples in $\OR'$ are entirely determined (up to replacing tuples in a
class by other tuples with the same value). This is because, while there may
be multiple ways to match parts of $L'$ to $\OR''$ in a way that leaves a
different sequence of tuples to be matched to $\OR'$, all these ways make us
match the same bag of tuples to $\OR'$; now the state of $\OR'$ after matching a bag
of tuples following the greedy strategy (for a fixed finishing order) is the
same, no matter the order in which these tuples are matched, assuming that the
match does not fail.

This justifies that we can solve the problem with a dynamic algorithm again.
The state contains the position $\mathbf{b}$ in each chain of $\OR$, and a position $i$
in the candidate possible world. As in the proof of
Theorem <ref>, we filter the configurations so that they are sane
with respect to the order constraints between the chains of $\OR$. For each
state, we will store a Boolean value indicating whether the prefix of length
$i$ of $L$ can be realized by $\OR \cupgen \OR'$ such that the tuples
of $\OR$ that
are matched is the order ideal $s(\mathbf{b})$
described by $\mathbf{b}$, and such that the
other tuples of the prefix are matched to $\OR'$ following a greedy strategy with
finishing order $\pi$. By
our second remark above, when the Boolean is true, the state of $\OR'$ is
uniquely determined, and we also store it as part of the state (it is
polynomial) so that we do not have to recompute it each time.

From each state we can make progress by consuming the next tuple from the
candidate possible world, increasing the length of the prefix, and reaching
one of the following states: either match the tuple to a chain of $\OR$,
in which case we make progress in one chain and the consumed tuples in
remain the same; or make progress in $\OR'$, in which case
we look at the previous state of $\OR'$ that was stored and consume a tuple from
$\OR'$ following the greedy algorithm of Proposition <ref>:
more specifically, we find an unused tuple with
the right label which is in the open class that appears first in the finishing
if the class is now exhausted we verify that it was supposed to be the next
one according to the finishing order, and
we update the open, exhausted and blocked status of the

Applying the dynamic algorithm allows us to conclude whether $L$ can be
realized by matching all tuples of $\OR$, and matching tuples in $\OR'$ following
the greedy algorithm with finishing order $\pi$ (and checking cardinality
suffices to ensure that we have matched all tuples of $\OR'$). If the answer of
the dynamic algorithm is YES, then it is clear that, following
the path from the initial to the final state found by the dynamic algorithm,
we can realize $L$. Conversely, if $L$ can be realized, then by our
preliminary remark it can be realized in a way that matches tuples in
following the greedy algorithm for some finishing order. Now, for that
finishing order, the path of the dynamic algorithm that matches tuples
to $\OR$
or to $\OR'$ following that match will answer YES.

queries with finite and position-invariant

We now prove the result for the case of a query with accumulation. In this
setting, the
results for and follow from the following claim:

For any constant $k \in \mathbb{N}$,
and position-invariant accumulation operator $\accum_{h, \oplus}$ with
finite domain, we can compute in PTIME,
for any input po-relation $\OR$ with width $\leq k$
and input po-relation $\OR'$ with ia-width $\leq k$,
the set $\accum_{h, \oplus}(\OR \cupgen \OR')$.

We use Theorem <ref> and Theorem <ref> to compute in PTIME a chain partition of
$\OR$, and we use Proposition <ref> to compute in PTIME
an ia-partition $A_1 \sqcup \cdots \sqcup A_n$ of minimal cardinality of
$\OR'$, with $n \leq k$.

We then apply a dynamic algorithm whose state
consists of:

* for each chain in the partition of $\OR$, the position in
the chain;

* for each class $A$ of the ia-partition of $\OR'$, for each element $m$ of the
monoid, the number of identifiers $\id$ of $A$ such that $h(T(\id), 1)
= m$ that have already been used.

There are polynomially many possible states; for the second bullet point, this
uses the fact that the monoid is finite, so its size is constant because it is
fixed as part of the query. Also note that we use the rank-invariance of $h$
in the second bullet point.

The possible accumulation results for each of the possible states can then be
computed by a dynamic algorithm. At each state, we can decide to make progress
either in a chain of $\OR$ (ensuring that the element that we enumerate has
the right image by $h$, and that the new vector of positions of the chains is
still sane, i.e., yields an order ideal of $\OR$) or in a class of $\OR'$
(ensuring that this class is open, i.e., it has no ancestors in $\OR'$ that
were not enumerated yet, and that it contains an element which has the right
image by $h$). The correctness of this algorithm is because these is a
bijection between the ideals of $\OR \cupgen \OR'$ and the pairs of ideals of
$\OR$ and of ideals of $\OR'$. Now, the dynamic algorithm considers all ideals
of $\OR$ as in the proof of Theorem <ref>, and it clearly
considers all possible ideals of $\OR'$ except that we identify ideals that
only differ by elements in the same class which are mapped to the same value
by $h$ (but this choice does not matter because the class is an antichain and
these elements are indistinguishable outside the class).

As in the proof of Theorem <ref>, we can ensure that all
accumulation operations are in PTIME, using PTIME-evaluability of the
accumulation operator, up to the technicality of storing at each state,
for each of the possible accumulation results, a witnessing totally ordered
relation from which to compute it in PTIME.

Disallowing product is
severe, but we can still integrate sources by taking the
union of their tuples, selecting subsets, and modifying tuple
values with projection. In fact, allowing product makes
intractable when allowing both unordered and totally ordered input:

§.§.§ Hardness result: Proof of Theorem <ref>

There is a query and a query for which the problem is NP-complete
even when the input po-database is restricted to consist only of one totally
ordered and one unordered po-relation.

The proof is by adapting the proof of Theorem <ref>.
The argument is exactly the
same, except that we take relation $S$ to be unordered rather than
totally ordered. Intuitively, in Figure <ref>, this means that we
drop the vertical edges. The proof adapts, because it only used
the fact that $t'_j < t'_k$ for $j < k$ within a row-$i$; we never used
the comparability across groups.

§ TRACTABLE CASES FOR ACCUMULATION QUERIES

We next study tractable cases for and
in presence of accumulation.

Cancellative monoids.

§.§ Cancellative monoids

We first consider a natural restriction on the accumulation function:

For any monoid $(\calM, \oplus, \epsilon)$,
we call $a \in \calM$ cancellable if, for all $b, c \in \calM$, we
have that $a \oplus b = a \oplus c$ implies $b = c$, and we also have that $b \oplus a = c
\oplus a$ implies $b = c$.
We call $\calM$ a cancellative monoid if all
its elements are cancellable.

Many interesting monoids are cancellative; in particular, this is the
case of both monoids in
Example <ref>. More generally, all groups are cancellative
monoids (but some infinite cancellative monoids are not groups, e.g., the monoid
of concatenation).
For this large class of accumulation functions, we design an efficient algorithm for certainty.

is in PTIME for any  query
that performs accumulation in a cancellative monoid.

We show that the accumulation result in cancellative monoids is certain iff the
po-relation on which we apply accumulation respects the following safe
swaps criterion: for all tuples $t_1$ and $t_2$ and consecutive positions $p$ and $p+1$
where they may appear, we have $h(t_1, p) \oplus h(t_2, p+1) = h(t_2, p) \oplus h(t_1,
p+1)$. We can check this in PTIME.

Hence, is tractable for
(Theorem <ref>), via the concatenation monoid, and
is also tractable for top-$k$ (defined in Example <ref>).
The hardness of for (Theorem <ref>) then implies that , unlike ,
is hard even on cancellative monoids.

Other restrictions on accumulation.

§.§ Other restrictions on accumulation

We next revisit the results of Section <ref> for
. However, we need to make other
assumptions on accumulation (besides PTIME-evaluability).
First, in the next results in this section, we
assume that the accumulation monoid is finite:

A query is said to perform finite accumulation if the
accumulation monoid $(\calM, \oplus, \epsilon)$ is finite.

For instance, if the domain of the output is assumed to be fixed (e.g., ratings
in $\{1, \ldots, 10\}$), then
select-at-$k$ and top-$k$ (the latter for fixed $k$),
as defined in Example <ref>, are finite.

Second, for some of the next results, we require position-invariant
accumulation, namely, that the accumulation map does not depend on
the absolute position of tuples:

Recall that the accumulation map $h$ has in general two inputs: a tuple and
its position. A query is said to be position-invariant if its
accumulation map ignores the
second input, so that effectively its only input is the tuple itself.

Note that
accumulation in the monoid is still performed in order, so we can still perform,
e.g., concatenation.
These two restrictions do not suffice to make and tractable (see
Appendix <ref>), but we will use them
to lift the results of Section <ref>.

We show the additional claim that assuming finiteness and position-invariance
of accumulation does not suffice to make or tractable.
Specifically, we show the following two results:

There is a  query performing finite and position-invariant accumulation
for which is NP-hard
even assuming that the input po-database contains only totally ordered po-relations.

There is a  query performing finite and position-invariant accumulation
for which is coNP-hard
even assuming that the input po-database contains only totally ordered po-relations.

We will first show the result about (Theorem <ref>),
and then use it to show the result about (Theorem <ref>).

§.§.§ Proof of Theorem <ref> for

§.§.§ Proof of Theorem <ref> for

Revisiting Section <ref>.

§.§ Revisiting Section <ref>

We now extend our previous results to queries with accumulation,
for and , under the additional assumptions on
accumulation that we presented. We call and the
extension of and with accumulation.

For the proof of the results of this paragraph, refer to the proof of
the corresponding results in Section <ref>: Theorem <ref>
is proven together with Theorem <ref> in
Appendix <ref>, and
Theorem <ref> is proven together with
Theorem <ref> in Appendix <ref>.

We can first generalize Theorem <ref> to queries with
finite accumulation:

For any query performing finite
and are in PTIME on po-databases of bounded width.

We can then adapt the tractability result for queries without product (Theorem <ref>):

For any query performing finite and position-invariant
and are in PTIME on po-databases whose relations
have either bounded width or bounded ia-width.

The finiteness assumption is important, as the previous result
does not hold otherwise. Specifically, there exists a query
that performs position-invariant but not finite
accumulation, for which is NP-hard even on unordered
po-relations (see Appendix <ref>).

§.§ Hardness Without the Finiteness Assumption

We show the additional claim that for queries can be hard if
we do not assume finiteness. Namely, we show:

There is a position-invariant accumulation operator $\accum_{h, \oplus}$
such that is NP-hard for the query $Q \defeq \accum_{h,
\oplus}(\OR)$ (i.e., accumulation applied directly to an input po-relation
$\OR$), even on input po-databases where $\OR$ is restricted to be an unordered relation.

Other definitions.

§.§ Other definitions

Finally, recall that we can use accumulation as in Example <ref> to
capture position-based selection
($\text{top-}k$, $\text{select-at-}k$) and tuple-level comparison
(whether the first occurrence of a tuple precedes all occurrences of another
tuple) for queries. Using a direct construction for these problems, we
can show that they are tractable:

For any query $Q$, the following problems are in PTIME:

select-at-$k$: Given a po-database $D$, tuple value $t$, and
position $k \in \NN$, whether it is  that $Q(D)$ has
value $t$ at position $k$;

top-$k$: For any fixed $k \in \NN$, given a po-database
$D$ and list relation $L$ of length $k$, whether it is
possible/certain that the top-$k$ values in $Q(D)$ are exactly $L$;

tuple-level comparison: Given a po-database $D$ and two tuple
values $t_1$ and $t_2$,
whether it is possible/certain that the first occurrence of $t_1$
precedes all occurrences of $t_2$.

To solve each problem, we first compute the po-relation $\OR \defeq Q(D)$ in
PTIME by Proposition <ref>.
We now address each problem in turn.

Considering the po-relation $\OR = (\ID, T, <)$, we can compute in PTIME,
for every element $\id \in \ID$, its earliest
index $\i^-(\id)$, which is its number of ancestors by $<$ plus one, and its latest
index $\i^+(\id)$, which is the number of elements of $\OR$ minus the number of
descendants of $\id$. It is easily seen that for any element $\id \in \ID$, there is a
linear extension of $\OR$ where $\id$ appears at position $\i^-(\id)$ (by
enumerating first exactly the ancestors of $\id$), or at position
$\i^+(\id)$ (by enumerating first everything except the descendants
of $\id$), or in fact at any position of $[\i^-(\id), \i^+(\id)]$, the
interval of $\id$ (this is by enumerating first the ancestors
of $\id$, and then as many elements as needed that are incomparable
to $\id$, along a linear extension of these elements).

Hence, select-at-$k$ possibility for tuple $t$ and position $k$ can be
decided by checking, for each $\id \in \ID$ such that $T(\id) = t$,
whether $k \in [\i^-(\id), \i^+(\id)]$, and answering YES iff we can find
such an $\id$. For select-at-$k$ certainty, we answer NO iff we can find
an $\id \in \ID$ such that $k \in [\i^-(\id), \i^+(\id)]$ but we have
$T(\id) \neq t$.

Considering the po-relation $\OR = (\ID, T, <)$,
we consider each sequence of $k$ elements of $\OR$, of which there are at most
$\card{ID}^k$, i.e., polynomially many, as $k$ is fixed. To solve possibility for top-$k$, we
consider each such sequence $\id_1, \ldots, \id_k$ such that $(T(\id_1),
\ldots, T(\id_k))$ is equal to the candidate list relation $L$, and we check if this sequence is indeed a prefix of a linear extension
of $\OR$, i.e., whether, for each $i \in \{1, \ldots, k\}$, for any $\id \in
\ID$ such that $\id < \id_i$, if $\id_i \in \{\id_1, \ldots, \id_{i-1}\}$,
which we can do in PTIME. We answer YES iff we can find such a sequence.

For certainty, we consider each sequence $\id_1, \ldots, \id_k$ such that
$(T(\id_1), \ldots, T(\id_k)) \neq L$, and we check whether it is a prefix of
a linear extension in the same way: we answer NO iff we can find such a

tuple-level comparison:
We are given the two tuple values $t_1$ and $t_2$, and we assume that both are
in the image of $T$, as the tuple-level comparison problem is vacuous

For possibility, given the two tuple values $t_1$ and $t_2$, we consider each
$\id \in \ID$ such that $T(\id) = t_1$, and for each of them, we construct
$\OR_\id \defeq (\ID, T, {<_\id})$ where ${<_\id}$ is the transitive closure
of ${<} \cup \{(\id, \id') \mid \id' \in \ID, T(\id') = t_2\}$. We answer YES iff one of the
$\OR_\id$ is indeed a po-relation, i.e., if $<_\id$ as defined does not
contain a cycle. This is correct, because it is possible that the first
occurrence of $t_1$ precedes all occurrences of $t_2$ iff there is some
identifier $\id$ with tuple value $t_1$ that precedes all identifiers with
tuple value $t_2$, i.e., iff one of the $\OR_\id$ has a linear extension.

For certainty, given $t_1$ and $t_2$, we answer the negation of possibility
for $t_2$ and $t_1$. This is correct because certainty is false iff there is a
linear extension of $\OR$ where the first occurrence of $t_1$ does not precede
all occurrences of $t_2$, i.e., iff there is a linear extension where the
first occurrence of $t_2$ is not after an occurrence of $t_1$, i.e., iff some
linear extension is such that the first occurrence of $t_2$ precedes all
occurrences of $t_1$, i.e., iff possibility is true for $t_2$
and $t_1$.

§ EXTENSIONS

We next briefly consider two extensions to our model: group-by and
duplicate elimination.

First, we extend accumulation with a group-by
operator, inspired by SQL.

Let $(\calM, \oplus, \epsilon)$ be a monoid and $h : \calD^k \to \calM$ be
an accumulation map (cf. Definition <ref>), and
$\mathbf{A} = A_1,...,A_n$ be a
sequence of attributes: we call $\accumgby_{h, \oplus, \mathbf{A}}$ an accumulation
operator with group-by.
Letting $L$ be a list relation with compatible schema,
we define $\accumgby_{h, \oplus, \mathbf{A}}(L)$ as
an unordered relation
that has, for each tuple value $t
\in \pi_{\mathbf{A}}(L)$, one tuple $\langle t, v_t \rangle$ where $v_t$ is $\accum_{h,
\oplus}(\sigma_{A_1 = t.A_1,...A_n=t.A_n}(L))$ with $\pi$ and $\sigma$ on
the list relation $L$ having the expected semantics. The result on a
po-relation $\OR$ is the set of unordered relations $\{\accumgby_{h, \oplus, \mathbf{A}}(L) \mid L \in
\pw(\OR)\}$.

In other words, the operator “groups by” the values of $A_1,...,A_n$, and
performs accumulation within each group, forgetting the order
across groups. As for standard accumulation, we only allow
group-by as an outermost operation,
calling the language of queries followed by one accumulation
operator with group-by. Note that the set of possible results is generally not
a po-relation,
because the underlying bag relation is not certain.

We next study the complexity of and for queries. Of course,
whenever and are hard for some query $Q$ on some kind of
input po-relations, then there is a corresponding query
for which hardness also holds (with empty $\mathbf{A}$). The main point of this section is to show that
the converse is not true: the addition of group-by increases
complexity. Specifically, we show that the problem for is
hard even on totally ordered po-relations and without the $\times_\dir$

§.§ Proof of Theorem <ref>: Hardness of with

There is a query $Q$
with finite and position-invariant
accumulation, not using $\times_\dir$, such that for $Q$ is NP-hard even on totally ordered po-relations.

This result contrasts with the tractability of for queries
(Theorem <ref>)
and for queries with finite
accumulation (Theorem <ref>)
on totally ordered po-relations.

By contrast, it is not hard to see that the problem for reduces to for the same query without group-by, so it is no harder than
the latter problem. Specifically:

§.§ Proof of Theorem <ref>: Tractability of with

All tractability results from Section <ref> extend to when imposing the same restrictions on query operators, accumulation, and input

Duplicate elimination.
We last study the problem of consolidating tuples with
duplicate values. To this end, we define a new operator, $\dupelim$, and introduce a
semantics for it. The main problem is that tuples with the same
values may be ordered differently relative to other
tuples. To mitigate this, we introduce the notion
of id-sets:

Given a totally ordered po-relation $(\ID, T, <)$, a subset $\ID'$ of $\ID$
is an indistinguishable duplicate set (or
id-set) if for every $\id_1, \id_2 \in \ID'$,
we have $T(\id_1) = T(\id_2)$,
and for every $\id \in \ID \backslash \ID'$,
we have $\id < \id_1$ iff $\id < \id_2$, and $\id_1 < \id$ iff $\id_2 < \id$.

Consider the totally ordered relation
$\OR_1 \defeq \Pi_{\mathit{hotelname}}(\mathit{Hotel})$, with
$\mathit{Hotel}$ as in Figure <ref>. The two
tuples are not an id-set: they disagree on their
ordering with “Balzac”.
Consider now a totally ordered relation $\OR_2 = (\ID_2, T_2, <_2)$ whose only possible world is
a list
relation $(A, B, B,
C)$ for some tuples $A$, $B$, and $C$ over $\calD$. The set
$\{\id \in \ID_2 \mid T_2(\id) = B\}$ is an id-set in $\OR_2$. Note that a singleton is always
an id-set.

We define a semantics for $\dupelim$ on a totally ordered po-relation $\OR =
(\ID, T, <)$
via id-sets.
First, check that for every
tuple value $t$ in the image of $T$, the set $\{\id \in \ID \mid T(\id) = t\}$ is an id-set
in $\OR$. If this
holds, we call $\OR$ safe, and set $\dupelim(\OR)$ to be the singleton
$\{L\}$ of the only possible world of
the restriction of $\OR$ obtained by picking one representative
element per id-set (clearly $L$ does not depend on the chosen
Otherwise, we call $\OR$ unsafe and say that
duplicate consolidation has failed; we then set $\dupelim(\OR)$ to
be an empty set of possible worlds. Intuitively, duplicate
consolidation tries to reconcile (or “synchronize”) order
constraints for tuples with the same values, and fails when it
cannot be done.

In Example <ref>, we have $\dupelim(\OR_1)=\emptyset$
but $\dupelim(\OR_2) = (A, B, C)$.

We then extend
$\dupelim$ to po-relations by
considering all possible
results of duplicate elimination on the possible worlds,
ignoring the unsafe possible worlds. If no possible worlds are safe, then
we completely fail:

For each list relation $L$, we let $\OR_L$ be a po-relation such that
$\pw(\OR_L) = \{L\}$.
Letting $\OR$ be a po-relation, we set $\dupelim(\OR) \defeq
\bigcup_{L \in pw(\OR)}\dupelim(\OR_L)$. We say that $\dupelim(\OR)$
completely fails if $\dupelim(\OR) = \emptyset$, i.e.,
$\dupelim(\OR_L) = \emptyset$ for every $L\in

Consider the totally ordered po-relation
$\mathit{Rest}$ from
Figure <ref>, and a totally ordered po-relation
$\mathit{Rest}_2$ whose only possible
world is $(\langlem
\textup{Tsukizi} \ranglem,$ $\langlem \textup{Gagnaire} \ranglem)$.
$Q \defeq
\dupelim(\Pi_{\mathit{restname}}(\mathit{Rest}) \cupgen \mathit{Rest}_2)$.
Intuitively, $Q$ combines restaurant rankings,
using duplicate consolidation to collapse two occurrences of the
name to a single tuple.
The only possible world of $Q$ is
(, , ), since
duplicate elimination fails in the other possible worlds:
indeed, this is the only possible way to combine the rankings.

We next show that the result of $\dupelim$ can still be represented as a
up to complete failure (which may be efficiently identified).

§.§ Proof of Theorems <ref>
and <ref> and Proposition <ref>

We first define the notion of quotient of a
po-relation by value equality:

For a po-relation $\OR=(\ID,T,{<})$, we define the value-equality
quotient of $\OR$ as
the directed graph $\mathrm{G}_\OR=(\ID', E)$ where:

* $\ID'$ is the quotient of
$\ID$ by the equivalence relation $\id_1\sim\id_2\Leftrightarrow

* $E\defeq\{(\id'_1,\id'_2)\in{\ID'}^2\mid \id_1' \neq
\id_2'\land \exists
(\id_1,\id_2) \in \id_1'\times \id_2'\text{~s.t.~}id_1<id_2\}$.

We claim that cycles in the value-equality quotient of $\OR$ precisely
characterize complete failure of $\dupelim$.

For any po-relation $\OR$, $\dupelim(\OR)$ completely fails iff
$\mathrm{G}_\OR$ has a cycle.

Fix the input po-relation $\OR = (\ID, T, <)$.
We first show that the existence of a cycle implies complete failure of
$\dupelim$. Let $\id'_1,\dots,\id'_n,\id'_1$ be a simple cycle of
For all $1\leq i\leq n$, there exists $\id_{1i},\id_{2i}\in\id'_1$ such
that $\id_{2i}<\id_{1(i+1)}$
(with the convention $\id_{1(n+1)}=\id_{11}$)
and the $T(\id_{2i})$ are pairwise distinct.

Let $L$ be a possible world of $\OR$ and let us show that $\dupelim$
fails on any po-relation $\OR_L$ that represents $L$, i.e.,
$\OR_L = (\ID_L, T_L, {<_L})$ is totally ordered and $\pw(\OR_L) = \{L\}$.
Assume by contradiction that
for all $1\leq i\leq n$, $\id'_i$ forms an id-set of $\OR_L$. Let us show
by induction on $j$ that for all $1\leq j\leq n$,
$\id_{21}\leq_{L}\id_{2j}$, where $\leq_L$ denotes the non-strict order
defined from $<_L$ in the expected fashion. The base case is trivial. Assume this holds
for $j$ and let us show it for $j+1$. Since $\id_{2j}<\id_{1(j+1)}$, we
have $\id_{21}\leq\id_{2j}<_L\id_{1(j+1)}$. Now, if $\id_{2(j+1)}<_{L}\id_{21}$,
then $\id_{2(j+1)}<_{L}\id_{21}<_L\id_{1(j+1)}$ with
$T(\id_{2(j+1)})=T(\id_{1(j+1)})\neq T(\id_{21})$, so this contradicts the fact that
$\id'_{j+1}$ is an id-set. Hence, as $L$ is a total order, we must have
$\id_{21} \leq_L \id_{2(j+1)}$, which
proves the induction case. Now the claim proved by induction implies that
$\id_{21}\leq_{L}\id_{2n}$, and we had $\id_{2n}<\id_{11}$ in $\OR$ and
therefore $\id_{2n}<_L\id_{11}$, so this contradicts the fact that
$\id'_1$ is an id-set. Thus, $\dupelim$ fails in $\OR_L$. We have thus shown that
$\dupelim$ fails in every possible world of $\OR$, so that it completely fails.

Conversely, let us assume that $\mathrm{G}_\OR$ is acyclic. Consider a
topological sort of $\mathrm{G}_\OR$ as $\id'_1,\dots,\id'_n$. For $1\leq
j\leq n$, let $L_j$ be a linear extension of the poset
$(\id'_j,\restr{<}{\id'_j})$. Let $L$ be the concatenation of $L_1,\dots L_n$.
We claim $L$ is a linear extension of $\OR$ such that $\dupelim$ does not
fail in $\OR_L = (\ID_L, T_L, {<_L})$; this latter fact is clear by construction of $L$, so we must only show
that $L$ obeys the comparability relations of $\OR$. Now, let
$\id_1<\id_2$ in $\OR$. Either for some $1\leq j\leq n$,
$\id_1, \id_2\in\id'_j$ and then the tuple for $\id_1$ precedes the one
for $\id_2$ in $L_j$ by construction, so
means $t_1<_L t_2$; or they are in different classes $\id'_{j_1}$ and
and this is
reflected in $\mathrm{G}_\OR$, which means that $j_1<j_2$ and
$\id_1<_L \id_2$. Hence, $L$ is a linear extension, which concludes the proof.

We can now state and prove the result:

For any po-relation $\OR$, we can test in PTIME if
$\dupelim(\OR)$ completely fails; if it does not,
we can compute in PTIME a po-relation $\OR'$ such that

We first observe that $\mathrm{G}_\OR$ can be constructed in PTIME,
and that testing that $\mathrm{G}_\OR$ is acyclic is also done in
PTIME. Thus, using Proposition <ref>, we can determine
in PTIME whether $\dupelim(\OR)$ fails.

If it does not, we let $\mathrm{G}_\OR=(\ID',E)$ and construct the
relation $\OR'$ that will stand for $\dupelim(\OR)$ as
$(\ID',T',<')$ where  $T'(\id')$ is the unique $T'(\id)$ for
$\id\in\id'$ and $<'$ is the transitive closure of $E$, which is
antisymmetric because $\mathrm{G}_\OR$ is acyclic. Observe that
the underlying bag relation of $\OR'$ has one identifier for each distinct
tuple value in $\OR$, but has no duplicates.

Now, it is easy to check that $\pw(\OR')=\dupelim(\OR)$. Indeed, any
possible world $L$ of $\OR'$ can be achieved in $\dupelim(\OR)$ by
considering, as in the proof of Proposition <ref>, some
possible world of $\OR$ obtained following the topological sort of
$\mathrm{G}_\OR$ defined by $L$. This implies that $\pw(\OR')
\subseteq \dupelim(\OR)$.

Conversely, for any possible world $L$ of $\OR$, $\dupelim(\OR_L)$ (for
$\OR_L$ a po-relation that represents $L$) fails
unless, for each tuple value, the occurrences of that tuple value in
$\OR_L$ is an id-set. Now, in such an $L$, as the occurrences of each
value are contiguous and the order relations reflected in
$\mathrm{G}_\OR$ must be respected, $L$ is defined by a topological
sort of $\mathrm{G}_\OR$ (and some topological sort of each id-set
within each set of duplicates), so that $\dupelim(\OR_L)$ can also be
obtained as the corresponding linear extension of $\OR'$. Hence, we
have $\dupelim(\OR) \subseteq \pw(\OR')$, proving their equality and
concluding the proof.

We note that $\dupelim$ is not redundant with any of the other PosRA
operators, generalizing Theorem <ref>:

No operator among those of and
$\dupelim$ can be expressed through a combination of the

This is shown in the proof of Theorem <ref> in
Appendix <ref>.

Last, we observe that $\dupelim$ can indeed be used to undo some of the effects
of bag semantics. For instance, we can show the following:

We also use the value-equality quotient to show:

For any po-relation $\OR$, we have $\dupelim(\OR \cup \OR) = \dupelim(\OR)$:
in particular, one completely fails iff the other does.

Let $G_\OR$ be the value-equality quotient of $\OR$ and $G'_\OR$ be the
value-equality quotient of $\OR \cup \OR$. It is easy to see that these two
graphs are identical: any edge of $G_\OR$ witnesses the existence of the same
edge in $G'_\OR$, and conversely any edge in $G'_\OR$ must correspond to a
comparability relation between two tuples of one of the copies of $\OR$ (and
also in the other copy, because they are two copies of the same relation), so
that it also witnesses the existence of the same edge in $\OR$. Hence, one
duplicate elimination operation completely fails iff the other does, because
this is characterized by acyclicity of the value-equality quotient (see
Proposition <ref>). Further, by Theorem <ref>, as
duplicate elimination is constructed from the value-equality quotient, we have
indeed the equality that we claimed.

We can also show that most of our previous tractability results still apply when
the duplicate elimination operator is added:

§.§ Possibility and Certainty Results

We first clarify the semantics of query evaluation when complete failure
occurs: given a query $Q$ in  extended with $\dupelim$, and given a po-database $D$,
if complete failure occurs at any
occurrence of the $\dupelim$ operator when evaluating $Q(D)$, we set
$\pw(Q(D)) \defeq \emptyset$,
pursuant to our choice of defining query evaluation on po-relations as
yielding all possible results on all possible worlds.
If $Q$ is
a  query extended with $\dupelim$, we likewise say that its
possible accumulation results are $\emptyset$.

This implies that for any query $Q$ extended with $\dupelim$,
for any input po-database $D$, and
for any candidate possible world $v$, the and problems for $Q$ are
vacuously false on instance $(D, v)$
if complete failure occurs at any stage when evaluating $Q(D)$. The same holds
for queries.

§.§.§ Proof of Theorem <ref>: Adapting the Results of
Section <ref>–<ref>

All and tractability results of
Sections <ref>–<ref>,
except Theorem <ref> and
Theorem <ref>,
extend to and where we allow $\dupelim$ (but impose
the same restrictions on query operators, accumulation, and input

All complexity upper bounds in Sections <ref>–<ref> are proved by first
evaluating the query result in PTIME using Proposition <ref>. So we
can still evaluate the query in PTIME, using in addition
Theorem <ref>. Either complete failure occurs at some point in
the evaluation, and we can
immediately solve and by our initial remark above, or no complete failure occurs and we obtain
in PTIME a po-relation on which to solve and . Hence, in what
follows, we can assume that no complete failure occurs at any stage.

Now, except Theorems <ref> and
Theorem <ref>, the only assumptions that are
made on the po-relation obtained from query evaluation are proved using the
following facts:

* For all theorems in Section <ref>, for
Theorem <ref>, and for
Proposition <ref>, no assumptions are
made, so the theorems continue to hold.

* For Theorem <ref> and Theorem <ref>, that the property of having a constant
width is preserved during query evaluation, using
Proposition <ref>.

Hence, Theorem <ref> follows from the following
width preservation result:

For any constant $k \in \NN$ and po-relation $\OR$ of width $\leq k$, if
$\dupelim(\OR)$ does not completely fail then it has width $\leq k$.

It suffices to show that to every antichain $A$ of $\dupelim(\OR)$ corresponds an
antichain $A'$ of the same cardinality in $\OR$. Construct $A'$ by picking a
member of each of the classes of $A$. Assume by contradiction that $A'$ is
not an antichain, hence, there are two tuples $t_1 < t_2$ in $A'$, and
consider the corresponding classes $\id_1$ and $\id_2$ in $A$. By our
characterization of the possible worlds of $\dupelim(\OR)$
in the proof of Theorem <ref>
as obtained from the topological sorts
of the value-equality quotient $\mathrm{G}_\OR$ of $\OR$, as $t_1 < t_2$ implies
that $(\id_1, \id_2)$ is an edge of $\mathrm{G}_\OR$, we conclude that we have $\id_1
< \id_2$ in $A$, contradicting the fact that it is an antichain.

We conclude by illustrating that Theorem <ref> cannot be
adapted as-is, because the preservation result that it uses does not adapt to
the $\dupelim$ operator.

Fix $n \in \NN$. Consider the totally ordered relation $R \defeq \ordern{n}$; it
has width $1$.
Consider the po-relation $S = (\ID, T, <)$ that consists of $n$ pairwise incomparable
identifiers $\id^\uparrow_1,
\ldots, \id^\uparrow_n$ whose images by $T$ are respectively $1, \ldots, n$, and $n$ pairwise
incomparable identifiers $\id_1^\downarrow, \ldots, \id_n^\downarrow$ with pairwise distinct fresh
values, with the order relation $\id_i^\uparrow < \id_j^\downarrow$ for all $1 \leq i, j \leq n$;
The po-relation $S$ has ia-width $2$, with the partition
$(\{\id^\uparrow_i \mid 1 \leq i \leq n\},
\{\id^\downarrow_i \mid 1 \leq i \leq n\})$. Hence, $R \cupgen S$ would satisfy the
hypotheses of Theorem <ref>. However, $R' \defeq \dupelim(R
\cupgen S)$
is the po-relation consisting of tuples $\id'_1, \ldots, \id'_n$ with values
respectively $1, \ldots, n$, tuples $\id''_1, \ldots, \id''_n$ with the values of
the $\id^\downarrow_i$, and the order relation $\id'_i < \id'_j$ iff $i
< j$ and $\id'_i < \id''_j$
for all $1 \leq i, j \leq n$.

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.

Furthermore, if in a set-semantics spirit we require that the
query output has no duplicates, and are always tractable (as this
avoids the technical difficulty of Example <ref>):

§.§.§ Proof of Theorem <ref>: and After Removing Duplicates

For any query $Q$, and for $\dupelim(Q)$
are in PTIME.

Let $D$ be an input po-relation, and $L$ be the candidate possible world
(a list relation).
We compute the po-relation $\OR'$ such that $\pw(\OR')= Q(D)$ in PTIME using
Proposition <ref>
and the po-relation $\OR \defeq \dupelim(\OR')$ in PTIME using
Theorem <ref>. If duplicate elimination fails, we vacuously
reject for and , following the remark at the beginning of
Appendix <ref>.
Otherwise, the result is a po-relation $\OR$, 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 $\OR$; so we assume that $L$ has the
same underlying set of tuples as $\OR$ and no duplicate tuples.

The problem is in PTIME on $\OR$ by Theorem <ref>, so
we need only study the case of , namely, decide whether $L \in
\pw(\OR)$.
Let $\OR_L$ be a po-relation that represents $L$.
As $\OR_L$ and $\OR$ have no duplicate tuples, there is only one way to
match each identifier of $\OR_L$ to an identifier of $\OR$.
Build $\OR''$ from $\OR$ by adding, for each pair $\id_i <_L \id_{i+1}$ of consecutive
tuples of $\OR_L$, the order constraint $\id_i'' {<''} \id''_{i+1}$ on the
corresponding identifiers in $\OR''$. We claim that $L \in \pw(\OR)$ iff the
resulting $\OR''$
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 $\OR''$ and checking that they are all trivial.

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

The introduced group-by and duplicate elimination operators have some  shortcomings: the result of group-by is in general not representable by po-relations, and duplicate elimination may fail. These are both consequences of our design choices, where we capture only uncertainty on order (but not on tuple values) and design each operator so that its result corresponds to the result of applying it to each individual world of the input (see further discussion in Section <ref>). Avoiding these shortcomings is left for future work.

§ COMPARISON WITH OTHER FORMALISMS

We next compare our formalism to previously proposed formalisms:
query languages over bags (with no order); a query language for
partially ordered multisets; and other related work.
To our knowledge, however, none of these works studied the possibility or
certainty problems for partially ordered data, so that our technical results do not follow from them.

Standard bag semantics.

We first compare to related work on the bag semantics for relational
algebra. Indeed, a natural desideratum for our semantics on
(partially) ordered relations is that it should be a faithful extension
of bag semantics. We first consider the $\BALG^{1}$ language on bags
[21] (the “flat fragment” of their language $\BALG$ on
nested relations).
We denote by $\BALG_{+}^{1}$ the fragment of $\BALG^{1}$,
that includes the standard extension of positive relational algebra
operations to bags: additive union, cross product, selection,
and projection.
We observe that, indeed, our semantics
faithfully extends $\BALG_{+}^{1}$:
evaluation commutes with “forgetting” the order. Formally, for a po-relation $\OR$, we
denote by $\bag(\OR)$ its underlying bag relation, and define likewise
$\bag(D)$ for a po-database $D$ as the database of the underlying bag relations.
For the
following comparison, we identify $\times_{\dir}$ and
$\times_{\lex}$ with the $\times$ of [21] and our
union with the additive union of [21], and then the following trivially holds:

For any 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

There is an exact correspondence in terms of the output bags between
additive union and our union; between cross product and $\times_{\dir}$ and
$\times_{\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 <ref> 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.

The full $\BALG^{1}$ language includes additional operators, such as bag
intersection and subtraction, which are non-monotone and as such may not be
expressed in our language: it is also unclear how they could be extended to our
setting (see further discussion in “” below).
On the other hand, $\BALG^{1}$ does not include
aggregation, and so and $\BALG^{1}$ are incomparable in terms of
expressive power.

A better yardstick to compare against for accumulation could be [33]:
they show that their basic language $\BQL$ is equivalent
to $\BALG$, and then further extend the language with aggregate operators, to
define a language called $\NRLaggr$ on nested relations.
On flat relations,
functions that cannot be captured in our
language: in particular the average function  is non-associative and thus cannot be captured by
our accumulation function (which anyway focuses on order-dependent functions, as
/are trivial otherwise).
On the other hand, $\NRLaggr$ cannot test
(Corollary 5.7 in [33]) whereas this is easily captured by our accumulation operator.
We conclude that $\NRLaggr$ and are incomparable in terms of captured transformations on bags, even when restricted to flat relations.

Algebra on pomsets.
We now compare our work to algebras defined
on pomsets [20, 22], which also
attempt to bridge partial order theory and data management (although, again, they do not
study possibility and certainty).
Pomsets are labeled posets quotiented by
isomorphism (i.e., renaming of identifiers), like po-relations.
conceptual difference between our formalism and that
of [20, 22] is that their language focuses on
processing connected components of the partial order graph,
and their operators are tailored for that semantics. As a
consequence, their semantics is not a faithful extension of bag
semantics, i.e., their language would not satisfy the counterpart of Proposition <ref> (see for instance the semantics of union in [20]).
By contrast, we manipulate po-relations that stand for sets of possible list
relations, and our operators are designed accordingly, unlike those of
[20] where transformations take into account the structure
(connected components) of the entire poset graph.
Because of this choice, [20] introduces
non-monotone operators that we cannot express, and
can design a duplicate elimination operator that cannot fail. Indeed, the possible failure of our duplicate elimination operator is a direct consequence of its semantics of operating on each possible world, possibly leading to contradictions.

If we consequently disallow duplicate elimination in both languages for the sake
of comparison, we note that the resulting fragment $\PomAlgEps$ of the language
of [20] can yield only series-parallel output
(Proposition 4.1 of [20]), unlike queries whose output order may be arbitrary (see
Appendix <ref>). Hence, $\PomAlgEps$ does not subsume

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

For any po-relation $\OR$, there is a query $Q$ with no inputs
s.t. $Q() = \OR$.

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

[36]
Letting $P = (V, <)$ be a poset, we say that a set of total orders
$(V, {<_1}), \ldots, (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 <cit.>,
see also <cit.>; we rephrase it in our vocabulary, and for
convenience we also give a self-contained proof.

Let $n \in \NN$, and let
$(P, <_P)$ be a poset that has a realizer $(L_1, \ldots, L_n)$ of size $n$.
Then $P$ is isomorphic to a subset $\OR'$ of $\OR = \ordern{l} \times_{\gen}
\cdots \times_{\gen} \ordern{l}$, with $n$ factors in the product, for some integer $l \in \mathbb{N}$ (the
order on $\OR'$ being the restriction on that of $\OR$).

We define $\OR$ by taking $l \defeq \card{P}$,
and we
identify each
element $x$ of $P$ to $f(x) \defeq (n_1^x, \ldots, n_n^x)$, where
$n^x_i$ 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) <_\OR 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 $\OR'$ to be the image of $f$ (which is
injective), $\OR'$ is indeed isomorphic to $P$.

We are now ready to prove Proposition <ref>:

We first show that for any
poset $(P, <)$, there exists a query $Q$
such that the tuples of $\OR' \defeq Q()$ all have unique
values and the underlying poset of $\OR'$ is $(P, <)$.
Indeed, we can take $d$ to be the order dimension of
$P$, which is necessarily finite [36], and then by
definition $P$ has a realizer of size $d$. By
Lemma <ref>, there is an integer
$l \in \mathbb{N}$ such that $\OR'' \defeq \ordern{l} \times_\gen \cdots
\times_\gen \ordern{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(\OR'') = S$ (which can clearly be constructed by
enumerating the elements of $S$), the query $Q' \defeq \sigma_\psi(\OR'')$ proves the
claim, with $\OR''$
expressed as above.

Now, to prove the desired result from this claim, build $Q$ from $Q'$ by
taking its join (i.e., $\times_\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 $\OR$. This
concludes the proof.

Incompleteness in databases.

Our work is inspired by the field of incomplete information management, which
has been studied for
various models [5, 30], in particular
relational databases [24]. This field inspires our design
of po-relations
and our study of
possibility and certainty [3, 34]. However, uncertainty in
these settings typically focuses on whether tuples exist
or on what their values are (e.g., with nulls [10],
including the novel approach of [31, 32];
with c-tables [24], probabilistic
databases [42] or fuzzy numerical values as
in [38]). To our knowledge, though, our work is the first to study possible and
certain answers in the context of
order-incomplete data. Combining order incompleteness with standard
tuple-level uncertainty is left as a challenge for future work.
Note that some works [8, 29, 32] use
partial orders on relations to compare the
informativeness of representations. This is
unrelated to our partial orders on tuples.

Ordered domains.
Another line of work has studied
relational data management where the domain elements are
(partially) ordered [25, 35, 43]. However, the perspective
is different: we see order on tuples as part of the relations, and
as being constructed by applying our operators; these works see
order as being given outside of the query, hence do not study the propagation of uncertainty through queries.
Also, queries in such works can often directly access the order
relation  [43, 6]. Some works also study uncertainty on totally ordered
domains [38, 39], while
we look at general order relations.

Temporal databases.

databases [9, 37] consider
order on facts, but it is usually induced by timestamps, hence
total. A notable exception is [16] which
considers that some facts may be more current than others,
with constraints leading to a partial order. In particular, they
study the complexity of retrieving query answers that are certainly
current, for a rich query class. In contrast, we can
manipulate the order via queries, and we can also ask
about aspects beyond currency, as shown throughout the paper
(e.g., via accumulation).

Using preference information.
Order theory has been also used to handle preference information in
database systems [26, 4, 27, 2, 41],
with some operators being the same as ours, and for rank
aggregation [15, 26, 14], i.e. retrieving top-$k$ query answers given multiple
rankings. However, such works typically try to resolve
uncertainty by reconciling many conflicting representations (e.g.
via knowledge on the individual scores given by different sources
and a function to aggregate them [15], or a preference
function [2]). In contrast, we focus on maintaining a faithful model of
all possible worlds without reconciling them, studying possible and certain answers in this respect.

§ CONCLUSION

This paper introduced an algebra for order-incomplete data. We have studied the complexity of possible and certain
answers for this algebra, have shown the problems to be generally intractable, and identified
several tractable cases. In future work we plan to study the incorporation of additional operators (in particular non-monotone ones), investigate how to combine order-uncertainty with uncertainty on values, and study additional semantics for $\dupelim$. Last, it would be interesting to establish a dichotomy
result for the complexity of , and a
complete syntactic characterization of cases where is tractable.

We are grateful to Marzio De
Biasi, Pálvölgyi Dömötör, and Mikhail Rudoy, from
<cstheory.stackexchange.com>, for helpful suggestions.
This research was partially supported by the Israeli Science Foundation (grant 1636/13) and the Blavatnik ICRC.

§ DISCUSSION OF CHANGES IN THIS VERSION

In the process of preparing a journal version of this
paper <cit.>, we have discovered a flaw in the proof of
some of our tractability results on ia-width. We have accordingly
removed these results from <cit.>
and from the present version of this paper.
However, the results still survive in the first version of this paper on
arXiv <cit.> and in the published
version in the TIME proceedings <cit.>. In this appendix,
we list the affected theorems, point out the source of the error, and discuss our
current understanding of their correctness.

Affected theorems.

The affected theorems are numbered as follows in the TIME proceedings version <cit.> and in
the main text of <cit.>:

* Theorem 19: tractability of for any query on po-databases
of unordered po-relations.

* Theorem 22: tractability of for any query on po-databases
of bounded-ia-width po-relations.

* Theorem 30: tractability of and for any query on
po-databases of bounded-ia-width po-relations.

Source of the error.

The error is in Proposition 66 of <cit.>.
This proposition claims
that, for any query $Q$ and $k \in \NN$, there is a bound $k' \in \NN$
such that, for any po-database $D$ of po-relations of ia-width $\leq k$, the
po-relation $Q(D)$ has ia-width $\leq k'$. The proof is by induction, but in the
case of the product operators $\times_\lex$ and $\times_\gen$, the argument
does not correctly reflect the behavior of the product operators. For this
reason, the proof of the proposition is incorrect, and this affects the theorems
listed previously, because their proofs rely on Proposition 66.

Status of the results.

It is easy to see that the statement of Proposition 66 fails to hold:

(a11) at (0, 0) $\langle 1, 1 \rangle$;
(a12) at (0, 1) $\langle 1, 2 \rangle$;
(a21) at (1, 0) $\langle 2, 1 \rangle$;
(a22) at (1, 1) $\langle 2, 2 \rangle$;
(d) at (2, .5) $\cdots$; ,
(an1) at (3, 0) $\langle n, 1 \rangle$;
(an2) at (3, 1) $\langle n, 2 \rangle$;
(a11) – (a12);
(a21) – (a22);
(an1) – (an2);