dataesr/scientific-paragraphs-categorization huggingface dataset:
Results and analysis The SDDR map was computed with MCNP6. 2 and FISPACT combination, FLUKA and RayActive. Fig. 3  shows the final SDDR map at y = 0. 0 cm for benchmark #1 (Co) obtained with FLUKA, Fig. 4  shows the one obtained with RayActive and Fig. 5  the one obtained with MCNP and FISPACT combination. There is a good agreement between the three methods even if for FLUKA some lines can be seen. These lines may correspond to a lack of convergence due to the simulation performance of induced activation of FLUKA code (as the amount of simulated particles is equivalent for each of the three methods used). The SDDR maps for benchmarks #2 (SS316LN) are in appendix C and also shows a good agreement between results of all processes. To compare the results more precisely, the SDDR value was computed along x axis at y = 0 cm and z = 0 cm.
Finally, all these steps are unified in the same prototype method which makes the solution more stable and avoid code interface. Verification on benchmarks have been made and seem to give coherent results even if small discrepancies have been seen. Validation benchmark has been made on a more complex geometry. It also shows coherent results even if some discrepancies are noticeable in comparison with the traditional R2S computation. The difference could come from the neutron flux computation which is averaged on the whole voxel with the classical R2S. As the neutron flux is computed for each cell enclosed in voxel in RayActive, its results should be more precise. Nevertheless, these discrepancies will be investigated in more details in a further work to ensure that it comes from the neutron flux computation.
g. ,  Crabot et al. 2021). Furthermore, we showed that local species richness in undisturbed patches also decrease with connectivity loss once a threshold value of connectivity loss is reached. This result is corroborated by the empirical findings of  Horváth et al. (2019) , who used a dataset on invertebrate species in ponds spanning six decades of habitat loss to demonstrate that habitat loss also translates into species loss within the remaining habitats. Using patch connectivity as a common currency is promising to gain general insights on the ecological impact of disturbances, which are expected to be more intense and more frequent in the future  (Coumou et al. 2012; Harris et al. 2018). For the specific case of drying river networks, our study suggests some qualitative rules of thumb.
PRELIMINARIES Our results apply in both a relational database setting and a graph database setting. We first focus on the relational database setting, for which we loosely follow the preliminaries as presented in  [1]. We assume that we have countably infinite and disjoint sets Rel of relation names and Const of values. Furthermore, when ( 1 ,. ,   ) is a Cartesian tuple, we may abbreviate it as ā. A -ary database tuple (henceforth abbreviated as tuple) is an element of Const  for some  ∈ N. A relation is a finite set  of tuples of the same arity. We denote the set of all such relations by R. A database is a partial function  : Rel → R such that Dom() is finite. If  is a database and  ∈ Rel, we write ( 1 ,. ,   ) ∈  to denote that ( 1 ,. ,   ) ∈  (). By Adom() we denote the set of constants appearing in tuples of , also known as the active domain of.
For  ⊆ Dom(), the projection of  on  , written as   (), is the binding  ′ with Dom( ′ ) =  ∩ Dom() and  ′ () =  (), for every  ∈ Dom( ′ ). For a set  of bindings, the projection of  on  is   () =   ()  ∈. A match for  in  is a binding of Var() such that   ( ( ū )) ∈  for every  ∈ {1,. , }. 1  The set of answers to  on  is () =  FVar() ()  is a match for  in. We define answers as functions instead of database tuples, as this simplifies the presentation and as reasoning about their underlying domains is useful in further sections, when dealing with query decompositions. Threshold Queries. A threshold query (TQ) is an expression  of the form ( x) ∧ ∃ , ȳ  ( x, ȳ) where, from left to right, ( x) is a CQ,  ∈ N,  ∈ N ∪ {∞}, and  ( x, ȳ) is a CQ in which we do not require that every variable in x appears in one of its atoms.
Graph Databases. For the purposes of this paper, graph databases can be abstracted as relational databases with unary and binary relations. That is, a graph database can be seen as a database  with a unary relation Node and binary relations , ,. where • Node() ∈  if  is a node of the graph database and • 𝐴(𝑎 1 , 𝑎 2 ) ∈ 𝐺 if (𝑎 1 , 𝑎 2 ) is an edge with label  in the graph database. An important feature that distinguishes graph database queries from relational database queries are regular path queries (RPQs)  [13]. In a nutshell, a regular path query is an expression of the form  (, ), where  is a regular expression over the set of edge labels in the graph database. When evaluated over a graph database , the query returns all node pairs (, ) such that there exists a path from  to  that is labeled with some word in the language of.
EXPLOITING THRESHOLDS AT A GLANCE Query evaluation is arguably the most fundamental problem in databases and comes in many variants, such as: (E1) Boolean evaluation, i. e. , testing existence of an answer; (E2) returning a given number of answers; (E3) counting the total number of answers; (E4) sampling answers with uniform probability; and (E5) enumerating the answers with small delay. An important reason why all these variants are considered is that the set of answers to a query can be very large and one is not always interested in the set of all answers. The computational cost of these variants tends to increase as we go down in the list, but already for CQs even the simplest problem (E1) is intractable  [1, Chapter 15]. Triggered by Yannakakis' seminal result on efficient evaluation of acyclic CQs  [70] , the literature developed a deep understanding that teaches us that, essentially, low tree-width is not only helpful but even necessary for polynomialtime Boolean evaluation of CQs  [38].
Intuitively, the tree-width of a CQ measures the likeness of its graph structure to a tree. In essence, this graph structure is obtained by taking the queries' variables as nodes and connecting variables with an edge iff they appear in a common atom. Queries with low tree-width are tree-like and queries with high tree-width are highly cyclic. Example 3. 1. Consider the following variant of the first query from the introduction: (, , ) ← Assets(, ), Subsidiary(, ), Shareholder (, ). For the purpose of Boolean evaluation we can rewrite  as  ′ () ← Assets(, ),  () ;  () ← Subsidiary(, ),  () ;  () ← Shareholder (, ) using views  and. It is clear that one can materialize the views and answer  ′ in time   • log  over databases of size. The tree-width of  manifests itself as the number of variables used in the definitions of the views.
For CQs of tree-width , views in the optimal rewriting will use up to  variables and the data complexity will be    • log. For threshold queries, however, low tree-width is not sufficient. The reason is that it is already hard to decide if the number of results of an acyclic CQ is above a threshold (represented in binary). Proposition 3. 2. Given an acyclic conjunctive query , a threshold  in binary representation, and a database , testing if  returns at least  tuples on  is coNP-hard. So, we cannot have a polynomial-time algorithm even for evaluating Boolean acyclic threshold queries of the form ∃ , ȳ  ( ȳ), unless P = NP. This is why one focus in the paper is on pseudopolynomial-time algorithms for threshold queries of low tree-width. We call an algorithm pseudopolynomial, if it is a polynomial-time algorithm assuming that the numerical values  and  in "∃ , ȳ" are represented in unary (instead of binary).
In the enumeration phase it iterates over possible values of  and, for each value of , over the contents of the corresponding groups of Assets and. The complexity of the preprocessing phase is then affected by the cost of materializing  , which can be quadratic in the worst case. Overall, the complexity is  ( 2 • log ) over databases of size. Evaluating a threshold query is closely related to constant-delay enumeration and counting answers to CQs. Indeed, a threshold query of the form ∃ , ȳ  ( ȳ) can be evaluated by enumerating answers to  up to threshold  + 1 or by counting all answers to. For both these tasks, however, tractability relies on more restrictive parameters of the query. For enumeration, tree-width needs to be replaced with its free-connex variant  [5] , which treats answer variables in a special way.
One can evaluate  on a database  by computing   () bottom up, as follows. Assuming that  is nice, if  is a leaf then 𝑞 𝑢 (𝐷) = q𝑢 (𝐷) , if 𝑢 is a project node with child 𝑣 then 𝑞 𝑢 (𝐷) = 𝜋 FVar(𝑞 𝑢 ) 𝑞 𝑣 (𝐷) , and if  is a join node with children  1 and  2 then 𝑞 𝑢 (𝐷) = q𝑢 (𝐷) ⊲⊳ 𝑞 𝑣 1 (𝐷) ⊲⊳ 𝑞 𝑣 2 (𝐷). If  is free-rooted then FVar(  ) ⊆   for each  and the above computation can be performed in time Õ (| |  ), where  is the width of. The following simple fact will also be useful. Lemma 4. 2. Let  be a nice tree decomposition of a CQ. (1) For each node  in  it holds that   ⊆ FVar(  ). (2) If  is  -connex and  is the maximal  -connex set in  , then each node in  either has all its children in  or it is a  -leaf, that is, it has no children in. Tree decompositions are not easy to find. Indeed, determining if an arbitrary graph admits a tree decomposition of width at most  is NP-hard  [3].
Threshold queries via exact counting Processing a threshold query 𝑡 ( x) = 𝑞( x) ∧ ∃ 𝑎,𝑏 ȳ 𝑝 ( x, ȳ) involves counting, for each answer  in (), how many answers in  () are compatible to. Formally, this means that we need to determine the size of  (, ) for each  ∈ (), where  (, ) is the set of answers in  () that are compatible to. So we need to solve the following computational problem for. Counting answers to  grouped by  ⊆ FVar() over database  consists in computing all pairs (, ) such that  :  → Adom() and  = | (, )|. Counting answers can leverage low star-size  [31]. While the original notion is designed to fit hypertree decompositions, we shall work with a slightly faster growing variant that fits tree decompositions better and is much easier to define; the two variants coincide for queries using at most binary atoms.
This is readily visible for the star-size method, where the views correspond to the queries   in the definition of star-size of , but it is also true for the free-connex method: there, the views correspond to subtrees of the decomposition rooted at the shallowest nodes holding an existentially quantified variable. Hence, the methods can be used interchangeably and we can replace star-size with free-connex treewidth in Proposition 4. 3. Below, the  -rooted free-connex tree-width of a query is the minimal width of a tree decomposition of the query that is both  -rooted and free-connex. Proposition 4. 4. Counting answers grouped by  for conjunctive queries of  -rooted free-connex tree-width  over databases of size  can be done in time Õ. In particular, all answers to  can be counted in Õ  tw() •ss() by Proposition 4.
Consider the input database in Figure  2. Let us count the answers to  (, ) grouped by  and the answers to  (, ) grouped by  (using Proposition 4. 4) and store the resulting pairs in sets  { } and  { } , respectively. We get 𝑅 {𝑦 } = 𝑅 {𝑧 } = (𝑏 1 , 1), (𝑏 2 , 1), (𝑏 3 , 2), (𝑐 1 , 3), (𝑐 2 , 2) , where a pair (, ) in  { } means that for  =  there are  witnessing values of , and similarly for  { }. This is the initial information that we shall now propagate up the tree. In the set  {, } we put triples (, , ) such that (, ) and for  =  there are  witnessing values of ; analogously for  {, }. We get  {, } = ( 1 ,  1 , 1), ( 1 ,  2 , 1), ( 1 ,  3 , 2) ,  {, } = ( 1 ,  1 , 3), ( 1 ,  2 , 2). These sets can be computed based on  { } and  { } , respectively. The set  { } stores pairs (, ) such that  is the maximal number of witnessing pairs of values for  and  that any combination of  =  and  =  with (, ) and  (, ) can provide.
In our case,  { } = ( 1 , 6). Because  and  can be chosen independently from each other, we have 𝑘 = 𝑚 • 𝑛, where 𝑚 = max 𝑎 ℓ (𝑎, 𝑏, ℓ) ∈ 𝑅 {𝑥,𝑦 } and 𝑛 = max 𝑏 ℓ (𝑎, 𝑐, ℓ) ∈ 𝑅 {𝑥,𝑧 }. That is, the only information that needs to be passed from {, } to { } is the set  ′ {, } of pairs (, ) with  defined as above, and similarly for {, }. In our case,  ′ {, } = (, 2) and  ′ {, } = (, 3). We return YES iff  { } contains a pair (, ) with  ≥ 3. In our case, it is so. Theorem 4. 7. Boolean evaluation of an at-most or at-least query  of free-connex FTVar()-connex tree-width  over databases of size  can be done in time Õ (  ). The combined complexity of the algorithm is polynomial, assuming  is constant. In terms of combined complexity, Theorem 4. 7 is optimal as both conditions imposed on tree decompositions are needed.
Threshold problems for CQs In terms of data complexity, however, we can improve Theorem 4. 7. Here we exploit the presence of thresholds to handle queries with unbounded FTVar()-connex tree-width. We will cover not only at-least and at-most queries, but arbitrary TQs, and we will solve not only Boolean evaluation, but also constant-delay enumeration, counting answers, and sampling, all based on a single data structure. The small price we have to pay is pseudopolynomial combined complexity. Our starting point is again the problem of counting grouped answers, but this time up to a threshold. Counting answers to  grouped by  ⊆ FVar() up to a threshold  over database  consists in computing the set of pairs (, ) such that  :  → Adom() and  = min(, | (, )|). In the presence of a threshold, it is not impractical to solve counting by enumerating answers.
This is what we shall do. Computing answers to query  grouped by  ⊆ FVar() up to a threshold  over database  consists in computing a subset  of  () that is complete for  and ; i. e. , for each  :  → Adom() either  (, ) ⊆  and | (, )| ≤ , or | (, ) ∩ | =. Consider a CQ , a set  ⊆ FVar() of grouping variables, and a database. We will use the term group to refer to the set of answers to  that agree on the grouping variables  ; that is, a subset of  () of the form  (, ) for some  :  → Adom(). If the  -rooted tree-width of  is , then | | ≤  and the number of groups is  (| |  ). Consequently, if we can compute answers to  grouped by  up to threshold  in time Õ ( • | |  ), then we can also count them within the same time, because we will get at most  answers per group. Additionally, for each  :  → Adom() with  (, ) = ∅, we need to include (, 0) into the result; this does not affect the complexity bound.
Hence, it suffices to show how to compute answers grouped by  up to threshold. Having seen an illustrating example in Section 3, we are ready for the full solution. Theorem 4. 8. Computing answers grouped by  up to a threshold  for conjunctive queries of  -rooted tree-width  over databases of size  can be done in time Õ ( •   ). Proof sketch. Consider Algorithm 1. We begin by computing a nice  -rooted tree decomposition  of minimal width , as described in Section 4. 1. That is, each bag of  has size at most  and the root bag is. Consider the queries   associated to nodes  of. By Lemma 4. 2,   ⊆ FVar(  ). By analogy to the evaluation algorithm described in Section 4. 1, for each  we solve the problem of computing answers to   grouped by   up to threshold  over ; that is, we compute a subset   ⊆   () that is complete for   and.
Processing threshold queries We now turn to processing general threshold queries. We give a unified approach to constant-delay enumeration, counting, and sampling, based on a single data structure that can be computed using the methods presented in Section 4. 3. Example 4. 9. Consider again the database from Figure  2  and the query  from Example 4. 6. This time we shall work with the freeconnex tree decomposition  4 of  shown in Figure  1 ; it has smaller width than  3. Like before, the subqueries  (, ) and  (, ) correspond to bags {} and {}, respectively, and the subtrees rooted at these bags are {}-rooted (resp. {}-rooted) tree decompositions for these subqueries, but they are not free-connex. We count the answers to  grouped by  and the answers to  grouped by , up to threshold 3, as described in Section 4.
In our case, ( 1 , 1), ( 1 , 3) is chosen with probability 1  2 , and both ( 1 , 2), ( 1 , 3) and ( 1 , 2), ( 1 , 2) with probability 1  4. Finally, we sample (, , ) and (, , ) uniformly among relevant triples in  {, } and  {, } , respectively, and we return (, , ). In our case, for ( 1 , 1), ( 1 , 3) we choose either ( 1 ,  1 , 1), ( 1 ,  1 , 3) or ( 1 ,  2 , 1), ( 1 ,  1 , 3) with probability 1  2 , and for ( 1 , 2), ( 1 , 3) and ( 1 , 2), ( 1 , 2) there is only one choice; overall, each answer is returned with probability 1  4. Theorem 4. 10. For TQs of free-connex tree-width , over databases of size , one can: count answers in time Õ (  ); enumerate answers with constant delay after Õ (  ) preprocessing; and sample answers uniformly at random in constant time after Õ (  ) preprocessing.
Assuming  is constant, the combined complexity of each of these algorithms is pseudopolynomial. Compared to  [5, 31] , this theorem provides the same complexity guarantees as for counting answers and enumerating answers for conjunctive queries, but we are able to generalize these to threshold queries (and add sampling). This generalization comes at the small cost of dependence on the value of the threshold. The results in  [5, 31]  can be strengthened to more refined measures such as hypertreewidth, but we believe that this is also true here. Proof sketch. Consider a database  and a threshold query 𝑡 ( x) = 𝑞( x) ∧ ∃ 𝑎,𝑏 ȳ 𝑝 ( x, ȳ). We write  for the threshold up to which we will be counting witnesses: if  < ∞, we let  =  + 1; if  = ∞, we let  =. Let  be a nice free-connex tree decomposition of , of width , and let  be the maximal free-connex set in.
Qualitative Study To demonstrate further the usefulness of threshold queries in practice across diverse contemporary domains, we also performed a qualitative study on two real-world graph datasets. Covid-19 Dataset. The Covid-19 Knowledge Graph  [25]  is a continuously evolving dataset, with more than 10M nodes and 25M edges, obtained by integrating various data sources, including gene expression repositories (e. g. , the Genotype Tissue Expression (GTEx) and the COVID-19 Disease Map genes), as well as article collections from different scientific domains (ArXiv, BioRxiv, MedRxiv, PubMed, and PubMed Central). The inferred schema of this graph exhibits more than 60 distinct node labels and more than 70 distinct edge labels  [53]. Such typing information is, however, not sufficient to express the domain-specific constraints that can be found in these real-life graph datasets.
Non-trivial constraints expressible with threshold queries can be naturally crafted in order to complement the schema, as we showcase in our study. Wikidata Dataset. Wikidata is a collaborative knowledge base launched in 2012 and hosted by the Wikimedia Foundation  [66]. By the efforts of thousands of volunteers, the project has produced a large, open knowledge base with numerous applications. Wikidata can be seen as a graph database which has a SPARQL endpoint that lets users and APIs formulate queries on the its massive knowledge graph. The query logs collected along the years on this endpoint  [52]  constitute a useful resource for the qualitative analysis of threshold queries. Working Method. We have manually inspected the Covid-19 Knowledge Graph schema in search of constraints that can be validated with threshold queries.
We have also found a number of threshold queries by sieving through a large sample of Wikidata query logs. We analyzed the structural properties of the collected threshold queries. Below we discuss our findings with the help of five selected threshold queries from the two datasets. The queries  Selected Queries. The first example comes from the Wikidata logs and appears to be a data exploration query. TQ1 Return all given names with more than 1000 occurrences. SELECT ? name WHERE { ? person < given_name > ? name } GROUP BY ? name HAVING ( ( COUNT (*) > 1000 ) ); A structurally similar query can help detect integrity violations in the Covid-19 Knowledge Graph. Namely, the latest release (June 2021) of the Gene Ontology (GO) contains 43917 valid terms  [23, 24]. Therefore, in the Covid-19 Knowledge Graph one can check whether a protein is suspicious if it exhibits more than this number of GO terms associated to it.
Experimental Study As a proof-of-concept, we implemented the algorithm in Theorem 4. 8 in SQL and compared it with the optimizer of a popular DBMS engine, namely the PostgreSQL 13. 4 optimizer. Using SQL windowing functions, our implementation can mimic some important aspects of our query evaluation algorithm (like internal information passing up to a threshold), but we note that SQL does not allow to capture our algorithm precisely. As shown in the remainder, the results of this comparison already show the superiority of our algorithm for threshold queries compared to naive evaluation. All the experiments were executed on an Intel Core i7-4770K CPU @ 3. 50GHz, 16GB of RAM, and an SSD. We used PostgreSQL 13. 4 in Linux Mint 20. 2 and built our own micro-benchmark  [12]  consisting of the following three types of query templates: (q1) -path selects up to 10 pairs of nodes linked by a -hop path; (q2) -neigh selects all nodes with ≥ 10 -hop neighbors; (q3) -conn selects all pairs of nodes linked by ≥ 10 -hop paths.
Assuming that the database consists of a single binary relation , then these queries for  = 2 can be naturally formulated in SQL as: In the following, we will refer to these formulations as the baseline formulations of the queries. We compared these queries with alternative formulations in SQL that mimic crucial aspects of our evaluation algorithm and that can be understood as follows. A simple decomposition for -path is a tree with a single branch and one node per each joined copy of table R. For this decomposition and  = 2 the algorithm in Theorem 4. 8 amounts to evaluating the following query: For -neigh we can use the same decomposition and the corresponding query is the same except for the last line which is SELECT X0 FROM S1 GROUP BY X0 HAVING count (*) >=10; For -conn we can also use the same decomposition but the corresponding query is a bit different, as we need to collect the whole paths, not just their endpoints.
We refer to these alternative implementations as the windowed versions of the queries. Natural query plans for the windowed versions have worst-case complexity Õ ( • ) for -path and -neigh, and Õ ( •  2 ) for -conn. Datasets. We considered two kinds of data sets: (1) The real-world IMDb data set used in Join Order Benchmark  [54] , which contains information about movies and related facts about actors, directors, production companies, etc. In our experiments, we focused on the movie_link relation, which has a graph-like structure, so that finding paths is meaningful. (2) A number of synthetic data sets, which are Barabási-Albert graphs  [7]  with varying parameters of  (total number of nodes to add) and  0 (the number of edges to attach from newly added nodes to existing nodes). 4 e repeated each experiment several times and report the median.
First Experiment. We compared the running time of the baseline and windowed versions of (q1-q3) for varying values of  on both the IMDb and synthetic data sets, both on fully indexed and non-indexed databases. Table  2  shows the results for the nonindexed case. We see that our approach (windowed) outperforms the baseline with speedups up to three orders of magnitude, while the baseline times out (T/O) for higher values of. The running times of the windowed versions reflect the good theoretical bounds, while the baseline clearly shows exponential dependence on. For the indexed case, leveraging the DBMS's default indexes, the baseline ran only marginally faster (∼5%), remaining three orders of magnitude slower than our algorithm. Second Experiment. In this second experiment, we wanted to assess the impact of the structure and size of the data on the runtimes of our algorithm.