ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

The causes of infertility should be a national challenge for French society to combat it

Samir Hamamah

To cite this version:

Samir Hamamah. The causes of infertility should be a national challenge for French society to combat it. Gynécologie Obstétrique Fertilité & Sénologie, 2022, 50 (7-8), pp.503-504. 10.1016/j.gofs.2022.06.004. hal-04468065

E ´ditorial
La lutte contre l'infertilite ´doit e ˆtre un de ´fi national pour la socie ´te franc ¸aise

The causes of infertility should be a national challenge for French society to combat it Aujourd'hui en France, comme dans la plupart des pays de ´veloppe ´s, un couple sur quatre en de ´sir d'enfants ne parvient pas a `obtenir une grossesse apre `s 12 mois d'essai, de ´lai correspondant a `la de ´finition de l'infertilite ´par l'OMS [START_REF] Messaoud | Infertility treatment in France, 2008-2017: a challenge of growing treatment needs at older ages[END_REF]. Une e ´tude mene ´e par l'Ined estime que le risque d'infertilite ´est effectivement d'environ 1 couple sur 4 a `30 ans a `1 couple sur 3 a 35 ans et a `plus d'un couple sur 2 a `40 ans [START_REF] Leridon | Can assisted reproduction technology compensate for the natural decline in fertility with age? A model assessment[END_REF]. Avec 3,3 millions de personnes directement touche ´es en France, l'infertilite ´est devenue un enjeu majeur de sante ´publique, sans pour autant avoir jamais e ´te ´traite ´e comme telle par les pouvoirs publics. Car la pre ´vention de l'infertilite ´doit se concevoir au niveau individuel, collectif, social et politique. Pour tenir compte des e ´volutions du monde moderne, la socie ´te ´doit permettre aux femmes qui souhaitent avoir des enfants, de mener a `bien ce projet lorsque leur fe ´condite ´est optimale, sans que ce choix porte atteinte a `leur carrie `re. C'est trop souvent l'accumulation de ces causes, individuelles et collectives, environnementales et socie ´tales, qui conduit les couples a `ne pas pouvoir concevoir et a `ne pas parvenir a `fonder une famille.

Une re ´cente e ´tude [START_REF] Skakkebaek | Environmental factors in declining human fertility[END_REF] re ´ve ´lait que la concentration de spermatozoı ¨des dans le sperme a diminue ´de plus de 50 % en moins de quarante ans (1973-2011) chez les hommes occidentaux, soit une diminution de 1,4 % par an. Fait pre ´occupant, cette e ´tude n'observe aucune atte ´nuation de la baisse dans les anne ´es les plus re ´centes. Il apparaı ˆt donc indispensable de concilier le message d'information avec le libre choix des personnes pour re ´aliser ou pas son projet parental.

  La lutte contre toutes les causes d'infertilite ´(me ´dicales, environnementales et socie ´tales) et la juste information sur la sante ´reproductive constituent en re ´alite ´les maillons indispensables et comple ´mentaires a `l'information sur la sante ´sexuelle du droit individuel a `la maı ˆtrise de la procre ´ation. L'instauration d'une politique de pre ´vention ambitieuse ne repre ´senterait pas ne ´cessairement un surcou ˆt pour les finances publiques et e ´viterait ainsi a `de nombreux jeunes d'e ˆtre expose ´s au proble `me d'infertilite ´. Il apparaı ˆt donc ne ´cessaire de mieux informer les femmes et les hommes du fonctionnement de leur appareil reproductif et des facteurs susceptibles d'alte ´rer leur fertilite ´. Cette information devrait e ˆtre faite suffisamment to ˆt dans la vie des individus pour que l'information ne soit pas perc ¸ue comme anxioge `ne et que l'individu l'assimile comme e ´tant neutre. En matie `re d'information collective, un double levier peut e ˆtre actionne ´, celui de l'enseignement scolaire et celui d'une information grand public sur la sante ´reproductive. Pour les adolescents, il faudra renforcer l'enseignement de la sante ´reproductive par l'e ´ducation nationale dont le ro ˆle est essentiel et mobiliser ainsi les re ´seaux sociaux. Les adolescents sont sensibilise ´s a `la ne ´cessite ´de se prote ´ger lors des rapports sexuels pour e ´viter les MST et les grossesses non-de ´sire ´es, mais le risque d'infertilite ´n'est jamais e ´voque ´. Pour cela, il faudra inte ´grer dans le programme scolaire, au colle `ge et au lyce ´e, une se ´ance supple ´mentaire, d'une dure ´e d'1 h 30 par an, consacre ´e a `la fertilite ´et a `ses facteurs d'alte ´ration. Le programme propose ´pourrait e ˆtre construit par cycles, abordant chaque anne ´e les me ˆmes the ´matiques mais s'adaptant au niveau de compre ´hension de l'enfant, puis de l'adolescent. Dans la lutte contre l'infertilite ´, une approche holistique, lucide, coordonne ´e et d'ampleur nationale est indispensable. La cre ´ation d'un Institut national de la fertilite ´devrait e ˆtre une priorite ´nationale pour incarner, impulser, piloter et coordonner la recherche, les actions de pre ´vention et la prise en charge des couples infertiles. Il s'agit d'un de ´fi que repre ´sente la fertilite ´des couples pour la nation, depuis ses causes jusqu'au parcours d'AMP. De ´claration de liens d'inte ´re ˆts L'auteur de ´clare ne pas avoir de liens d'inte ´re ˆts. Gyne ´cologie Obste ´trique Fertilite ´& Se ´nologie 50 (2022) 503-504 I N F O A R T I C L E Mots cle´s : Lutte contre l'Infertilite Á sur ScienceDirect www.sciencedirect.com https://doi.org/10.1016/j.gofs.2022.06.004 2468-7189/ C 2022 Elsevier Masson SAS. Tous droits re ´serve ´s.


Wafaa El

Cheikh Brahim
email: cheikh-brahim.el-vaigh@u-bourgogne.fr

El Vaigh

François Goasdoué

Hélène Jaudoin
email: helene.jaudoin@irisa.fr

Query Optimization for Ontology-Mediated Query Answering

Keywords: Information systems → Query optimization, Semantic web description languages, • Computing methodologies → Knowledge representation and reasoning Existential rules, query optimization, data summarization

Ontology-mediated query answering (OMQA) consists in asking database queries on knowledge bases (KBs); a KB is a set of facts called the KB's database, which is described by domain knowledge called the KB's ontology. A widely-investigated OMQA technique is FO-rewriting: every query asked on a KB is reformulated w.r.t. the KB's ontology, so that its answers are computed by the relational evaluation of the query reformulation on the KB's database. Crucially, because FO-rewriting compiles the domain knowledge relevant to queries into their reformulations, query reformulations may be complex and their optimization is the crux of efficiency.

We devise a novel optimization framework for a large set of OMQA settings that enjoy FO-rewriting: conjunctive queries, i.e., the core select-project-join queries, asked on KBs expressed using datalog±, description logics, existential rules, OWL, or RDFS. We optimize the query reformulations produced by state-of-the-art FO-rewriting algorithms by computing rapidly, with the help of a KB's database summary, simpler (contained) queries with the same answers that can be evaluated faster by RDBMSs. We show on a well-established OMQA benchmark that time performance is significantly improved by our optimization framework in general, up to three orders of magnitude.

CCS CONCEPTS

•

INTRODUCTION

Ontology-mediated query answering [START_REF] Bienvenu | Ontology-Mediated Query Answering: Harnessing Knowledge to Get More from Data[END_REF] (OMQA) is a widely studied data management problem in Artificial Intelligence, Databases and Semantic Web. It consists in asking database-style queries on knowledge bases (KBs). A KB is a first-order (FO) theory that consists of a set of facts called a database, which models the application's data, and of a set of axioms called an ontology, which models the application's domain knowledge. The notable difference between this query answering setting and the traditional database one is that the answers to queries must be computed w.r.t. both the facts that are stored in the KB's database and the facts that can be deduced from the KB's database with the help of the KB's ontology.

There exist two main OMQA techniques in the literature. Both reduce OMQA to standard query evaluation on relational databases. The first technique is called FO-rewriting, e.g., [START_REF] Calvanese | Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family[END_REF]. It consists in rewriting a query asked on a KB into a so-called query reformulation, so that the query answers are obtained by evaluating the query reformulation on the KB's database. The second technique is called materialization, e.g., [START_REF] Abiteboul | Foundations of Databases[END_REF]. It consists in adding to the KB's database all the facts than can be deduced from it with the KB's ontology, so that the query answers are obtained by evaluating the (original) query on the augmented KB's database. The combination of FO-rewriting and materialization, called the combined or hybrid approach, has also been investigated, e.g., [START_REF] Kontchakov | The Combined Approach to Ontology-Based Data Access[END_REF]. Crucially, both FOrewriting and materialization are useful because, although there exist simple OMQA settings in which they compete, e.g., [START_REF] Afnan | ForBackBench: A Benchmark for Chasing vs. Query-Rewriting[END_REF], there also exist more expressive OMQA settings to which only a single technique applies, e.g., [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF].

In this paper, we focus on FO-rewriting. It has been mainly studied in OMQA settings consisting of (e.g., Table 1): queries expressed as conjunctive queries (CQs); KBs expressed using datalog±, description logics, existential rules, OWL, or RDFS; query reformulations expressed as unions of CQs (UCQs), unions of semi-CQs (USCQs), joins of UCQs (JUCQs), or non-recursive datalog programs (datalog 𝑛𝑟 ). These reformulation languages are recalled in Appendix A. We consider all these OMQA settings in this work.

