dataesr/scientific-paragraphs-categorization huggingface dataset:
Note that pw (Γ ∪ CAT Γ ′ ) = {L ∪ CAT L ′ | L ∈ pw (Γ), L ′ ∈ pw (Γ ′ )}, where L ∪ CAT L ′ is the concatenation of two list relations in the usual sense. We show that concatenation can be captured in PosRA LEX. Lemma 2. 6. For any arity n ∈ N and distinguished relation names R and R ′ , there is a query Q n without × DIR operator such that, for any two po-relations Γ and Γ ′ of arity n, letting D be the database mapping R to Γ and R ′ to Γ ′ , the query result Q n (D) is Γ ∪ CAT Γ ′. Proof. For any n ∈ N and names R and R ′ , consider the following query: Q n (R, R ′ ) • • = Π 3. n+2 σ. 1=. 2 [ 2] × LEX (([1] × LEX R) ∪ ([2] × LEX R ′ )) It is easily verified that Q n satisfies the claimed property. By contrast, we show that concatenation cannot be captured in PosRA DIR. Lemma 2. 7. For any arity n ∈ N >0 and distinguished relation names R and R ′ , there is no PosRA DIR query Q n such that, for any po-relations Γ and Γ ′ of arity n, letting D be the po-database that maps R to Γ and R ′ to Γ ′ , the query result Q n (D) is Γ ∪ CAT Γ ′.
To prove Lemma 2. 7, we first introduce the following concept. Definition 2. 8. Let v ∈ D. We call a po-relation Γ = (ID, T, <) v-impartial if, for any two identifiers id 1 and id 2 and 1 i a(Γ) 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. Lemma 2. 9. Let v ∈ D\N be a value. For any PosRA DIR query Q, for any po-database D of v-impartial po-relations, the po-relation Q(D) is v-impartial. Proof. Let D be a po-database of v-impartial po-relations. We show by induction on the query Q that v-impartiality is preserved. 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.
v ′ ). Consider the po-database D mapping R to Γ and R ′ to Γ ′. Write Γ ′′ • • = Q n (D). By our assumption, as Γ ′′ = (ID ′′ , T ′′ , < ′′ ) is Γ ∪ CAT Γ ′ , it must contain an identifier id ∈ ID ′′ such that T ′′ (id ) = t and an identifier id ′ ∈ ID ′′ such that T ′′ (id ′ ) = t ′. Now, as Γ and Γ ′ are (vacuously) v-impartial, Lemma 2. 9 implies that Γ ′′ is v-impartial. Hence, as n > 0, taking i = 1, as t = t ′ and exactly one of t. 1 and t ′. 1 is v, the identifiers id and id ′ are incomparable in < ′′ , so there is a possible world of Γ ′′ where id ′ precedes id. This contradicts the fact that, as we should have Γ ′′ = Γ ∪ CAT Γ ′ , the po-relation Γ ′′ should have exactly one possible world, namely, (t, t ′ ). This establishes that the × LEX operator cannot be expressed using the others, and shows that none of our operators is redundant, which concludes the proof of Theorem 2.
PosRA acc : Queries With Accumulation We now enrich PosRA with order-aware accumulation as the outermost operation, inspired by right accumulation and iteration in list programming, and aggregation in relational databases. Recall that a monoid (M, ⊕, ε) consists of a set M (not necessarily finite), an associative operation ⊕ : M × M → M, and an element ε ∈ M which is neutral for ⊕, i. e. , for all m ∈ M, we have ε ⊕ m = m ⊕ ε = m. We will use a monoid as the structure in which we perform accumulation. We can now define accumulation on a given list relation. Definition 2. 10. For k ∈ N, let h : D k × N >0 → M be a function called an arity-k accumulation map, which maps pairs consisting of an k-tuple and a position to a value in the monoid M. We call accum h,⊕ an arity-k accumulation operator; its result accum h,⊕ (L) on an arity-k list relation L = (t 1 ,.
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: Definition 2. 12. For a po-relation Γ, we define accum h,⊕ (Γ) • • = {accum h,⊕ (L) | L ∈ pw (Γ)}. Of course, accumulation has exactly one result whenever the accumulation operator accum h,⊕ does not depend on the order of input tuples: this covers, e. g. , the standard sum, min, max, etc. Hence, we focus on accumulation operators which depend on the order of tuples, e. g. , the monoid M of strings with ⊕ being the concatenation operation. In this case, there may be more than one accumulation result. Example 2. 13. As a first example, let Ratings(user , restaurant , rating ) be an unordered po-relation describing the numerical ratings given by users to restaurants, where each user rated each restaurant at most once.
Possibility and Certainty Evaluating a PosRA or PosRA acc query Q on a po-database D yields a set of possible results: for PosRA acc , it yields an explicit set of accumulation results, and for PosRA, it yields a porelation that represents a set of possible worlds (list relations). The uncertainty on the result may come from uncertainty on the order of the input relations (i. e. , if they are po-relations with multiple possible worlds), but it may also be caused by the query, e. g. , the union of two non-empty totally ordered relations is not totally ordered. In some cases, however, there is only one possible result to the query, i. e. , a certain answer. In other cases, we may wish to examine multiple possible answers. We thus define the corresponding problems. ∈ pw (Q(D)), i. e. , if L is a possible result of Q on D.
First, as we exemplify below, the output of a query may be certain even for a complex query 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 CERT problem is useful for this task, because we can use it to decide if a certain output exists: and if it is the case, then we can compute the certain output in polynomial time, by choosing an arbitrary linear extension and computing the corresponding possible world. However, CERT is a challenging problem to solve, because of duplicate values (see the "Technical difficulties" paragraph below). Example 3. 2. Consider the po-database D of Figure  1  with relations Restaurant and Hotel 2. To find recommended pairs of hotels and restaurants in the same district, we can write Q • • = σ Restaurant.
General Complexity Results We have defined the PosRA and PosRA acc query languages, and defined and motivated the problems POSS and CERT. We now start the study of their complexity, which is the main technical contribution of our paper. We will always study their data complexity 2  , where the query Q is fixed: in particular, for PosRA acc , 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 POSS and CERT for the fixed query Q is the po-database D and the candidate result (a list relation for PosRA, an accumulation result for PosRA acc ). We summarize the complexity results of Sections 4-6 in Table  1. In this section, we state our main complexity results and prove the corresponding upper bounds.
1): CERT is in PTIME for PosRA acc queries that perform accumulation in a cancellative monoid. Practical implications We now discuss some implications of the results highlighted in Table  1  on the implementation of the algebra on top of, say, a SQL database engine. First, recall Proposition 2. 2: computing the result of a query, as a po-relation, is in PTIME in the size of the input database, and can thus reasonably be implemented. Second, thanks to Theorem 6. 1, since CERT is in PTIME for PosRA, it should also be possible to implement certainty tests efficiently. However, Theorem 4. 1 shows that possibility tests are prohibitive to implement in all generality. However, in a practical context, input relations are usually not arbitrary po-relations: it makes sense to assume in many scenarios that input relations are either totally ordered (say, because they are ordered by their primary key, or by an explicit ORDER BY construct) or unordered (because no specific ordering has been chosen).
Tractable Cases for POSS on PosRA Queries We have stated a general NP-hardness result for POSS with PosRA queries. We next show that tractability may be achieved if we both restrict the allowed operators and bound some order-theoretic parameters of the input po-database, e. g. , its width. Recall that PosRA LEX (respectively, PosRA DIR ) denotes the fragment of PosRA that disallows × DIR (respectively, × LEX ).
In a sense, the × DIR operator is the one introducing the most uncertainty and "unorderedness" in the result, so we consider the fragment PosRA LEX of PosRA queries without × DIR , and show the following result. Theorem 5. 1. For any fixed k ∈ N and fixed PosRA LEX query Q, the POSS problem for Q is in PTIME when all po-relations of the input po-database have width k. To show this result, letting D be the input po-database, we can use Proposition 2. 2 to evaluate Γ := Q(D) in PTIME. Recall that we have previously shown Lemma 2. 4 on PosRA LEX , so we know that the width of the po-relation Γ is constant: it only depends on k and Q, but not on D. Hence, to show Theorem 5. 1, it suffices to show the following. Let us prove this lemma and conclude the proof of Theorem 5. 1. Proof. Let Γ = (ID, T, <) be the po-relation of width k ′ k, and let P = (ID , <) be its underlying poset.
, 0) = ε and from the previously computed values of t, recalling that t(m ′ ) := 0 whenever m ′ is not sane. Now, t(n 1 ,. , n k ′ ) is true iff Γ has a linear extension achieving L, so we have indeed solved the POSS problem for Γ and L in PTIME, concluding the proof. We have now shown Theorem 5. 1 and established tractability for POSS with PosRA LEX queries on po-databases of bounded width. We will show in Theorem 6. 12 that this proof technique further extends to queries with accumulation, under some assumptions over the accumulation function. We next show that our tractability result only holds for PosRA LEX. Indeed, if we allow × DIR , then POSS is hard on totally ordered po-relations, even if we disallow × LEX. This result implies the general NP-hardness result on POSS that we stated earlier (Theorem 4.
1) for queries without accumulation. Theorem 5. 3. There is a PosRA DIR query for which the POSS problem is NP-complete even when input po-databases consist only of totally ordered po-relations. Proof. We reduce from the NP-hard UNARY-3-PARTITION problem  [25] : given 3m integers E = (n 1 ,. , n 3m ) written in unary (not necessarily distinct) and a number B, decide if the integers can be partitioned in triples such that the sum of each triple is B. We reduce an instance I = (E, B) of UNARY-3-PARTITION to a POSS instance in PTIME. We fix D • • = N ⊔ {s, n, e}, with s, n and e standing for start, inner, and end. Let D be the po-database which interprets the relation name S by the totally ordered porelation [ 3m -1], and the relation name S ′ by the totally ordered po-relation constructed from the instance I as follows: for 1 i 3m, consider the concatenation of one tuple id i 1 with value s, n i tuples id i j (with 2 j n i + 1) with value n, and one tuple id i n i +2 with value e, and define the interpretation of S ′ by concatenating the 3m sequences of length n i + 2.
Consider the query Q • • = Π 2 (S × DIR S ′ ), where Π 2 projects to the attribute of the relation S ′. See Figure  4  for an illustration with E = (1, 1, 2) and B = 4. We define the candidate possible world L as the list relation  • L 1 is a list relation defined as the concatenation, for 1 i 3m, of 3mi copies of the following sublist: one tuple with value s, n i tuples with value n, and one tuple with value e. L := L 1 L ′ L 2 , with L 1 , L ′ , • L 2 is a list relation defined like L 1 , except that 3mi is replaced by i -1. • L 0 is the list relation consisting of three tuples with value s, B tuples with value n, three tuples with value e. See Figure  4  for an illustration of L 0. • L ′ is the list relation defined as the concatenation of m copies of L 0. We now consider the POSS instance that asks whether L is a possible world of the query Q on the po-database D.
It is an indistinguishable antichain if it is both an antichain and an indistinguishable set. An indistinguishable antichain partition (ia-partition) of P is a partition of ID into indistinguishable antichains. The cardinality of the partition is the number of antichains. 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 Γ has ia-width at most |Γ|, 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). Theorem 5. 5. For any fixed k ∈ N and fixed PosRA no× query Q, the POSS problem for Q is in PTIME when each po-relation of the input po-database has either ia-width k or width k. To prove this result, we start by making a simple observation. Lemma 5. 6. Any PosRA no× query Q can be equivalently rewritten as a union of projections of selections of a constant number of input relations and constant relations. Proof. For the semantics that we have defined for operators, it it easy to show that 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 2. 2, argue that the width bounds are preserved using Lemma 2. 4, and compute a chain partition of the relations using Dilworth's theorem. Let us first show an analogue of Lemma 2. 4 for the new notion of ia-width. Lemma 5. 7. Let k 2 and Q be a PosRA no× query. For any po-database D of ia-width k, the po-relation Q(D) has ia-width max(k, q) × |Q|, where q denotes the largest value such that [ q] appears in Q. Proof. We first show by induction on Q that the ia-width of the query output can be bounded by a function of k. We show the base cases. • The input relations have ia-width at most k. • The constant relations have ia-width q with the trivial ia-partition consisting of singleton classes.
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 to Γ ′ following that match will answer YES. 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 POSS intractable when allowing both unordered and totally ordered inputs. Theorem 5. 12. There is a PosRA LEX query and a PosRA DIR query for which the POSS problem is NP-complete even when the input po-database is restricted to consist only of one totally ordered and one unordered po-relation.
Finite and Position-Invariant Accumulation We have shown that CERT (but not POSS) is tractable on cancellative accumulation operators. It is then natural to wonder whether a similar result holds when assuming that accumulation is finite and position-invariant (recall Definition 2. 11). We will now show that these restrictions do not suffice to make POSS and CERT tractable. However, we will show in Section 6. 3 that they can ensure tractability when we combine them with assumptions on the input po-relations. We start by showing that POSS is intractable. Theorem 6. 6. There is a PosRA acc query with a finite and position-invariant accumulation operator for which POSS is NP-hard even assuming that the input po-database contains only totally ordered po-relations. To prove this result, we define the following finite domains: • D -• • = {s -, n -, e -} (the element names used here intuitively correspond to the names used in the proof of Theorem 5.
3); • D + • • = {s + , n + , e + }; • D ± • • = D -⊔ D + ⊔ {l, r} ( the additional elements stand for "left" and "right"). We define the following regular expression on D * ± , and call balanced a word that satisfies it: e • • = l (s -s + |n -n + |e -e + ) * r We now define the following problem. Definition 6. 7. The balanced checking problem for a PosRA query Q asks, given a podatabase D of po-relations over D ± , whether there is L ∈ pw (Q(D)) such that L is balanced, i. e. , it has arity 1, its domain is D ± , and L satisfies e when seen as a word over D ±. We also introduce the following regular expression: e ′ • • = l D * ± r, which we will use later to guarantee that there are only two possible worlds. We now show that the balanced checking problem is intractable. Lemma 6. 8. There exists a PosRA query Q b over po-databases with domain in D ± such that the balanced checking problem for Q b is NP-hard, even when all input po-relations are totally ordered.
Further, Q b is such that, for any input po-database D, all possible worlds of Q b (D) satisfy e ′. To prove this lemma, recall the definition of ∪ CAT (Definition 2. 5), and recall from Lemma 2. 6 that ∪ CAT can be expressed by a PosRA query. We construct the query Q ′ b (R, T ) • • = [l] ∪ CAT ((R ∪ T ) ∪ CAT [r] ), i. e. , the union of R and T , preceded by l and followed by r. For any word w ∈ D * + , we denote by L + w the unary list relation defined by mapping each letter of w to the corresponding letter in D + , we define L - w analogously for D -, and we write Γ - w for the totally ordered po-relation with pw (Γ - w ) = {L - w }. We now claim that the balanced checking problem for Q ′ b can be rephrased in terms of the possibility problem. Lemma 6. 9. For any w ∈ D * + and unary po-relation Γ over D + , we have L + w ∈ pw (Γ) iff the po-database D mapping R to Γ - w and T to Γ is a positive instance to the balanced checking problem for Q ′ b.
What is more, by inspecting the construction in the proof of Theorem 5. 3, we can observe that the output arity of Q 0 is 1, and that the input relations can be assumed to have domain D + : indeed, the input po-relation S defined as [ 3m -1] uses labels that are irrelevant (they are projected away), and the input po-relation S ′ uses only labels from {s, n, e}, so we can rename them to {s + , n + , e + }. We now define the PosRA query Q b : its input relations are those of Q 0 plus a fresh relation name R, and it maps any po-relation Γ ′ for R and input po-database D for Q 0 to Q ′ b (Γ ′ , Q 0 (D)). By definition of Q ′ b , our query Q b clearly satisfies the additional condition that all possible worlds satisfy e ′. We reduce the POSS problem for Q 0 to the balanced checking problem for Q b in PTIME.
More specifically, we claim that (D, L) is a positive instance to POSS for Q 0 iff D ′ is a positive instance to the balanced checking problem for Q b , where D ′ is obtained from D by adding the totally ordered relation Γ - w to interpret the fresh name R, with w the word on D + achieved by L. But this is exactly what Lemma 6. 9 shows, for Γ := Q 0 (D). This concludes the reduction, so we have shown that the balanced checking problem for Q b is NP-hard, even assuming that the input po-database (here, D ′ ) contains only totally ordered po-relations. To prove our hardness result for POSS (Theorem 6. 6), we will now reduce the balanced checking problem to POSS, using an accumulation operator to do the job. We will further ensure that there are at most two possible results, which will be useful for CERT later.
This ensures that we have only two possible accumulation results, and that they accurately test whether the input word is balanced. We can now prove our hardness result for POSS, Theorem 6. 6. Proof. Consider the query Q b whose existence is guaranteed by Lemma 6. 8, and remember that all its possible worlds on any input po-database must satisfy e ′. Construct now the query Q a • • = accum h,• (Q b ), using the mapping h that we defined above, seen as a position-invariant accumulation map. We conclude the proof by showing that POSS is NP-hard for Q a , even when the input po-database consists only of totally ordered po-relations. To see that this is the case, we reduce the balanced checking problem for Q b to POSS for Q a with the trivial reduction: we claim that for any po-database D, there is a balanced possible world in Q b (D) iff f 1 ∈ Q a (D), which is proved by Lemma 6.
10. Hence, Q b (D) is balanced iff (D, f 1 ) is a positive instance of POSS for Q a. This concludes the reduction, and establishes our hardness result. We last show an analogue of Theorem 6. 6 for CERT as well. Theorem 6. 11. There is a PosRA acc query with a finite and position-invariant accumulation operator for which CERT is coNP-hard even assuming that the input po-database contains only totally ordered po-relations. Proof. Consider the query Q a from Theorem 6. 6. We show a PTIME reduction from the NPhard problem of POSS for Q a (for totally ordered input po-databases) to the negation of the CERT problem for Q a (for input po-databases of the same kind). Consider an instance of POSS for Q a consisting of an input po-database D and candidate result v ∈ M. Recall that the query Q a uses accumulation, so it is of the form accum h,⊕ (Q ′ ).
Revisiting Section 5 We now know that finiteness and position-invariance do not suffice to ensure the tractability of POSS and CERT. In this section, we will show that they can nevertheless be used to obtain tractability when combined with assumptions on the input po-database, as we did in Section 5. Specifically, in the rest of this section, we will always assume that accumulation is finite, and we will sometimes assume that it is position-invariant. We call PosRA acc LEX and PosRA acc no× the extension of PosRA LEX and PosRA no× with accumulation. We can first generalize our width-based tractability result on PosRA LEX (Theorem 5. 1) to PosRA acc LEX queries with finite accumulation. Theorem 6. 12. For any PosRA acc LEX query with a finite accumulation operator, POSS and CERT are in PTIME on po-databases of bounded width.
5) when accumulation is finite and position-invariant. Theorem 6. 14. For any PosRA acc no× query with a finite and position-invariant accumulation operator, POSS and CERT are in PTIME on po-databases whose relations have either bounded width or bounded ia-width. To do so, again, it suffices to show the following analogue of Lemma 5. 11 for finite and position-invariant accumulation. We then apply a dynamic algorithm whose state consists of the following: • for each chain in the partition of Γ, the position in the chain; • for each class A of the ia-partition of Γ ′ , 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.