Standard OMQA via FO-rewriting is illustrated in Figure 1. It consists in producing a query reformulation 𝑞 O from a query 𝑞 and the ontology O of the KB K, and then in evaluating 𝑞 O on the database D of K stored in an RDBMS. We point out that a query reformulation 𝑞 O may be large and complex to evaluate, e.g., [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Gottlob | Rewriting Ontological Queries into Small Nonrecursive Datalog Programs[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF]. FO-rewriting is indeed both ontology-dependent and data-independent, hence 𝑞 O must accomodate to all the possible databases and cannot be specific to the particular database D of K.

So far, and similarly to semantic query optimization for deductive databases, e.g., [START_REF] Upen | Logic-Based Approach to Semantic Query Optimization[END_REF], query optimization for FO-rewriting has focused on studying equivalent representations of query reformulations that can be evaluated faster: minimal (e.g., [START_REF] Chortaras | Optimized Query Rewriting for OWL2QL[END_REF][START_REF] König | Sound, complete and minimal UCQ-rewriting for existential rules[END_REF]), compact (e.g., [START_REF] Gottlob | Rewriting Ontological Queries into Small Nonrecursive Datalog Programs[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF]) or cost-based (e.g., [START_REF] Bursztyn | Optimizing Reformulation-based Query Answering in RDF[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF]) reformulations. However, because these optimizations are ontology-dependent and dataindependent, optimized query reformulations remain complex to evaluate. They correspond to syntactically different but semantically equivalent variants of non-optimized query reformulations, thus they still need to accommodate to all the possible databases, and not to just the fixed database at hand. The main contribution of this paper is a novel optimization framework for OMQA via FO-rewriting. It is illustrated in Figure 1. This framework capitalizes on the ontology-dependent and dataindependent query optimization for FO-rewriting that have been studied so far in the literature (Reformulation step in Figure 1). Its originality is to include complementary data-dependent query optimization for FO-rewriting (Summarization and Optimization steps in Figure 1). Its purpose is to optimize the query reformulation 𝑞 O produced by any off-the-shelf FO-rewriting algorithm into a query reformulation 𝑞 K that is optimized for the particular database D of K: 𝑞 K is simpler than 𝑞 O , as it just needs to accommodate to D, so that it can be evaluated faster; at the same time it has the same answers as 𝑞 O on D in order to guarantee the correctness of query answering on K. Crucially, 𝑞 O is optimized for D using a summary S of D, which is a typically small approximation of D. This allows a trade-off between optimization time and the extent to which 𝑞 K is optimized for D.

More specifically, our optimization framework builds on the following contributions. 1/ We formalize the problem of data-dependent optimization of a query reformulation using the well-known notion of query containment [START_REF] Abiteboul | Foundations of Databases[END_REF] (Section 3). 2/ We devise an optimization function Ω that rewrites a query reformulation into a simpler contained one, i.e., a simpler more specific one, with the same answers on a fixed database (Section 4.1). Containment and query answering correctness are ensured by appropriately removing useless subqueries from the query reformulation, i.e., subqueries that do not participate in producing answers on the given database while they may take time to be evaluated. 3/ We define a summary of a database, which is a (typically smaller) homomorphic database (Section 4.1). A summary can be used by our Ω optimization function in place of the original database to perform faster a sound but incomplete identification and removal of useless subqueries. Then, we adapt the quotient operation from graph theory [START_REF]Handbook of Graph Theory[END_REF] in order to build concrete summaries tailored to our needs (Section 4.2): both small summaries for fast optimization time and precise summaries to limit the incompleteness of identifying useless subqueries. DL-Lite R is the description logic that underpins the W3C's OWL2 QL profile for OMQA on large KBs [START_REF] Calvanese | Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family[END_REF]. We show that our optimization framework significantly improves query answering time performance (up to 3 orders of magnitude).

The paper is organized as follows. We present OMQA and FOrewriting in Section 2. We introduce our optimization framework and we formalize the underlying research problem in Section 3. We devise a solution (Ω optimization function and database summaries) to this problem in Section 4 and we experimentally evaluate this solution in Section 5. Finally, we conclude with related work and perspectives in Section 6. Proofs are available in the appendix.

This paper is an in-depth presentation of our optimization framework that was briefly introduced in the demonstration paper [START_REF] Husseini | OptiRef: Query Optimization for Knowledge Bases[END_REF].

PRELIMINARIES

KBs. We consider FO KBs expressed using datalog± or existential rules [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF][START_REF] Calì | Datalog ± : a unified approach to ontologies and integrity constraints[END_REF][START_REF] Calì | A general datalogbased framework for tractable query answering over ontologies[END_REF][START_REF] Calì | Datalog+/-: A Family of Logical Knowledge Representation and Query Languages for New Applications[END_REF][START_REF] Calì | A logical toolbox for ontological reasoning[END_REF], which we call rules hereafter. A KB K is of the form K = (O, D), where O is the KB's ontology and D is the KB's database. An ontology O is a set of rules of the form ∀x (𝑞 1 ( x) → 𝑞 2 ( x)), where 𝑞 1 and 𝑞 2 are CQs (recall Appendix A) with the same set x of answer variables. Rules are used to derive entailed facts in the KB. A database D is a set of incomplete facts, i.e., whose terms are constants and existential variables modeling unknown values [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Imielinski | Incomplete Information in Relational Databases[END_REF], which we call facts from now. The semantics of a KB K = (O, D) is that of the FO formula rule∈ O ∧∃v ( fact∈ D ), where v is the set of variables that appear in D.

Notation. We use small letters to denote constants, e.g., f, h, etc., and small italic letters to denote variables, e.g., 𝑥, 𝑦, etc. Also, we omit quantifiers in rules: existential variables solely appear on the right-hand side of → by virtue of FO semantics (see Appendix B).

Example 2.1 (Running example). Let us consider the following DL-Lite R KB K = (O, D), here expressed using rules [START_REF] Calì | A general datalogbased framework for tractable query answering over ontologies[END_REF]: 1 where CQs are reformulated into UCQs, USCQs, JUCQs or datalog 𝑛𝑟 programs. We therefore term FO-rewriting setting a triple of query language L 𝑄 , KB language L 𝐾 and query reformulation language L 𝑅 , denoted by (L 𝑄 , L 𝐾 , L 𝑅 ), such that (L 𝑄 , L 𝐾 ) is an FO-rewritable OMQA setting for which query reformulations are expressed in L 𝑅 .

O = {𝑟 1 = 𝑤𝑤 (𝑥, 𝑦) → 𝑤𝑤 (𝑦, 𝑥), 𝑟 2 = 𝑠𝑢𝑝 (𝑥, 𝑦) → 𝑤𝑤 (𝑥, 𝑦), 𝑟 3 = 𝑃ℎ𝐷 (𝑥) → 𝑠𝑢𝑝 (𝑦, 𝑥)}, D ={𝑅(f), 𝑅(h), 𝑠𝑢𝑝 (f, w), 𝑠𝑢𝑝 (h, w), 𝑃ℎ𝐷 (w), 𝑤𝑤 (f, h), 𝑅(𝑢), 𝑤𝑤 (
In this paper, we focus on FO-rewriting settings with queries expressed in the language of CQs and query reformulations expressed in the languages of UCQs, USCQs and JUCQs. These setting are widely considered in the literature on FO-rewriting (recall Table 1). We remark that datalog 𝑛𝑟 reformulations may need to be unfolded into UCQs reformulations, which we consider, to be (efficiently) evaluated by RDBMSs.

A key property of the FO-rewriting settings that we consider, on which our work relies, is that a query reformulation 𝑞 O is equivalent to the CQ 𝑞 w.r.t. O. In particular, 𝑞 O is equivalent, regardless of the language used to express it, to the union of all the CQs that are maximally-contained in 𝑞 w.r. [START_REF] Chortaras | Optimized Query Rewriting for OWL2QL[END_REF], Compact [START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF] and GDL [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF] FO-rewriting tools:

𝑞 O UCQ (𝑥 ) = (𝑅 (h) ∧ 𝑤𝑤 (h, 𝑥 ) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) (1) ∨(𝑅 (h) ∧ 𝑤𝑤 (h, 𝑥 ) ∧ 𝑃ℎ𝐷 (𝑥 ) ) (2) ∨(𝑅 (h) ∧ 𝑠𝑢𝑝 (h, 𝑥 ) ) (3) ∨(𝑅 (h) ∧ 𝑤𝑤 (𝑥, h) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) (4) ∨(𝑅 (h) ∧ 𝑤𝑤 (𝑥, h) ∧ 𝑃ℎ𝐷 (𝑥 ) ) (5) ∨(𝑅 (h) ∧ 𝑠𝑢𝑝 (𝑥, h) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) (6) ∨(𝑅 (h) ∧ 𝑠𝑢𝑝 (𝑥, h) ∧ 𝑃ℎ𝐷 (𝑥 ) ) (7) 𝑞 O USCQ (𝑥 ) = (𝑅 (h) ) ∧ (𝑤𝑤 (h, 𝑥 ) ∨ 𝑠𝑢𝑝 (h, 𝑥 ) ∨ 𝑤𝑤 (𝑥, h) ∨ 𝑠𝑢𝑝 (𝑥, h) ) ∧ (𝑠𝑢𝑝 (𝑦, 𝑥 ) ∨ 𝑃ℎ𝐷 (𝑥 ) ) 𝑞 O JUCQ (𝑥 )=(𝑅 (h) ) ∧ (𝑤𝑤 (h, 𝑥 ) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) ∨(𝑤𝑤 (h, 𝑥 ) ∧ 𝑃ℎ𝐷 (𝑥 ) ) ∨(𝑠𝑢𝑝 (h, 𝑥 ) ) ∨(𝑤𝑤 (𝑥, h) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) ∨(𝑤𝑤 (𝑥, h) ∧ 𝑃ℎ𝐷 (𝑥 ) ) ∨(𝑠𝑢𝑝 (𝑥, h) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) ∨(𝑠𝑢𝑝 (𝑥, h) ∧ 𝑃ℎ𝐷 (𝑥 ) )
𝑞 O UCQ is the union of all the maximally-contained CQs in 𝑞 w.r.t. O.

𝑞 O

USCQ and 𝑞 O JUCQ model the same union up to the distributive property of ∧ and ∨. The answer to 𝑞 on K (i.e., w) results from (3) in 𝑞 UCQ , shown in blue, and from the logical combination of the subqueries shown in blue in 𝑞 O USCQ and 𝑞 O JUCQ , from which (3) can be recovered by distributing the ∧'s over the ∨'s. ⋄

OPTIMIZATION PROBLEM

Motivation. The definition of FO-rewriting is data-independent: a single query reformulation 𝑞 O is able to answer the CQ 𝑞 on all the KBs with ontology O. This generality of 𝑞 O follows from the fact that it is equivalent to the union of all the CQs that are maximally-contained in 𝑞 w.r.t. O, which can also be regarded as all the ways databases may store answers to 𝑞 according to O. As a consequence, a query reformulation may be large and complex to evaluate in practice [START_REF] Bursztyn | Optimizing Reformulation-based Query Answering in RDF[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF]. For instance, the worst-case number of CQs that are maximally-contained in a CQ 𝑞 w.r.t. a lightweight RDFS, DL-Lite R or datalog± 0 ontology, is exponential in the size of the CQ 𝑞 (number of atoms) [START_REF] Buron | Reformulation-Based Query Answering for RDF Graphs with RDFS Ontologies[END_REF][START_REF] Calvanese | Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family[END_REF][START_REF] Goasdoué | Efficient query answering against dynamic RDF databases[END_REF][START_REF] Gottlob | Query Rewriting and Optimization for Ontological Databases[END_REF]. Rationale behind our optimization problem. We study the datadependent optimization of a query reformulation for a particular KB, in order to trade its generality for more OMQA performance.

When the query 𝑞 is asked on a given KB K = (O, D), the database D is indeed fixed and just one of all the possible databases a reformulation 𝑞 O accommodates to. In particular, within the union of maximally-contained CQs to which 𝑞 O is equivalent, many CQs may be irrelevant to D, because they have no answer on D (i.e., D do not store answers to 𝑞 w.r.t. O this way), and translate into wasteful evaluation time.

Example 3.1 (Cont.). In 𝑞 O UCQ , all the CQs except the CQ (3) are irrelevant to D, and similarly in 𝑞 O USCQ and 𝑞 O JUCQ , where these CQs are present up to the distribution of the ∧'s over the ∨'s. ⋄ Problem statement. Our goal is to devise an optimization framework for OMQA via FO-rewriting that enjoys the following properties: generality to be used in as many FO-rewriting settings as possible, correctness to compute the exact answer set of a query, and effectiveness to improve query answering time performance.

Our framework relies on an optimization function Ω that turns a given query reformulation 𝑞 O into an optimized query reformulation for a given database D. This optimized query reformulation is hereafter denoted by 𝑞 K as it is specific to the KB K = (O, D).

For the generality of our framework, the Ω function optimizes query reformulations from the language of (∧, ∨)-combinations of CQs (Definition 3.2 below), which includes UCQ, USCQ and JUCQ reformulations.

Definition 3.2 ((∧, ∨)-combination of CQs). A (∧, ∨)-combination

of CQs, denoted by (∧, ∨)-CQ, is either a CQ or a conjunction or union of (∧, ∨)-CQs.

The Ω function computes an optimized query reformulation 𝑞 K contained in 𝑞 O (item 1 in Problem 1 below) since 𝑞 O is equivalent to a union of maximally-contained queries, in which we remove those irrelevant to a database D, and removing disjuncts from a union makes it more specific. However, this containment relationship only ensures that the answers to 𝑞 K form a subset of the answers to 𝑞 O on all possible databases. For the correctness of our framework, Ω thus computes an optimized query reformulation 𝑞 K with same answers as 𝑞 O on D (item 2 in Problem 1 below).

Finally, for the effectiveness of our framework, the Ω function optimizes 𝑞 O for D using a summary S of D (item 3 in Problem 1 below). This allows for a trade-off between the number of removed irrelevant maximally-contained queries and the cost to remove them, which translates into optimization time. As we shall see in our experiments, the optimization time may be too high to improve OMQA time performance when Ω identifies irrelevant maximallycontained queries in 𝑞 O using the database D instead of a typically much smaller summary S of it.

We summarize the above discussion with the formal statement of the research problem studied in this paper.

Problem 1 (Summary-based optimization of FO-rewriting).

Let 𝑞 O be a (∧, ∨)-CQ query reformulation and let D be a database. Define an optimization function Ω and a summary S of D so that the optimization of 𝑞 O for D using S, denoted by 𝑞 K and computed by Ω(𝑞 O , S), satisfies: and 𝑅(h) ∧ 𝑠𝑢𝑝 (𝑥, h) ∧ 𝑃ℎ𝐷 (𝑥): without 𝑠𝑢𝑝 (𝑥, h), they cannot be recovered by distributing the ∧'s over the ∨'s. We therefore devise the Ω function to optimize a (∧, ∨)-CQ query reformulation for a given database by rewriting it from the bottom up to (𝑖) identify subCQs with no answer on this database and (𝑖𝑖) propagate the effect of their removal within the query reformulation.

(1) 𝑞 K ⊆ 𝑞 O , (2) 𝑒𝑣𝑎𝑙 (𝑞 K , D) = 𝑒𝑣𝑎𝑙 (𝑞 O , D), (3) 𝑐 (Ω(𝑞 O , S)) +𝑐 (𝑒𝑣𝑎𝑙 (𝑞 K , D)) ≤ 𝑐 (𝑒𝑣𝑎𝑙 (𝑞 O , D))
Identifying CQs with no answer on a database. Checking if a single CQ has no answer on a database can be done easily (e.g., using exists in SQL) and efficiently in general since RDBMSs are highlyoptimized for CQs, e.g., [START_REF] Silberschatz | Database System Concepts, Seventh Edition[END_REF]. However, doing the same check for all the subCQs in a query reformulation may take significant time, especially when the database is large. To mitigate this issue, the Ω optimization function uses database summaries that are (typically small) homomorphic approximations of the databases they summarize. Using such summaries instead of the databases allows trading completeness of identifying subCQs with no answer for efficiency, while retaining soundness. In the above definition, (𝑖) ensures that S is a homomorphic approximation of D, while (𝑖𝑖) ensures the soundness of identifying CQs with no answer on D using S (Theorem 4.2 below). Also, we remark that a database is a particular summary of itself: D = S holds when the database-to-summary homomorphism 𝜎 maps each term to itself, i.e., when 𝜎 is the identity function. Theorem 4.2. Let D be a database and S a summary of it with the homomorphism 𝜎. Let 𝑞 be a CQ 𝑞 asked on D and 𝑞 𝜎 the CQ obtained from 𝑞 by replacing its constants with their images through 𝜎. If 𝑞 𝜎 has no answer on S, then 𝑞 has no answer on D.

We stress that, as illustrated below, if 𝑞 𝜎 has no answer on S then for sure 𝑞 has no answer on D, while if 𝑞 𝜎 has some answer on S then 𝑞 may or may not have an answer on D. Let 𝑞 be a (∧, ∨)-CQ asked on a database D and S be a summary of D with the homomorphism 𝜎. The optimization of 𝑞 for D using S, i.e., denoted by Ω(𝑞, S), is recursively defined as follows. Below, ∅ denotes the empty relation with appropriate arity.

The optimization of a CQ 𝑞 is:

Ω(𝑞, S) = ∅ if 𝑒𝑣𝑎𝑙 (𝑞 𝜎 , S) = ∅ 𝑞 otherwise (1)
where 𝑞 𝜎 is obtained from 𝑞 by replacing its constants by their images through 𝜎.

The optimization of a conjunction of subqueries 𝑛 𝑖=1 𝑞 𝑖 is:

Ω( 𝑛 𝑖=1 𝑞 𝑖 , S) = ∅ if ∃𝑖 ∈ [1, 𝑛] Ω(𝑞 𝑖 , S) = ∅ 𝑛 𝑖=1 Ω(𝑞 𝑖 , S) otherwise (2)
The optimization of a disjunction of subqueries 𝑛 𝑖=1 𝑞 𝑖 is:

Ω( 𝑛 𝑖=1 𝑞 𝑖 , S) = ∅ if ∀𝑖 ∈ [1, 𝑛] Ω(𝑞 𝑖 , S) = ∅ 1≤𝑖 ≤𝑛, Ω (𝑞 𝑖 ,S)≠∅ Ω(𝑞 𝑖 , S) otherwise (3)
Above, the rewriting rule (1) follows from the soundness of identifying CQs with no answer using a database summary (Theorem 4.2), while the two other rewriting rules (2) and (3) follow from the semantics of the ∧ and ∨ operators, respectively.

The next theorem establishes two semantic relationships between a (∧, ∨)-CQ and its optimization, which correspond to items 1 and 2 in Problem 1. In particular, it states the correctness of summarybased optimization of a (∧, ∨)-CQ w.r.t. relational query evaluation. USCQ and 𝑞 O JUCQ for D using S corresponds to the following UCQ, USCQ and JUCQ, respectively. We also show in gray the subqueries that would have been additionally removed (with higher optimization cost) if Ω had used D instead of S.

Ω (𝑞 O UCQ , S) = (𝑅 (h) ∧ 𝑤𝑤 (h, 𝑥 ) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) (1) ∨(𝑅 (h) ∧ 𝑤𝑤 (h, 𝑥 ) ∧ 𝑃ℎ𝐷 (𝑥 ) ) (2) ∨(𝑅 (h) ∧ 𝑠𝑢𝑝 (h, 𝑥 ) ) (3) Ω (𝑞 O USCQ , S) = (𝑅 (h) ) ∧ (𝑤𝑤 (h, 𝑥 ) ∨ 𝑠𝑢𝑝 (h, 𝑥 ) ∨ 𝑤𝑤 (𝑥, h) ) ∧ (𝑠𝑢𝑝 (𝑦, 𝑥 ) ∨ 𝑃ℎ𝐷 (𝑥 ) ) Ω (𝑞 O JUCQ , S)=(𝑅 (h) )∧ (𝑤𝑤 (h, 𝑥 ) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥 ) ) ∨ (𝑤𝑤 (h, 𝑥 ) ∧ 𝑃ℎ𝐷 (𝑥 ) ) ∨ (𝑠𝑢𝑝 (h, 𝑥 ) )
For L 𝑅 ∈ {UCQ, USCQ, JUCQ}, it can be easily checked that: Finally, we provide our cost estimation function 𝑐 (Definition 4.7 below) to formally characterize the efficiency of summary-based optimization of a (∧, ∨)-CQ, which corresponds to item 3 in Problem 1. It provides summable optimization and evaluation costs by (𝑖) trivially setting the query evaluation cost to the cost of relational query evaluation [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Ramakrishnan | Database management systems[END_REF] (first item in Definition 4.7 below) and (𝑖𝑖) reducing the query optimisation cost to the sole cost of relational query evaluation that it induces (second item in Definition 4.7 below): Ω's simple in-memory data processing ((2) and (3) in Definition 4.4) is typically negligible w.r.t. Ω's on-disk data processing ((1) in Definition 4.4).

Ω(𝑞 O L 𝑅 , S) ⊆ 𝑞 O L 𝑅

Definition 4.7 (Cost estimation function 𝑐).

Let 𝑞 be a (∧, ∨)-CQ and D be a database. Given a cost estimation function cost-rel-eval for query evaluation on relational databases, the cost estimation function 𝑐 for summary-based optimization is such that:

• 𝑐 (𝑒𝑣𝑎𝑙 (𝑞, D)) = cost-rel-eval(𝑒𝑣𝑎𝑙 (𝑞, D))

• 𝑐 (Ω(𝑞, D)) = 𝑛 𝑖=1 cost-rel-eval(𝑒𝑣𝑎𝑙 (𝑐𝑞 𝑖 , D)), where 𝑐𝑞 1 , . . . , 𝑐𝑞 𝑛 are all the CQs in the (∧, ∨)-CQ 𝑞.

Database summarization

The concrete database summaries that we use with our Ω optimization function are defined by adapting the quotient operation from graph theory [START_REF]Handbook of Graph Theory[END_REF] to the incomplete relational databases we consider. The quotient operation has been widely used in the literature for graph database summarization [START_REF] Cebiric | Summarizing semantic graphs: a survey[END_REF][START_REF] Liu | Graph Summarization Methods and Applications: A Survey[END_REF]. It offers an elegant summarization technique by decoupling the summarization method, which fuses equivalent nodes, from the high-level specification of equivalent nodes, defined by an equivalence relation, e.g., bisimilarity [START_REF] Abriola | Bisimulations on Data Graphs[END_REF]. We recall that an equivalence relation is a reflexive, symmetric, and transitive binary relation. Assuming we have an equivalence relation between database terms (the one we use will be discussed shortly), we define a quotient database as follows.

Definition 4.8 (Quotient database). Let D be a database, ≡ be some equivalence relation between terms, and let 𝑐 1 ≡ , . . . , 𝑐 𝑘 ≡ denote, by abuse of notation, both the equivalence classes of all terms in D w.r.t. ≡ and the terms used to represent these equivalence classes.

The quotient database of D w.r.t. ≡ is the database D ≡ such that:

• 𝑅(𝑐 𝛼 1 ≡ , • • • , 𝑐 𝛼 𝑛 ≡ ) ∈ D ≡ iff there exists 𝑅(𝑡𝑒𝑟𝑚 1 , • • • , 𝑡𝑒𝑟𝑚 𝑛 ) ∈ D with 𝑡𝑒𝑟𝑚 𝑖 ∈ 𝑐 𝛼 𝑖 ≡ and 1 ≤ 𝛼 𝑖 ≤ 𝑘, for 1 ≤ 𝑖 ≤ 𝑛, • the term 𝑐 𝑗 ≡ in D ≡ , for 1 ≤ 𝑗 ≤ 𝑘,
is a variable if all the equivalent terms in D it represents according to ≡ are variables, otherwise it is a constant.

The next proposition establishes that quotient databases can be used by the optimization function Ω to identify CQs with no answer on databases. It follows from the fact that in the above definition, ≡ defines an implicit function that maps the terms in D to the terms in D ≡ , which turns out to be the homomorphism 𝜎 in Definition 4.1: the first and second items in the above definition enforce respectively the conditions (𝑖) and (𝑖𝑖) in Definition 4.1. Proposition 4.9. Quotient databases are database summaries.

We introduce the equivalence relation ≡ Ω used to build our summaries, i.e., how database terms are fused into summary terms. Since ontology languages [START_REF]The Description Logic Handbook[END_REF][START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF][START_REF] Calì | Datalog+/-: A Family of Logical Knowledge Representation and Query Languages for New Applications[END_REF][START_REF] Chein | Graph-based Knowledge Representation -Computational Foundations of Conceptual Graphs[END_REF] are centered on concepts modeled by unary predicates, which are then interrelated using relationships modeled by 𝑛-ary predicates (with 𝑛 ≥ 2), we adopt a summarization centered on the instances of concepts stored in a KB's database: all the terms that are instances of the same concept in the KB's database are represented by a single term in the summary ((𝑖) in Definition 4.10 below), and all the concepts with common instances in the KB's database have the same single term that represents all their instances in the summary ((𝑖𝑖) in Definition 4.10 below). As we shall see in our experiments, database summaries built with ≡ Ω achieve a good tradeoff between size reduction (≥90%) and completeness of identifying CQs with no answer (92% on average).

Definition

EXPERIMENTAL EVALUATION

We implemented our optimization framework in the OptiRef JAVA tool [START_REF] Husseini | OptiRef: Query Optimization for Knowledge Bases[END_REF] in order to evaluate the OMQA time performance it brings.

Setup. For our KBs, we used the well-established extended LUBM benchmark a.k.a. LUBM ∃ [START_REF] Lutz | The Combined Approach to OBDA: Taming Role Hierarchies Using Filters[END_REF]. It is an adaptation of the Leight University benchmark a.k.a. LUBM [START_REF] Guo | LUBM: A benchmark for OWL knowledge base systems[END_REF] to the DL-Lite R description logic [START_REF] Calvanese | Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family[END_REF]. We chose this benchmark for two reasons. First, DL-Lite R is the most expressive KB language for which the reformulation of CQs into UCQ, USCQ and JUCQ reformulations has been studied. Second, LUBM ∃ is widely-considered in the OMQA literature and provides opportunities to adapt many available queries to our needs. For the ontology O of all our KBs, we used the default benchmark ontology LUBM ∃ 20 . It is made of 449 rules over 163 predicates: 128 unary predicates, a.k.a. concepts, and 35 binary predicates, a.k.a. roles. We used the EUGen (v0.1b) data generator provided with LUBM ∃ to generate the databases of our KBs.

OptiRef relies on the open-source PostgreSQL RDBMS (v14.2) to store the generated databases and their summaries, which is commonly used in the OMQA literature. We adopted the data layout of [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF] for the databases and summaries, which was found to be the most efficient for evaluating query reformulations on DL-Lite R KB's database. Concepts instances are stored in unary relations, and role instances are stored in binary relations. Also, all the values are dictionary-encoded into integers; the dictionary is stored as a binary relation. Finally, for a database summary, the database-to-summary homomorphism 𝜎, which maps the database terms to the summary terms, is stored as a binary relation. For all the above-mentioned database, summary, dictionary and homomorphism relations, each unary relation has an index on its unique attribute and each binary relation has the two two-attributes indexes.

OptiRef relies on the Rapid (v0.93) [START_REF] Chortaras | Optimized Query Rewriting for OWL2QL[END_REF], Compact (v1.0b6) [START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF] and GDL (v1.0) [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF] FO-rewriting tools that respectively compute UCQ, USCQ and JUCQ reformulations of CQs w.r.t. DL-Lite R ontologies. They load and keep in memory the ontology w.r.t. which CQs are reformulated. We chose Compact and GDL because they are the only tools to respectively compute USCQ and JUCQ query reformulations, to the best of our knowledge. By contrast, there are other tools besides Rapid to compute UCQ query reformulations, e.g., Clipper [START_REF] Eiter | Query Rewriting for Horn-SHIQ Plus Rules[END_REF], Graal [START_REF] Baget | Graal: A Toolkit for Query Answering with Existential Rules[END_REF], Iqaros [START_REF] Venetis | Incremental Query Rewriting for OWL 2 QL[END_REF], Nyaya [START_REF] De | NYAYA: A System Supporting the Uniform Management of Large Sets of Semantic Data[END_REF], Presto [START_REF] Rosati | Improving Query Answering over DL-Lite Ontologies[END_REF], Requiem [START_REF] Pérez-Urbina | Efficient Query Answering for OWL 2[END_REF], etc. These tools differ w.r.t. query reformulation time and query reformulation minimality. We chose Rapid since it is fast, although we do not consider query reformulation cost (hence time) in our optimization problem (Problem 1), to compute minimal UCQ reformulations, i.e., within which no CQ is redundant with another.

We ran our experiments on a Ubuntu 20.04 Linux server with Intel Xeon 4215R 3.20GHz CPU, 128GB of RAM, and 7TB of HDD. Database summarization. We generated five LUBM databases: LUBM1M, LUBM10M, LUBM50M, LUBM100M, LUBM150M. The name of a database indicates the number of stored facts in millions. Also, databases are created such that LUBM1M ⊆ LUBM10M ⊆ LUBM50M ⊆ LUBM100M ⊆ LUBM150M, where ⊆ means set inclusion, so that query answering becomes harder as data grows.

OptiRef relies on a union-find data structure for disjoint sets [START_REF] Thomas | Introduction to Algorithms[END_REF] for database summarization, since equivalence classes of database terms w.r.t. ≡ Ω are disjoint sets of equivalent terms w.r.t. ≡ Ω . This data structure supports two main operations, union and find, in optimal constant amortized time complexity [START_REF] Endre | Amortized Computational Complexity[END_REF][START_REF] Endre | Worst-case Analysis of Set Union Algorithms[END_REF], i.e., time complexity is almost constant over a sequence of union or find operations. Union is used to state which values must be in a same set, and results in merging the sets these values belong to. Find returns the representative value of the set a given value belongs to.

OptiRef first computes the homomorphism 𝜎 from the database D to the summary S (Definition 4.1) w.r.t. the ≡ Ω equivalence relation (Definition 4.10). Given a union-find data structure for disjoint sets of integers, we use union to state that the (integer-encoded) terms stored in each unary relation in D are in a same set, as these terms are equivalent w.r.t. ≡ Ω (condition (𝑖) in Definition 4.10). By definition of union, this ensures that if unary relations share some terms, in which case all the terms of these relations are equivalent w.r.t. ≡ Ω (condition (𝑖𝑖) in Definition 4.10), then these terms end up in the same set. Finally, since find returns a representative term for the set of equivalent terms a given term belongs to, it models the homomorphism 𝜎 from the database D to its summary S w.r.t. ≡ Ω . The computation of 𝜎 is therefore linear in the size of the data: it needs a worst-case number of calls to union in the size of D, each of which is performed in constant amortized time. Then, OptiRef computes the summary S of the database D w.r.t. ≡ Ω as per Definition 4.8: every fact in D leads to a fact in S obtained by replacing each term by its image through 𝜎, i.e., find. The computation of S is therefore linear in the size of the data: it needs a worst-case number of calls to find in the size of D (one or two calls per fact), each of which is performed in constant amortized time.

Table 2 shows for each database D we generated: its size |D | and the size |S| of its summary S, i.e., numbers of facts, the Dto-S size reduction (1 -|S|/|D|), and the summarization time with PostgreSQL (computation and storage of 𝜎 and then of S). We observe that ≡ Ω achieves significant size reduction (≥ 90%) and that summarization time scales linearly in the size of the data. However, we remark that it would be prohibitive to redo summarization upon database updates. OptiRef thus relies on incremental summary maintenance [START_REF] Husseini | OptiRef: Query Optimization for Knowledge Bases[END_REF]. By definition of a summary built with ≡ Ω , in the worst case, an insertion fuses two equivalence classes and a deletion splits an equivalence class into two ones. Maintenance rewrites the affected summary facts, i.e., in which some term moves from an equivalence class to another, based on the updated homomorphism 𝜎 modeled with a union-find data structure that also supports the delete operation in optimal constant amortized time complexity [START_REF] Alstrup | Union-Find with Constant Time Deletions[END_REF].

OMQA performance. We used ten CQs adapted from [START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Lutz | The Combined Approach to OBDA: Taming Role Hierarchies Using Filters[END_REF] to obtain a variety of numbers of maximally-contained CQs w.r.t. O that query reformulations model (recall Section 2) and of answers.

The main characteristics of these CQs are shown in Table 3 (top).

For each database, OptiRef processed every query with 3 strategies per L 𝑅 query reformulation languages used by FO-rewriting tools: L 𝑅 = UCQ for Rapid, L 𝑅 = USCQ for Compact and L 𝑅 = JUCQ for GDL. The first strategy, denoted by L 𝑅 /REF, consists in computing the L 𝑅 query reformulation with the FO-rewriting tool and then evaluating it with PostgreSQL; this is how OMQA is performed via FO-rewriting, hence the state-of-the-art baseline. The second strategy, denoted by L 𝑅 /DB, departs from L 𝑅 /REF by optimizing the query reformulation for the database D before evaluating it. For this strategy, our Ω function optimizes the query reformulation using the database D. The third strategy, denoted by L 𝑅 /S, is similar to L 𝑅 /DB except that our Ω function optimizes the query reformulation for D using the summary S of D.

Table 3 (bottom) shows the optimization ratio per query obtained with L 𝑅 /S on LUBM100M, i.e., the percentage of CQs with no answers on LUBM100M that are identified and removed by Ω using LUBM100M's summary; the ratio is 0% with L 𝑅 /REF and 100% with L 𝑅 /DB. We observe that optimization ratios are high in general, 92% on average with 52.53% the lowest value (𝑄𝐴6), thus our summaries are effective to identify CQs with no answers. Similar results are obtained on LUBM1M, LUBM10M, LUBM50M and LUBM150M.

We analyze below the times we measured when our queries are processed with the above-mentioned strategies. The measured time is: optimization time + evaluation time. Each reported time is an average over 5 "hot" query runs, i.e., the first "cold" query run is discarded. For space consideration, we focus on the times measured for LUBM10M and the ten times larger LUBM100M, which are shown in Figure 2. Measured times for all our databases are in Appendix D; they gradually increase as data size grows from 1M to 150M facts.

L 𝑅 /S versus the state-of-the-art baseline L 𝑅 /REF. We observe that when query reformulations are optimized by Ω using S: • Performance almost always improves for UCQs (UCQ/S for all the databases except for 𝑄𝐴6), often significantly and up to 3 orders of magnitude (e.g., UCQ/S for 𝑄𝐴1 on LUBM10M and LUBM100M).

• Performance frequently improves for JUCQs (in half of the cases overall), up to one order of magnitude (e.g., JUCQ/S for 𝑄𝐴8 on LUBM100M), otherwise performance is marginally affected. We remark that when the performance visibly degrades (e.g., 𝑄𝐴9 on LUBM100M) it is just in the order of a few tens of ms.

• Performance is marginally affected for USCQs.

These observations are explained with the two following facts, and the optimization ratios obtained with our summaries (Table 3).

(1) Optimizing reformulations with Ω removes CQs with no answer from the top union in UCQs and from the unions on which the top join is performed in JUCQs; in USCQs, single-atom CQs are removed from unions on top of which joins are performed, on top of which the top union is performed.

(2) Removing CQs with no answer from a union improves its evaluation time (as it may take time for an RDBMS to find out that a CQ has no answer), while it does not change the size of its output hence the number of tuples to process after this union.

Therefore: • Optimizing a UCQ reformulation with Ω speeds up its entire evaluation since Ω optimizes its top union. Also, because our summaries allow high optimization ratios for UCQ/S, performance is significantly improved in general. We remark that performance degrades for 𝑄𝐴6 because the optimization time does not amortize with a low optimization ratio (52.53% on LUBM100M).

• Optimizing a JUCQ reformulation with Ω speeds up the evaluation of its sub-UCQs but does not affect the evaluation time of the top join (as the same tuples must be joined). JUCQ reformulations are thus more difficult to optimize than UCQ ones. This is why performance is "only" frequently improved (in half of the cases) and marginally affected otherwise, even with high optimization ratios for JUCQ/S (> 78% on LUBM100M).

• Optimizing a USCQ reformulation with Ω only removes atomic CQs from its inner unions while it does not take time for an RDBMS to figure out that these atomic CQs are empty. The optimization thus marginally affects the evaluation time of these inner unions, and the evaluation time of the subsequent joins and top union is not affected. USCQ reformulations are thus more difficult to optimize than UCQ and JUCQ ones. This is why performance is marginally affected in general, even with maximal optimization ratios for USCQ/S (100% on LUBM100M). L 𝑅 /DB versus L 𝑅 /REF and L 𝑅 /S. We observe that when Ω optimizes query reformulations using D instead of S, performance may improve or degrade:

• Performance is overall marginally to significantly better with UCQ/DB than with the baseline UCQ/REF, although the performance with UCQ/DB is generally worse than with UCQ/S. • Performance with JUCQ/DB is always worse than with the baseline JUCQ/REF and almost always worse than with JUCQ/S. • Performance with USCQ/DB is always worse than with the baseline USCQ/REF and with USCQ/S. These observations are explained by the extra-time spent by L 𝑅 /DB w.r.t. L 𝑅 /S in completely optimizing a query reformulation using the database (recall that optimization ratios are of 100% for L 𝑅 /DB): optimization time with L 𝑅 /DB is in general significantly higher than with L 𝑅 /S, because a database is much larger than its summary, while at the same time L 𝑅 /DB provides a moderate gain in optimization ratios because they are already very high with L 𝑅 /S in general. This is why L 𝑅 /DB performs worse than L 𝑅 /S overall, and worse than L 𝑅 /REF when optimization time is higher than the time saved when the optimized reformulation is evaluated. Experiment conclusion. Our summaries can be fast to compute (linear in data size), small (<10% of data size), and effective to identify CQs with no answer on a database (92% on average). Also, when they are used with our Ω optimization function, OMQA time performance can be significantly improved for UCQ reformulations in general and frequently for JUCQ reformulations, while performance is marginally affected for USCQ ones.

RELATED WORK AND CONCLUSION

We devised a novel optimization framework for OMQA via FOrewriting. It is complementary to, and capitalizes on, the optimizations that have been proposed so far in the literature, e.g., [START_REF] Bursztyn | Optimizing Reformulation-based Query Answering in RDF[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Chortaras | Optimized Query Rewriting for OWL2QL[END_REF][START_REF] Gottlob | Rewriting Ontological Queries into Small Nonrecursive Datalog Programs[END_REF][START_REF] König | Sound, complete and minimal UCQ-rewriting for existential rules[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF], which are both ontology-dependent and dataindependent. Its novelty is to add a complementary data-dependent optimization step to query reformulations produced by state-ofthe-art FO-rewriting tools, e.g., [START_REF] Baget | Graal: A Toolkit for Query Answering with Existential Rules[END_REF][START_REF] Bursztyn | Optimizing Reformulation-based Query Answering in RDF[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF][START_REF] Chortaras | Optimized Query Rewriting for OWL2QL[END_REF][START_REF] Pérez-Urbina | Efficient Query Answering for OWL 2[END_REF][START_REF] Rosati | Improving Query Answering over DL-Lite Ontologies[END_REF][START_REF] Thomazo | Compact Rewritings for Existential Rules[END_REF][START_REF] Venetis | Incremental Query Rewriting for OWL 2 QL[END_REF][START_REF] De | NYAYA: A System Supporting the Uniform Management of Large Sets of Semantic Data[END_REF]. This framework is general enough to apply to a variety of FO-rewriting settings, in particular those in Table 1, and it guarantees the correctness of OMQA on the queried KBs. For the FO-rewriting settings in which it was evaluated, it significantly improves OMQA time performance for the widely-adopted UCQ query reformulations, e.g., [9, 16, 20, 30-33, 39, 44, 45, 47, 52], and for the JUCQ ones of [START_REF] Bursztyn | Optimizing Reformulation-based Query Answering in RDF[END_REF][START_REF] Bursztyn | Teaching an RDBMS about ontological constraints[END_REF]. The originality of our framework is to build on the Ω optimization function that rewrites a query reformulation into a contained one, by pruning away subqueries that are useless to its evaluation on a given database. Notably, useless subqueries are identified rapidly by using database summaries, which we devised for this purpose by adapting the quotient operation [START_REF]Handbook of Graph Theory[END_REF] to databases. Database summaries, in particular those based on the quotient operation, have been mainly investigated for graph databases, e.g., [START_REF] Cebiric | Summarizing semantic graphs: a survey[END_REF][START_REF] Liu | Graph Summarization Methods and Applications: A Survey[END_REF], and description logic databases [START_REF] Dolby | Scalable Semantic Retrieval through Summarization and Refinement[END_REF][START_REF] Dolby | Scalable Highly Expressive Reasoner[END_REF][START_REF] Vaigh | A Well-founded Graphbased Summarization Framework for Description Logics[END_REF][START_REF] Fokoue | The Summary Abox: Cutting Ontologies Down to Size[END_REF], for the purpose of data exploration and of data management optimization. To the best of our knowledge, summaries have not been used for the optimization of OMQA via FO-rewriting. We adapted the quotient operation to relational databases and we defined the new equivalence relation ≡ Ω for the special task of sound and fast identification of CQs with no answer on a database. ≡ Ω departs from prior equivalence relations by being based on the instances of concepts that KB's databases describe with n-ary relationships between them, and not on bisimulation [START_REF] Henzinger | Computing Simulations on Finite and Infinite Graphs[END_REF], e.g., [START_REF] Fan | Query preserving graph compression[END_REF][START_REF] Milo | Index Structures for Path Expressions[END_REF], or cooccurrence of relationships [START_REF] Goasdoué | Incremental structural summarization of RDF graphs[END_REF][START_REF] Goasdoué | RDF graph summarization for first-sight structure discovery[END_REF]. A perspective is to study other database summaries for our framework, to improve further OMQA time performance, either via the quotient operation and other equivalence relations than ≡ Ω , or with other procedures than the quotient operation.

C PROOFS

Proof of Theorem 4.2. We prove the theorem by showing that its contrapositive holds, i.e., if 𝑞 has some answer on D, then 𝑞 𝜎 has some answer on S. If 𝑞 has an answer on D, then there exists a homomorphism ℎ from 𝑞 to D such that ℎ(𝑞) ⊆ D where every free variable is mapped to a constant, every existential variable is mapped to a constant or variable, and every constant is mapped to itself. Moreover, the composition 𝜎 • ℎ is a homomorphism from 𝑞 to S such that 𝜎 • ℎ(𝑞) ⊆ S where, by definition of a database summary, every free variable is mapped to a constant, every existential variable is mapped to a constant or variable, and every constant is mapped to its image through 𝜎. Let us now build a homomorphism 𝑔 from 𝑞 𝜎 to S such that 𝑔(𝑞 𝜎 ) = 𝜎 • ℎ(𝑞) ⊆ S: it suffices that 𝑔 maps every variable exactly as 𝜎 • ℎ does, while it maps every constant to itself (constants have already been replaced by their image through 𝜎 in 𝑞 𝜎 ). Since defined this way 𝑔 maps free variables to constants, 𝑞 𝜎 has an answer on S. □ Proof of Theorem 4.5. Let us first prove Ω(𝑞, S) ⊆ 𝑞. We prove this by induction on the depth 𝑑 of 𝑞 defined as the maximal nesting of the ∧ and ∨ operators on top of CQs, with the induction hypothesis that Ω performs rewritings (rules (1), ( 2) and (3) in Definition 4.4) that are contained in the rewritten query. Base case, 𝑑 = 0: rule (1) rewrites 𝑞 either by (second case) itself or by (first case) ∅, and clearly, 𝑞 is contained in itself and ∅ is contained in 𝑞. Induction step, 𝑑 > 0: rule (2) rewrites a conjunction either by (second case) a contained one (induction) or by (first case) ∅ that is by definition contained in the rewritten conjunction; rule (3) rewrites a disjunction either by (second case) a contained one (induction), or by ∅ (first case) that is by definition contained in the rewritten disjunction.

Let us now prove that 𝑒𝑣𝑎𝑙 (𝑞, D) = 𝑒𝑣𝑎𝑙 (Ω(𝑞, S), D). Again, we prove this by induction on the depth 𝑑 of 𝑞 defined as the maximal nesting of ∧ and ∨ operators on top of CQs, with the induction hypothesis that Ω performs rewritings (rules (1), ( 2

D EXPERIMENTAL RESULTS

Query answering times (ms, logscale) with PostgeSQL on all our LUBM databases.

Figure 1 :

 1 Figure 1: Standard (solid and dashed, back edges) and optimized (black and blue, solid edges) OMQA via FO-rewriting

Definition 4 . 1 (

 41 Summary of a database).A database S is a summary of a database D iff (𝑖) there exists a homomorphism 𝜎 from D to S, i.e., D 𝜎 = S where D 𝜎 is the database obtained from D by replacing the terms in D by their images in S through 𝜎, such that (𝑖𝑖) 𝜎 maps constants in D to constants in S, while it maps variables in D to constants or variables in S.

Example 4 . 3 (

 43 Cont.). Consider the summary S of D with homomorphism 𝜎 such that 𝜎 (c) = 𝜎 (w) = p, 𝜎 (f) = 𝜎 (h) = 𝜎 (𝑢) = r: S = {𝑅(r), 𝑠𝑢𝑝 (r, p), 𝑃ℎ𝐷 (p), 𝑤𝑤 (r, r), 𝑤𝑤 (r, p)}. Consider the CQs (1) and (5) in 𝑞 O UCQ , which we name 𝑞 1 and 𝑞 5 respectively. According to Theorem 4.2: 𝑞 1 𝜎 (𝑥) = 𝑅(r) ∧𝑤𝑤 (r, 𝑥) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥) has an answer on the summary S (𝑒𝑣𝑎𝑙 (𝑞 1 𝜎 , S) = {p}) then 𝑞 1 may or may not have an answer on D (here, 𝑞 1 has no answer on D), while 𝑞 5 𝜎 (𝑥) = 𝑅(r) ∧ 𝑤𝑤 (𝑥, r) ∧ 𝑃ℎ𝐷 (𝑥) has no answer on S then for sure 𝑞 5 has no answer on D. ⋄ (∧, ∨)-CQ optimization for a database. Our Ω function builds on Theorem 4.2 to optimize a (∧, ∨)-CQ for a database D. It rewrites a query while (𝑖) identifying its CQs with no answer on D using a summary S of it ((1) in Definition 4.4 below) and (𝑖𝑖) performing a bottom-up removal of the largest subqueries with no answer on D that these CQs are the causes of ((2) and (3) in Definition 4.4 below).

Definition 4 . 4 (

 44 Optimization function Ω).

Theorem 4 . 5 .

 45 Let D be a database, S a summary of D, and 𝑞 a (∧, ∨)-CQ. Then Ω(𝑞, S) ⊆ 𝑞 and 𝑒𝑣𝑎𝑙 (𝑞, D) = 𝑒𝑣𝑎𝑙 (Ω(𝑞, S), D).

Example 4 . 6 (

 46 Cont.). The summary-based optimization of 𝑞 O UCQ , 𝑞 O

  since Ω makes unions more specific by removing disjuncts, and 𝑒𝑣𝑎𝑙 (Ω(𝑞 O L 𝑅 , S), D) = 𝑒𝑣𝑎𝑙 (𝑞 O L 𝑅 , D) since both 𝑞 O L 𝑅 and Ω(𝑞 O L 𝑅 , S) model the CQ (3) that produces the sole answer w. ⋄

Figure 2 :

 2 Figure 2: Query answering times (ms, logscale) with PostgreSQL on LUBM10M (left) and LUBM100M (right)

  ) and (3) in Definition 4.4) that are equivalent w.r.t. the database D. Base case, 𝑑 = 0: rule (1) rewrites 𝑞 either by (second case) itself or by (first case) ∅ if 𝑞 has no answer on S, hence on D according to Theorem 4.2, i.e., 𝑞 is equivalent to ∅ on D. Induction step, 𝑑 > 0: rule (2) rewrites a conjunction either by (second case) an equivalent one (induction) or by (first case) ∅ if a 𝑞 𝑖 subquery has no answer on D (induction), hence the conjunction is equivalent to ∅ on D; rule (3) rewrites a disjunction either by (second case) an equivalent one (induction), or by ∅ (first case) if all its subqueries have no answer on D, hence the disjunction is equivalent to ∅ on D. □

Table 1 :

 1 Main related works on conjunctive query answering via FO-rewriting

		Query reformulation language
	KB language	UCQ	USCQ JUCQ datalog 𝑛𝑟
	datalog±/existential rules	[31, 32, 39]	[51]	[33, 44]
	description logics/OWL	[16, 20, 45, 52]	[11]	[47]
	RDF/S	[9, 30]	[10]

  𝑥) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥). Its answer set on K is 𝑎𝑛𝑠 (𝑞, K) = {w}: w is obtained from 𝑅(h) ∈ D, 𝑠𝑢𝑝 (f, w) ∈ D or 𝑠𝑢𝑝 (h, w) ∈ D, and the fact 𝑤𝑤 (h, w) entailed from 𝑠𝑢𝑝 (h, w) ∈ D and 𝑟 2 . ⋄ 𝑄 , L 𝐾 ) of query and KB languages. Such a setting is FO-rewritable if for any L 𝑄 query 𝑞 and any L 𝐾 ontology O, there exists an FO query 𝑞 O , called a reformulation of 𝑞 w.r.t. O, such that for any KB K = (O, D): 𝑎𝑛𝑠 (𝑞, K) = 𝑒𝑣𝑎𝑙 (𝑞 O , D), where 𝑒𝑣𝑎𝑙 (𝑞 O , D) is the result of the relational evaluation of 𝑞 O on D from which tuples with variables are pruned away. Furthermore, each FO-rewriting algorithm computes query reformulations in a fixed FO query dialect. Recall for instance Table

	Ontology-mediated query answering. We consider FO queries
	of the form 𝑞( x) = 𝜙, where 𝜙 is an FO formula, the set of free
	(non-quantified) variables of which is exactly the tuple x of answer
	variables. The arity of a query 𝑞( x) is the cardinality of x; 𝑞( x) is
	said Boolean if x = ∅. A (certain) answer to a query 𝑞( x) of arity 𝑛
	on a KB K is a tuple t of 𝑛 constants from K such that K |= 𝑞( t),
	where |= is the FO entailment relation and 𝑞( t) is the Boolean query
	obtained by instantiating x with t in 𝑞; when 𝑞 is Boolean, t is the
	empty tuple ⟨⟩. From now, we denote by 𝑎𝑛𝑠 (𝑞, K) the answer set of
	𝑞 on K and we remark that if 𝑞 is Boolean then the answer is true
	when 𝑎𝑛𝑠 (𝑞, K) = {⟨⟩} and the answer is false when 𝑎𝑛𝑠 (𝑞, K) = ∅.
	Example 2.2 (Cont.). Let us consider the CQ asking for the super-
	visees who work with h that must be a researcher: 𝑞(𝑥) = ∃𝑦 𝑅(h) ∧
	𝑤𝑤 (h, Ontology-mediated query answering technique. We focus on
	optimizing OMQA via FO-rewriting [16].
	FO-rewriting reduces query answering on KBs to query evalu-
	ation on relational databases in FO-rewritable OMQA settings. An
	OMQA setting is a pair (L
	𝑢, c), 𝑃ℎ𝐷 (c)}.
	The ontology O states that working with (𝑤𝑤) someone is a sym-
	metric relation (𝑟 1 ), supervising someone (𝑠𝑢𝑝) is a particular case
	of working with someone (𝑟 2 ), and PhD students (𝑃ℎ𝐷) are nec-
	essarily supervised (𝑟 3 ). The database D states that f and h are
	researchers (𝑅) who supervise the PhD student w, f works with h,
	and a researcher 𝑢 works with the PhD student c.	⋄

  t. O, i.e., the union of all the most general CQ specializations of 𝑞 w.r.t. O. We recall that (𝑖) a query 𝑞 ′ is contained in a query 𝑞, denoted by 𝑞 ′ ⊆ 𝑞, if and only if for each database D, 𝑒𝑣𝑎𝑙 (𝑞 ′ , D) ⊆ 𝑒𝑣𝑎𝑙 (𝑞, D) and (𝑖𝑖) a query 𝑞 ′ is contained in a query 𝑞 w.r.t. an ontology O, denoted by 𝑞 ′ ⊆ O 𝑞, if and only if for each KB K = (O, D), 𝑎𝑛𝑠 (𝑞 ′ , K) ⊆ 𝑎𝑛𝑠 (𝑞, K). A query 𝑞 ′ is maximally-contained in a query 𝑞 w.r.t. an ontology O if and only if (𝑖) 𝑞 ′ ⊆ O 𝑞 and (𝑖𝑖) for any other query 𝑞 ′′ ⊆ O 𝑞, if 𝑞 ′ ⊆ 𝑞 ′′ then 𝑞 ′′ ⊆ 𝑞 ′ (i.e., 𝑞 ′ and 𝑞 ′′ are equivalent). . We omit existential quantifiers in queries, as nonanswer variables are existentially quantified in the query languages we consider (recall Appendix A). For instance, the CQ of Example 2.2 is now written 𝑞(𝑥) = 𝑅(h) ∧ 𝑤𝑤 (h, 𝑥) ∧ 𝑠𝑢𝑝 (𝑦, 𝑥). Example 2.3 (Cont.). Consider the following equivalent UCQ 𝑞 O UCQ , USCQ 𝑞 O USCQ and JUCQ 𝑞 O JUCQ reformulations of 𝑞 w.r.t. O, which are respectively computed by the Rapid

	Notation

  for a given cost estimation function 𝑐 (•) that models the cost to compute •. Removing subCQs from a query reformulation seen as (∧, ∨)-combinations of CQs obviously removes all the maximally-contained queries these subCQs are part of, and crucially for us, removing such subCQs with no answer on a particular database removes maximally-contained queries that are irrelevant to this database. E.g., in Example 2.3, removing the subCQ 𝑠𝑢𝑝 (𝑥, h) with no answer on D from 𝑞 O USCQ also removes from 𝑞 O USCQ the two irrelevant maximally-contained CQs 𝑅(h) ∧ 𝑠𝑢𝑝 (𝑥, h) ∧ 𝑠𝑢𝑝 (𝑥, 𝑦)

	4 OPTIMIZATION FRAMEWORK
	4.1 The Ω optimization function

Rationale behind the Ω optimization function. When a query reformulation is seen as a (∧, ∨)-combination of CQs, these subCQs are parts of the maximally-contained CQs that the query reformulation models. Recall for instance Example 2.3 where the maximallycontained CQ (3) in the UCQ reformulation corresponds to the logical combinations of the subCQs shown in blue in the JUCQ and USCQ reformulations.

  4.10 (≡ Ω equivalence relation). ≡ Ω is the equivalence relation such that two terms 𝑡 1 and 𝑡 2 are equivalent within a database D, denoted 𝑡 1 ≡ Ω 𝑡 2 , iff (𝑖) both 𝑡 1 and 𝑡 2 are instances of the same unary predicate, i.e., concept, or (𝑖𝑖) there exists a term 𝑡 3 in D such that 𝑡 1 ≡ Ω 𝑡 3 and 𝑡 2 ≡ Ω 𝑡 3 . Example 4.11 (Cont.). The summary S in Example 4.3 is actually the quotient database of D w.r.t. ≡ Ω : it defines two equivalence classes, one for the researchers in D, i.e., {f, h, 𝑢}, and one for the PhD students in D, i.e., {w, c}; these two classes are represented in S by the constants r and p, respectively. ⋄

Table 2 :

 2 Characteristics of the databases and summaries, database size reduction and summarization time for PostgreSQL

	Database D	|D |	|S| size red. (%) sum. time (s)
	LUBM1M	1,187k	93k	92.12	15
	LUBM10M	10,794k	843k	92.18	86
	LUBM50M	53,328k	4,160k	92.20	308
	LUBM100M 106,596k	8,316k	92.19	699
	LUBM150M 159,899k 12,474k	92.19	1,100

Table 3 :

 3 Characteristics of the queries, K = (O, D) with O = LUBM ∃ 20 and D = LUBM100M

	Query answering

  An existential rule ∀x (𝑞1 ( x) → 𝑞 2 ( x)) corresponds to an FO formula ∀x (∃ ȳ ∧ 𝑚 𝑖=1 𝑎 𝑖 → ∃z ∧ 𝑛 𝑗=1 𝑏 𝑗 ) and: ∀x (∃ ȳ ∧ 𝑚 𝑖=1 𝑎 𝑖 → ∃z ∧ 𝑛 𝑗=1 𝑏 𝑗 ) ⇔ ∀x (¬(∃ ȳ ∧ 𝑚 𝑖=1 𝑎 𝑖 ) ∨ ∃z ∧ 𝑛 𝑗=1 𝑏 𝑗 ) ⇔ ∀x (∀ȳ¬(∧ 𝑚 𝑖=1 𝑎 𝑖 ) ∨ ∃z ∧ 𝑛 𝑗=1 𝑏 𝑗 ) ⇔ ∀x∀ȳ (∧ 𝑚 𝑖=1 𝑎 𝑖 → ∃z ∧ 𝑛 𝑗=1 𝑏 𝑗 )

	A MAIN FO QUERY LANGUAGES USED FOR
	FO-REWRITING
	Language First-Order Logic syntax Relational algebra syntax
	CQ	𝑞( x) = ∃ ȳ 𝑛 𝑖=1 𝑎𝑡𝑜𝑚 𝑖		𝑞( x) = Π x ( 𝑛 𝑖=1 𝑎𝑡𝑜𝑚 𝑖 )
	UCQ	𝑞( x) = 𝑛 𝑖=1 𝐶𝑄 𝑖			𝑞( x) = 𝑛 𝑖=1 𝐶𝑄 𝑖
	JUCQ	𝑞( x) = 𝑛 𝑖=1 𝑈 𝐶𝑄 𝑖		𝑞( x) = Π x ( 𝑛 𝑖=1 𝑈 𝐶𝑄 𝑖 )
	SCQ	𝑞( x) = ∃ ȳ 𝑛 𝑖=1	𝑚𝑖 𝑗=1 𝑎𝑡𝑜𝑚	𝑗 𝑖	𝑞( x) = Π x ( 𝑛 𝑖=1	𝑚𝑖 𝑗=1 𝑎𝑡𝑜𝑚	𝑗 𝑖 )
	USCQ	𝑞( x) = 𝑛 𝑖=1 𝑆𝐶𝑄 𝑖			𝑞( x) = 𝑛 𝑖=1 𝑆𝐶𝑄 𝑖
	B EXISTENTIAL VARIABLES IN RULES

ACKNOWLEDGMENTS

This work was supported by the ANR CQFD project (ANR-18-CE23-0003) and the Gedeon project (LTC & ARED Région Bretagne).


Ismaela Cavallin

Bessem Chouaia
email: bessem.chouaia@unive.it.

A minimal growth medium for Pseudomonas azotoformans associated with insect gut

Pseudomonas spp. can be found associated with several insect hosts. Some of these strains play a crucial role in helping their hosts overcome biotic challenges such as plant defence effectors. Defined media and optimally minimal media are instrumental in studying the physiology and metabolic pathways of microorganisms. In the case of the insect-associated Pseudomonas azotoformans isolated from Galeruca laticollis' gut, we tested six previously designed defined/minimal media. To determine the optimal medium, we compared the bacterium's growth performances on the different defined/minimal media to its growth performance on a rich medium using the Dynamic Time Warping Algorithm. The growth results at both 25°C and 30°C indicated the SMM as the optimal medium, with bacterial growth performances being the closest to a rich medium. Therefore, this medium would be highly suitable to study the catabolic pathways for the degradation of some xenobiotics in P. azotoformans.

.

Introduction

Bacteria of the genus Pseudomonas can be found in many habitats, including host-associated ones [START_REF] Peix | Historical evolution and current status of the taxonomy of genus Pseudomonas[END_REF]. Several Pseudomonas strains have been found in plants [START_REF] Anderson | Insights into plant-beneficial traits of probiotic Pseudomonas chlororaphis isolates[END_REF][START_REF] Xin | Pseudomonas syringae: What it takes to be a pathogen[END_REF][4] and animals [START_REF] Shukla | Gut microbiota degrades toxic isothiocyanates in a flea beetle pest[END_REF][START_REF] Zhukova | Diversity and Transmission of Gut Bacteria in Atta and Acromyrmex Leaf-Cutting Ants during Development[END_REF][START_REF] Montagna | Metamicrobiomics in herbivore beetles of the genus Cryptocephalus (Chrysomelidae): toward the understanding of ecological determinants in insect symbiosis[END_REF] with a variety of phenotypes ranging from pathogenicity [START_REF] Xin | Pseudomonas syringae: What it takes to be a pathogen[END_REF][START_REF] Dolan | Contextual flexibility in Pseudomonas aeruginosa central carbon metabolism during growth in single carbon sources[END_REF] to mutualism [START_REF] Shukla | Gut microbiota degrades toxic isothiocyanates in a flea beetle pest[END_REF][START_REF] Ceja-Navarro | Gut microbiota mediate caffeine detoxification in the primary insect pest of coffee[END_REF][START_REF] Pieterse | Induced systemic resistance by beneficial microbes[END_REF]. During recent years, some Pseudomonas strains were discovered to play a crucial role in helping different insects overcome biotic challenges such as pesticides or plant defence effectors [START_REF] Shukla | Gut microbiota degrades toxic isothiocyanates in a flea beetle pest[END_REF][START_REF] Ceja-Navarro | Gut microbiota mediate caffeine detoxification in the primary insect pest of coffee[END_REF][START_REF] Wang | Changes in Microbiome Confer Multigenerational Host Resistance after Sub-toxic Pesticide Exposure[END_REF].

Although the bacterium's role in these symbioses is established, the molecular and biochemical mechanisms by which the symbionts are able to protect their respective hosts remain unknown.

Understanding how Pseudomonas species interact with their environment, host-associated or not, is of interest from a fundamental and applied perspective. For example, understanding how these bacteria are able to degrade a wide range of xenobiotics (such as pesticides) could help develop more ecologically-friendly approaches to deal with contaminations due to these xenobiotics. Since such metabolic investigations would ideally be carried out outside of the insect host, the development of suitable bacterial growth media that support good growth and produce consistently high viable cell counts is crucial. Such media are instrumental in studying certain aspects of bacterial metabolism at the biochemical and molecular level (i.e. transcriptomics).

However, for physiological and metabolical studies of these strains, defined/minimal media (liquid and agar) that support good growth and gives consistently high viable cell counts are a staple to unveil the mechanisms of action of metabolical processes and clarify the effects of changes in medium composition on cell growth and product formation. Defined media are culture media whose chemical composition is well known. A defined medium with only the ingredients necessary for the growth of a microorganism is called a minimal medium.

Nevertheless, the number of ingredients that compose a minimal medium varies enormously and depends mainly on which microorganism is cultivated. Chemically defined minimal media allow for a finer metabolic profiling of the microorganism [START_REF] Singleton | A design of experiments approach for the rapid formulation of a chemically defined medium for metabolic profiling of industrially important microbes[END_REF][START_REF] Roth | Genetic Techniques in Studies of Bacterial Metabolism[END_REF].

Although several defined or minimal nutritional media have been used for the genus Pseudomonas, most of the media were developed for the most common species (e.g., P. syringae, P. aeruginosa, P. fluorescens;) [START_REF] Labauve | Growth and laboratory maintenance of Pseudomonas aeruginosa[END_REF][START_REF] Mishek | Development of a chemically-defined minimal medium for studies on growth and protein uptake of Gemmata obscuriglobus[END_REF][START_REF] Sörensen | Comparative evaluation of the effect of different growth media on in vitro sensitivity to azithromycin in multi-drug resistant Pseudomonas aeruginosa isolated from cystic fibrosis patients[END_REF] and the growth performance of other strains on these media have rarely been investigated. Therefore, there is a need to test the already available minimal defined media and possibly develop more suitable ones for other Pseudomonas species.

Here, we aimed to determine an ideal minimal defined medium to grow a strain of P. azotoformans, isolated from an insect gut, in the laboratory. To this end, we compared the growth performance of this strain on several media to a rich medium (i.e. Luria Bertani broth).

Materials and methods

Strain:

The bacterial strain was isolated from the gut of the beetle Galeruca laticollis plated on LB agar media and incubated at 30°C. The strain was initially identified based on its 16S rRNA gene sequence, and the taxonomic assignment was later confirmed through a phylogenomic analysis (data subject of a separate publication). The strain was identified as Pseudomonas azotoformans strain GL93.

Culture media and growth conditions:

In addition to LB media, which was used as a growth reference, five minimal media (namely SMM, M9, MOPS, MMV, and MMP) were tested (see supplementary file S1 for details).

During the first test, bacteria grown on MMP produced fluorescent siderophores that could potentially interfere with the optical density (OD) readings. In order to minimize the production of these siderophores, the medium was supplemented with calcium chloride (CaCl2; supplementary figure S1).

The bacterium was incubated overnight at 30°C in a fresh LB medium prior to the experiments.

Log-phase cells were collected by centrifugation at 2000 g for 10 minutes and washed three times in a sterile NaCl 9‰ solution to remove any remnants of the previous growth medium.

Finally, the cells were concentrated to the desired concentration (10 8 cells/ml), and 1 ml was used for the inoculation of different growth media. To test if the bacterium could grow on the different media, 100 ml of each medium were inoculated with 1 ml of a NaCl 9‰ solution containing 10 8 bacterial cells. Bacterial growth at 30°C was monitored for seven days, taking OD readings at 24h intervals using an ONDA V-10 plus spectrophotometer.

Three minimal media (SMM, M9 and MMP+CaCl2) as well as LB proved suitable to grow the Pseudomonas strain (i.e. ODmedium > ODLB*0.2 after seven days) and were used in a second experiment. A 24-well plate was prepared with 200 µl of a given medium per well, one medium per row (see supplementary figure S2 for an illustration of the experimental design). Five out of the six wells for each medium were inoculated with 10 µl of the bacterial inoculate prepared as outlined above. The last well was used as blank. Bacterial growth was monitored for six days on a BioTek Synergy H1 multi-plate reader with OD readings at 600 nm every 15 minutes, preceded by 5 seconds of orbital shaking to homogenize the cultures. The experiment was carried out twice, once at 30°C and a second time at 25 °C.

Data analyses:

the R (https://cran.r-project.org) package growthcurver (https://github.com/sprouffske/growthcurver [START_REF] Sprouffske | Growthcurver: An R package for obtaining interpretable metrics from microbial growth curves[END_REF]) was used to infer the different terms of each logistic curve equation Nt = N0 K N0 + (K-N0) e (-rt) , where Nt is the number of cells (or the absorbance reading) at time t, N0 is the initial cell count (or absorbance reading), K is the carrying capacity, and r is the growth rate. The Dynamic Time Warping (DTW; [START_REF] Berndt | Using dynamic time warping to find patterns in time series[END_REF]) Algorithm from the package SimilarityMeasures (https://cran.rproject.org/web/packages/SimilarityMeasures/) was then used to determine the similarity between the different growth curves. First, we compared the growth curves between the replicates of each growth medium to exclude outliers. To this end, the values generated by pairwise comparisons of all growth curves were aggregated in a similarity distance matrix and visualized after hierarchical clustering. Secondly, we compared the averaged growth curves (i.e., curve resulting from the averaged values of the single curves) of the different media using the same approach used for the intra-medium comparisons.

Metabolic pathway assessment:

The metabolic capacities of P. azotoformans were checked using the four complete genomes available on the NCBI database (accession numbers: LT629702, CP041236, CP014546 and CP019856). In particular, the protein sequences of each genome were downloaded and submitted to GhostKOALA (ver 2.2, [START_REF] Kanehisa | BlastKOALA and GhostKOALA: KEGG tools for functional characterization of genome and metagenome sequences[END_REF]) for metabolic pathway reconstruction. The pathways related to the central metabolism (e.g., glycolysis, pentose phosphate, TCA cycle, purine and pyrimidine synthesis, amino acid synthesis) were checked visually for completeness.

Results and discussion

Growth performance of P. azotoformans GL93 on different media P. azotoformans was able to grow on all tested media but with very different growth performances (Table 1, Supplementary figure S3). As such, the bacterium reached the stationary phase on LB medium in less than 24h (mean = 18h), but it took longer to reach this phase on other media. It took ca 24h for the bacteria to reach the stationary phase on MMV, ca 36h on M9 and more than 48h on the other media. MOPS was the medium with the longest lag phase (mean = 36h). Similarly, the shortest generation time was observed on LB (ca. 1h) and the longest on both MMP and SMM (ca. 20h). However, P. azotoformans reached higher bacterial densities in MMP (OD600 = 1.18 ± 0.04) and SMM (OD600 = 1.3 ± 0.01) than in all other media, including LB (OD600 ≈ 1 ± 0.01). In the other media, the maximum value of OD600 remained inferior to one (namely M9: 0.3 ± 0.01, MMP + CaCl2: 0.2 ± 0.004, MMW: 0.12 ± 0.005, and MOPS: 0.03 ± 0.004). It is noteworthy that the addition of CaCl2 to the MMP medium reduced the production of siderophores (see Supplementary figure S1), but also had a notable effect on both the optical density (which decreased from an OD600 of 1.18 ± 0.04 to 0.2 ± 0.004) and on the generation time, lowering it from 20h to 12h. A possible explanation could be that, since the bacterium no longer produced siderophores, more resources could be invested into growth, resulting in a shortening of the time needed for cellular division. Considering the low bacterial density achieved on MMW and MOPS compared to LB (OD600 of 0.12 and 0.03, respectively), these two media were not included in subsequent experiments. The low growth performance on these two media could be due to a chemical being present at a highly limiting concentration or a growth-inhibiting factor for our strain. The reported values are the average of three readings and the standard error Identification of the best minimal medium for P. azotoformans The growth of P. azotoformans on the selected media (SMM, M9, and MMP + CaCl2, hereafter MMP) was monitored every 15 minutes at two constant temperatures (i.e., 25°C and 30°C).

The data obtained from 5 replicate cultures for each medium at both temperatures was used to infer the theoretical growth curve for each culture (Figs 1,3). Comparing the growth curves of the five replicate cultures for each medium at both temperatures (Fig. 2, 4) revealed a certain degree of variability between replicates for some conditions. In particular, there was some variability in the exponential growth phase for M9 at both temperatures and for MMP at 30°C (Fig. 2,4). In order to determine which replicates represented significant deviations from the general trend of each medium, we applied the DTW algorithm on a pairwise distance matrix between the replicates. Using this approach, several replicates were indeed determined to be outliers: 1 LB replicate, 1 SMM replicate and 2 M9 replicates at 25°C (Supplementary Figure S4), as well as 1 SMM and 1 M9 replicate at 30°C (Supplementary Figure S6). No outliers were detected among the different replicates of MMP at both temperatures. The replicates determined to be outliers were removed and the remaining replicates were used to calculate the average theoretical growth curve for each medium at both temperatures (Supplementary Figures S5,S7). Comparing the average growth curves of the three minimal media to that of the rich LB medium revealed that the SMM medium performed best and even surpassed the LB medium in terms of bacterial density (i.e. higher OD600) in the stationary phase (Fig. 5A,C). In contrast, the other two minimal media M9 and MMP could not sustain the same growth and vitality performance (Fig. 5). MMP was the most different from bacterial growth on the LB medium.

This was also evident from the inferred generation time at each medium based on the average absorbance values: generation time at 25°C was 99 min, 432 min, 560 min and 609 min on LB, SMM, M9 and MMP, respectively (Supplementary figure S5; tables 2, 3). When comparing the growth performances on the different media at 25° and 30°C, it emerged that Pseudomonas generally grew more slowly at 30°C than at 25°C. Hence, generation time at 30°C was 162 min, 446 min, 684 min and 1100 min on LB, SMM, M9 and MMP, respectively (Supplementary figure S7; tables 2, 3). SMM represents the exception to this trend, since bacteria growing on SMM had similar growth rates at both temperatures (average generation time at 25°C: 432 min vs average generation time at 30°C: 446). Despite growing 188 at a similar rate, bacterial density remained lower at 30°C than at 25°C (Fig. 5 A.C).

189 Taken together, P. azotoformans grown on SMM performed best compared to the other minimal media (shorter generation time and higher bacterial density). However, it was not comparable to growth on a rich medium.

Based on the metabolism of P. azotoformans inferred from the available genomes on the NCBI database (Table 4), we can hypothesize that the higher growth performance on the SMM medium could be due to minimal composition. SMM contains the necessary glucose as a carbon source, glutamine as a nitrogen source, K2HPO4 as a phosphate source and MgSO4 as a sulfur source. These four ingredients are sufficient in P. azotoformans for the biosynthesis of all the needed building blocks for metabolism and growth. The addition of other nutrients, such as for the other media tested, will probably trigger other, possibly secondary, metabolic pathways. These active metabolic pathways could divert resources (e.g., ATP, metabolites) from the central metabolism, thus slowing the growth and multiplication of the bacterial cells.

This may result in slower performances when P. azotoformans is incubated in more complex media.

Conclusion

An optimal medium allows for good microbial growth, which can be summarised as short generation time and high cell concentration in solution. In light of the results achieved here, the SMM medium is the most suitable medium for studying the metabolism of P. azotoformans.

SMM outperformed the other two media (i.e., M9 and MMP), and the bacterial growth performances were consistently closer to those on LB. Furthermore, while the optimal growth temperature is 25°C, the SMM medium was the least susceptible to performance variations at a suboptimal growth temperature.

The better growth performance on the SMM medium could be partly explained by the fact that the medium contains the necessary nutrients sufficient for the biosynthesis of all the needed building blocks for metabolism and growth. In addition, P. azotoformans is a phylogenetic closer to P. fluorescens [START_REF] Anzai | Phylogenetic affiliation of the pseudomonads based on 16S rRNA sequence[END_REF], which SMM was originally designed, than other Pseudomonas species. In contrast, most of the other minimal media tested here had been designed for P.

aeruginosa, except for the more generic MMP. The phylogenetic proximity with P. fluorescens may suggest similar metabolic needs between the two species. Thus, a medium developed for one of the two species could offer better growth performances for the second species than media developed for more distant relatives.

Figure 1 :

 1 Figure 1: Growth curves obtained from the absorbance readings of the different media incubated at 25°C. The experimental curves (grey dots) correspond to the absorbance values recorded every 15 minutes for seven days. Each column corresponds to a medium, and each graph shows the growth performance in a single well (N=5 per medium). The red line represents the theoretical curve fitted over the experimental points.

Figure 2 :

 2 Figure 2: The theoretical growth curves of the 5 replicate cultures per medium at 25°C.

Figure 3 :

 3 Figure 3: Growth curves obtained from the absorbance readings of the different media incubated at 30°C. The experimental curves (grey dots) correspond to the absorbance values recorded every 15 minutes for seven days. Each column corresponds to a medium, and each graph describes the growth performance in a single well (N=5 per medium). The red line represents the theoretical curve fitted over the experimental points.

Figure 4 :

 4 Figure 4: The theoretical growth curves of the 5 replicate cultures per medium at 30°C.

Figure 5 :

 5 Figure 5: Comparison of the growth performance of P. azotoformans on the different media at 25°C (A, B) and 30°C (C, D). A and C: Averaged theoretical growth curves on the different media. B and D: Dendrograms of the curves' similarity using the DTW metric.

Table 1 : Optical density (OD) readings at 600 nm for each medium.

 1

	Medium\time (h)	0	24	48	72	144	168
	LB	0.03±0.01 1.19±0.04	0.98±0.04	0.91±0.02	0.97±0.04	0.94±0.02
	SMM	0.02±0.02 0.37±0.01	0.53±0.02	0.66±0.02	1.16±0.01	1.3±0.01
	M9	0.02±0.02 0.07±0.01	0.42±0.02	0.39±0.03	0.24±0.01	0.3±0.01
	MOPS	0	0.02±0	0.03±0.01	0.04±0.01	0.03±0	0.03±0
	MMW	0±0	0.16±0	0.18±0	0.15±0	0.1±0	0.12±0
	MMP	0	0.32±0.01	0.49±0.02	0.65±0.02	1.08±0.03	1.18±0.04
	MMP + CaCl2	0±0	0.12±0	0.18±0	0.2±0.01	0.21±0.01	0.2±0

Table 2 : Logistic curve parameters estimated for each sample both at 30°C and 25°C 190

 2

					30°C				25°C
		Sample	K	N0	r	Generation time	K	N0	r	Generation time
		LB1	1.811	0.101	0.004	168	1.979	0.007	0.007	93
		LB2	1.956	0.109	0.004	171	2.094	0.011	0.007
		LB3	1.924	0.091	0.004	157	2.161	0.014	0.006
		LB4	1.882	0.094	0.004	159	2.075	0.013	0.006
		LB5	1.914	0.094	0.004	158	1.964	0.006	0.007	93
		SMM1	1.896	0.006	0.002	363	2.232	0.015	0.002
		SMM2	2.008	0.015	0.001	448	2.368	0.02	0.002
		SMM3	1.994	0.022	0.001	497	2.408	0.02	0.002
		SMM4	1.978	0.017	0.001	490	2.415	0.017	0.002
		SMM5	1.770	0.020	0.001	474	2.277	0.013	0.002
		M91	0.911	0.035	0.001	536	0.996	0.076	0.001
		M92	1.298	0.080	0.001	831	0.98	0.048	0.001
		M93	1.257	0.069	0.001	739	0.989	0.039	0.002
		M94	1.172	0.070	0.001	700	1.061	0.033	0.002
		M95	1.016	0.072	0.001	670	1.05	0.032	0.002
		MMP1*	0.397	0.022	0.001	643	0.261	0.027	0.001
		MMP2*	0.733	0.050	0.001	1391	0.243	0.026	0.001
		MMP3*	1.144	0.059	0.001	1670	0.236	0.024	0.001
		MMP4*	0.601	0.055	0.001	1247	0.218	0.023	0.001
		MMP5*	0.459	0.025	0.001	784	0.25	0.028	0.001
	191	* The medium contains CaCl2 at the concentration reported in the supplementary file

Table 3 : Logistic curve parameters estimated for the averaged curve for each medium both at 192

 3

	193	30°C and 25°C
					30°C				25°C
		sample	K	N0	r	Generation time	K	N0	r	Generation time
		LB	1.897	0.098	0.004	163	2.028	0.009	0.007	99
		SMM	1.963	0.014	0.002	446	2.355	0.018	0.002
		M9	1.063	0.062	0.001	684	0.981	0.054	0.001
		MMP*	0.557	0.043	0.001	1100	0.241	0.025	0.001

* The medium contains CaCl2 at the concentration reported in the supplementary file 194

Acknowledgements

BC would like to thank Jessica Dittmer for the critical reading of the paper.