Martin Grohe
email: grohe@math.uic.edu

Thomas Schwentick

Luc Segoufin
email: luc.segoufin@inria.fr.

When is the evaluation of conjunctive queries tractable ?

The evaluation of conjunctive queries is hard both with respect to its combined complexity (NP-complete) and its parameterized complexity (W[1]-complete). It becomes tractable (PTIME for combined complexity, FPT for parameterized complexity), when the underlying graphs of the conjunctive queries have bounded tree-width [2]. We show that, in some sense, this is optimal both with respect to combined and parameterized complexity: For every class C of graphs, the evaluation of all conjunctive queries whose underlying graph is in C is tractable if, and only if, C has bounded tree-width. A technical result of independent interest is that the colored grid homomorphism problem is NP-complete and, if parameterized by the grid size, W[1]-complete.

Introduction

Conjunctive queries are relational database queries expressed by formulas of first-order logic that are of the form ∃y1 . . . ∃y l (α1 ∧ . . . ∧ αn), where the αi are atomic formulas. Conjunctive queries are fundamental for relational database systems, and they are the queries appearing most frequently in practice. The conjunctive query evaluation problem is the following: Given a finite relational structure (or database instance) A and a conjunctive query ϕ(x1, . . . , x k ), compute the set ϕ(A) := {(a1, . . . , a k ) | A |= ϕ(a1, . . . , a k )}. In the complexity theo-retic analysis of this paper, we will focus on the associated decision problem of whether ϕ(A) is empty or not.

We will measure the complexity of query evaluation in two different ways. The most straightforward measure, where the complexity is measured simply in terms of the input size, i.e. size of the structure A plus length of the formula ϕ, is called the combined complexity of the query evaluation problem [START_REF] Vardi | The complexity of relational query languages[END_REF]. Chandra and Merlin [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] proved in 1977 that the combined complexity of conjunctive query evaluation is NP-complete. However, the main factor responsible for the high complexity of the problem is the length of the input formula and not the size of the database. This does not fit the practical situation very well, because usually one evaluates a short query against a large database. It is easy to see that conjunctive (and, more general, first-oder) queries can always be evaluated in time ||A|| O(||ϕ||) , where ||A|| denotes the size of the input structure A and ||ϕ|| the length of the formula ϕ. Thus conjunctive query evaluation is possible in time polynomial in the structure size. However, even for short queries ϕ, say, of length ||ϕ|| = 10, ||A|| ||ϕ|| is not a feasible complexity. Yannakakis [START_REF] Yannakakis | Perspectives on database theory[END_REF] was the first to suggest that parameterized complexity might be an appropriate way to measure the complexity of database query evaluation. We say that the query evaluation problem is fixed-parameter tractable (FPT) if there is a computable function f : N → N and a constant c > 0 such that the problem can be solved in time f (||ϕ||) • n c . The idea is that we can disregard the dependence on the formula length as long as it does not appear in the exponent of the structure size. Of course, the notion of fixed-parameter tractability is only another mathematical abstraction of "practical tractability", but in the situation of query evaluation it seems to be the most appropriate abstraction. Unfortunately, it turns out that the parameterized complexity of conjunctive query evaluation is W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]-complete and thus most likely not fixed-parameter tractable; this result, observed by Papadimitriou and Yannakakis [START_REF] Papadimitriou | On the complexity of database queries[END_REF], can be seen as the parameterized analogue of the NP-completeness of the combined complexity.

The results mentioned in the previous paragraph show that conjunctive query evaluation is hard both with respect to its combined complexity and its parameterized complexity. Therefore, it is natural to look for classes of conjunctive queries for which the evaluation is tractable. The archetypal result of this form, due to Yannakakis [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF], states that the evaluation of acyclic conjunctive queries is possible in polynomial time (and therefore both tractable in the classical sense of combined complexity and fixed-parameter tractable). This result has been improved in several ways.

One of the approaches for finding tractable queries is the following: With every conjunctive query ϕ we associate its underlying graph Gϕ whose vertices are the variables of ϕ, with an edge between two variables x and y if there is an atom of ϕ that contains both x and y. Then the hope is that the evaluation of a query is easy if its underlying graph is "simple". Tree-width, measuring the similarity of a graph with a tree, turns out to be a good notion of simplicity. Chekuri and Rajaraman [START_REF] Ch | Conjunctive query containment revisited[END_REF] have proved that evaluation of conjunctive queries of bounded tree-width is possible in polynomial time. (The result is presented here using a different formalization due to Kolaitis and Vardi [START_REF] Ph | Conjunctive-query containment and constraint satisfaction[END_REF]). Gottlob, Leone, and Scarcello [START_REF] Gottlob | The complexity of acyclic conjunctive queries[END_REF] showed that this problem is actually LOGCFL-complete, for each fixed tree-width k. Other, similar approaches are based on the underlying hypergraph of a query. Appropriate notions of simplicity of queries obtained this way are bounded query-width [START_REF] Ch | Conjunctive query containment revisited[END_REF] and bounded hypertree-width [START_REF] Gottlob | Hypertree decompositions and tractable queries[END_REF]. Although these notions are equivalent to bounded tree-width when the schema of the database is considered as fixed, the hypergraph based approach leads to more general classes of queries when the schema is not fixed (see [START_REF] Gottlob | Hypertree decompositions and tractable queries[END_REF] for a comparison of the different approaches). In this paper, we focus on the graph based approach. We show that Chekuri and Rajaraman's result is optimal both with respect to combined complexity and parameterized complexity. Under the complexity theoretic assumption that FPT = W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF], which can be seen as the analogue of PTIME = NP in the parameterized world, we show that for every class C of graphs the following three statements are equivalent:

(1) The evaluation of all conjunctive queries whose underlying graph is in C is fixed-parameter tractable.

(2) The evaluation of all conjunctive queries whose underlying graph is in C is in polynomial time.

(3) The class C has bounded tree-width.

To prove this, we show that if C does not have bounded tree-width, the evaluation problem for conjunctive queries whose underlying graph is in C is W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]-complete. This also yields a nice dichotomy: Either the evaluation problem for queries with underlying graph in C is W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]-complete, or it is fixed-parameter tractable.

Another noteworthy aspect of this result is that the equivalence between (2) and (3) that is only concerned with classical complexity theory is proved under an assumption from parameterized complexity theory. Under the weaker assumption that PTIME = NP, we can only prove the equivalence of statements ( 2) and ( 3) for all classes of graphs that are closed under taking minors.

In the last section of the paper, we extend our results to the existential fragment of first-order logic by showing that tractability of query evaluation is linked to an expressive power limited by the number of variables.

The main ingredient of our proofs is of independent technical interest: We show that the colored grid homomorphism problem, asking whether a given 2-colored grid can be mapped homomorphically to a given colored graph is NP-complete and, if parameterized by the grid size, W[1]complete. We also prove a similar result for directed grids. These results are linked to tree-width by the deep Excluded Grid Theorem due to Robertson and Seymour [START_REF] Robertson | Graph minors V. Excluding a planar graph[END_REF].

Preliminaries

Relational Structures. A vocabulary is a finite set of relation symbols. The arity of a vocabulary is the maximum of the arities of all relations symbols it contains.

(a) = i if a ∈ C G i . The distance d G (a, b
) between two points a, b in a graph or colored graph is the length of the shortest path from a to b. For m, n ≥ 1, the (m, n)-grid is the graph Gm,n with universe Gm,n := {1, . . . , m} × {1, . . . , n} and edge relation

E Gm,n := (i, j), (i , j ) ∈ G 2 m,n (i = i and |j -j | = 1)
or (|i -i | = 1 and j = j ) .

If m = n, then we call Gm,n a square grid. A homomorphism from a τ -structure A to a τ -structure B is a mapping h : A → B such that for every R ∈ τ and (a1, . . . , ar) ∈ R A we have (h(a1), . . . , h(ar)) ∈ R B . HOM(A, B) is the set of all homomorphisms from A to B. For every class C of structures, we consider the following problem:

C-Homomorphism

Input: Structures A ∈ C, B. Problem: Is there a homomorphism from A to B.

It is well known that Graph-Homomorphism is NP-complete (where Graph denotes the class of all graphs).

Parameterized complexity. A parameterized problem is a set P ⊆ Σ * × Π * , where Σ and Π are finite alphabets. We usually represent a parameterized problem P in the following form:

Input: I ∈ Σ * . Parameter: π ∈ Π * Problem: Decide if (I, π) ∈ P .
In this paper, we always have Π = {0, 1} and consider the parameters π ∈ Π * as natural numbers (in binary). Observe that ≤ fp T and ≤ fp m are transitive and that P ≤ fp m P implies P ≤ fp T P . Furthermore, if P ≤ fp T P and P ∈ FPT then P ∈ FPT. We define hardness and completeness of parameterized problems for a parameterized complexity class (under parameterized m-or T-reductions) in the usual way. If we do not specify the reduction-type in a hardnessresult, we always refer to m-reductions. Downey and Fellows defined a hierarchy W

[1] ⊆ W[2] ⊆ • • •
of parameterized complexity classes, and they conjecture that this hierarchy is strict and that FPT is strictly contained in W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. The classes of the W-hierarchy are defined in terms of a parameterized version of the satisfiability problem for bounded-depth Boolean circuits. We refer the reader to [START_REF] Downey | Parameterized Complexity[END_REF] for the technical definitions. In this paper, we are only interested in the class W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF], which can be seen as an analogue of NP in parameterized complexity theory. Our results are based on the following Theorem 1. Remember that the Clique-problem is one of the basic NPcomplete problems [START_REF] Karp | Reducibilities among combinatorial problems[END_REF]:

Clique Input: Graph G, integer k ≥ 1. Problem: Decide if G has a k-clique.

Its parameterized version

Parameterized Clique

Input:

Graph G, integer k ≥ 1. Parameter: k Problem: Decide if G has a k-clique.
plays a similar role in parameterized complexity theory.

Theorem 1 (Downey and Fellows [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W [1[END_REF]).

Parameterized Clique is W[1]-complete (under parameterized m-reductions).

For any class C of structures, consider the following parameterized version of the homomorphism problem:

Parameterized C-Homomorphism Input: Structures A ∈ C, B. Parameter: ||A|| Problem: Decide if there is a homomorphism from A to B.
Parameterized C-Homomorphism is in W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] for every C. By a trivial reduction from Parameterized Clique, it can be seen that Parameterized Graph-Homomorphism is W[1]-complete. The following lemma will be needed later: Tree-decompositions and minors. A tree is an acyclic graph. A tree-decomposition of a τ -structure A is a pair (T , (Bt)t∈T ), where T is a tree and (Bt)t∈T a family of subsets of A (the blocks of the decomposition) such that

Lemma 2. Let C
(1) For every a ∈ A, the set {t ∈ T | a ∈ Bt} is non-empty and connected in T (that is, induces a subtree).

(2) For every R ∈ τ and all ā ∈ R A there is a t ∈ T such that ā ∈ Bt.

The width of a tree-decomposition (T , (Bt)t∈T ) is max{|Bt| | t ∈ T }-1. The tree-width tw(A) of A is the minimum taken over the widths of all tree-decompositions of A.

A

Grid homomorphism

For c ≥ 1, let c-Grid be the class of all c-colored square grids. We shall prove that c-Grid Homomorphism is NPcomplete and Parameterized c-Grid Homomorphism is W[1]-complete for every c ≥ 2. Before we show this, we observe that 1-Grid Homomorphism is trivially in PTIME, because as a bi-partite graph every grid has a homomorphism to a single edge. We also observe that, as an instance of the general Homomorphism problem for relational structures, c-Grid Homomorphism is contained in NP, and its parameterized version is contained in W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. Thus we just have to prove hardness. Of course it suffices to consider the case c = 2 (which, by the way, is considerably harder than c ≥ 3).

Let n ≥ 6 be even. We let Sn be the 2-colored (n × n)-grid with (cf. Figure 1(a))

C Sn 1 := (1, 1), (1, 2), (1, n), (2, 1), (4, 1), (n, 1)
∪ (i, j) ∈ Sn i + j ≥ n + 4, (i + j -n) ≡ 0 (mod 4) or (i + j -n) ≡ 1 (mod 4) , C Sn 2 :=Sn \ C Sn 1 .
The first major step in the proof of our completeness results is the following lemma:

Lemma 5. HOM(Sn, Sn) = {id} (i.e. the only homomorphism from Sn to Sn is the identity).

The proof requires some preparation. For every m ≥ 1 we let Pm be the 2-colored path with universe Pm := {1, . . . , m}, edge relation E Pm := (i, j) |i -j| = 1 , and

C Pm 1 := i ∈ Pm i ≡ 1 (mod 4) or i ≡ 2 (mod 4) , C Pm 2 :=Pm \ C Pm 1 . 1 -1 -2 -2 -2 -2 -2 -1 (b) The colored grid S 8 Figure 1.
Let X := {(1, 1), (2, 1), (4, 1), (n, 1), (1, n)}. We define a mapping hn : Sn → Pn+1 by hn((i, j)) := , and thus i1 ≡ 1 (mod 4) or i1 ≡ 2 (mod 4). Case 1: i1 ≡ 1 (mod 4).

                                 1 if (i, j) = (1, 1), 2 if (i, j) ∈ X \ {(1, 1)}, 3 if (i, j) ∈ X and i + j < n + 4 and i + j ≡ 0 (mod 2), 4 if (i, j) ∈ X and i + j < n + 4 and i + j ≡ 1 (mod 2), i + j -n + 1 if i + j ≥ n + 4 (cf.
Then h((1, 2)) = h((2, 1)) = i1 + 1. Since (4, 1), (n, 1), and (1, n) are reachable in Sn from (2, 1) by paths of even length whose inner vertices are all in C Sn 2 , we must have h((4, 1)) = h((n, 1)) = h((1, n)) = i1 + 1. Similarly, all (i, j) with (i, j) ∈ X, i + j < n + 4, and i + j ≡ 0 (mod 2) are reachable in Sn from (2, 1) by paths of odd length whose inner vertices are all in C Sn 2 . Hence we have h((i, j)) = i1 +2. All (i, j) with (i, j) ∈ X, i + j < n + 4, and i + j ≡ 1 (mod 2) are reachable in Sn from (2, 1) by paths of even length whose inner vertices are all in C Sn 2 . Hence we have h((i, j)) = i1 +3. All (i, j) with (i, j) ∈ X and i + j = n + 4 are reachable in Sn from (2, 1) by paths of odd length whose inner vertices are all in C Sn 2 . Hence we have h((i, j)) = i1 + 4. Now a simple induction shows that for all (i, j) with i + j ≥ n + 4 we have h((i, j)) = i1 + i + j -n. Altogether, this shows that i1 = 1 and h = hn. Case 2: i1 ≡ 2 (mod 4). We argue similarly as in Case 1 with the direction of the path reversed and show that i1 = n + 1. Then h((2, 1)) = n, which implies 1 = col Sn ((2, 1)) = col Pn (n). But this immediately yields a contradiction since n ≡ 0 (mod 4) and thus col Pn (n) = 2.

2

We now define an (n + 1)-colored (n, n)-grid S n by letting col S n (a) = hn(a) for all a ∈ S n = Sn.

is no a ∈ C S n 4 with d S n ((1, 1), a) ≤ 3, d S n ((n, 1), a) ≤ n -4, we have h((1, n)) = (1, n).
Thus h is the identity on the four corner points of S n . Now a simple induction using [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] shows that h = id.

2

Let k ≥ 4 such that k ≡ 0 (mod 4) or k ≡ 1 (mod 4). Then K := k 2 is even. Let f : {1, . . . , K} → {{i, j} | 1 ≤ i < j ≤ k} be the bijection that maps l to the lth element in the lexicographic order of {i, j} 1 ≤ i < j ≤ k . Let H be an arbitrary graph. For a ∈ H and e = (b, c) ∈ E H we write a ∈ e to denote that a is an endpoint of e, i.e. that a ∈ {b, c}. We define a 2-colored graph H k as follows:

H k := (a, e, i, p) a ∈ H, e ∈ E H , 1 ≤ i ≤ k, 1 ≤ p ≤ K such that i ∈ f (p) ⇐⇒ a ∈ e ∪ (i, p) k + 1 ≤ i ≤ K, 1 ≤ p ≤ K}, E H k := (a, e, i, p), (a , e, i , p) a, a ∈ H, e ∈ E H , 1 ≤ i, i ≤ k, |i -i | = 1, 1 ≤ p ≤ K ∪ (a, e, i, p), (a, e , i, p ) a ∈ H, e, e ∈ E H , 1 ≤ i ≤ k, 1 ≤ p, p < K, |p -p | = 1 ∪ (a, e, k, p), (k + 1, p) , (k + 1, p), (a, e, k, p) a ∈ H, e ∈ E H , 1 ≤ p ≤ K} ∪ (i, p), (i , p ) (i, p), (i , p ) ∈ E S K , k + 1 ≤ i ≤ K, 1 ≤ p ≤ K , C H k j := (a, e, i, p) a ∈ H, e ∈ E H , 1 ≤ i ≤ k, 1 ≤ p ≤ K, (i, p) ∈ C S K j } ∪ (i, p) k + 1 ≤ i ≤ K, 1 ≤ p ≤ K, (i, p) ∈ C S K j } (for j ∈ {1, 2}).
The following lemma is obvious: It is easy to check that h is a homomorphism. Note that the main point is to verify that h is well-defined.

Lemma 8.
For the backward direction, suppose that h : SK → H k is a homomorphism. Then by Lemma 8, π • h : SK → SK is a homomorphism. Thus, recalling that K ≥ 6 is even, by Lemma 5, π • h is the identity. Hence for all 1 ≤ i ≤ k, 1 ≤ p ≤ K there are aip, eip such that h(i, p) = (aip, eip, i, p). By the definition of E H k , this implies aip = aiq =: ai for 1

≤ i ≤ k, 1 ≤ p, q ≤ K and eip = ejp =: ep for 1 ≤ i, j ≤ k, 1 ≤ p ≤ K.
Then by the definition of H k , for 1 ≤ i ≤ k and 1 ≤ p ≤ K we have ai ∈ ep if, and only if, i ∈ f (p). Thus e f -1 ({i,j}) is an edge between ai and aj, and therefore {a1, . . . , a k } is a clique of H. 2

The following lemma is again obvious:

Lemma 10. There is a polynomial time algorithm that, given a graph H and a k with 4 ≤ k ≤ |H| and k ≡ 0, 1 (mod 4), computes SK and H k .

Thus the NP-completeness of Clique and the W[1]-completeness of Parameterized Clique immediately yield the following Theorem 11. There is a slight problem in that we only have a reduction for k ≥ 4 with k ≡ 0, 1 (mod 4). However, we can use the simple fact that for all l < k, a graph H has an l-clique if, and only if, the graph obtained from H by adding (k -l) vertices and connecting them with each other and all old vertices has a k-clique. For every n ≥ 1 we let S d n be the directed acyclic (n × n)gridthat is obtained by directing the edges of Gn,n according to the Hamiltonian path (cf. Figure 2).

(1, 1), (1, 2), . . . , (1, n), (2, n), . . . , (2, 1), (

Conjunctive Query Evaluation

Atomic formulas, or atoms, are expressions of the form x = y or Rx1 . . . xr, where R is an r-ary relation symbol and x, y, x1, . . . , xr are variables. The formulas of first-order logic FO are build up in the usual way from the atomic formulas using the connectives ∧, ∨, ¬, →, and the quantifiers ∀, ∃. The vocabulary of a first-order formula ϕ, denoted by τ (ϕ), is the set of all relation symbols occurring in ϕ. If L is a class of formulas, then L[τ ] denotes the class of all ϕ ∈ L with τ (ϕ) ⊆ τ . FO denotes the class of all first-order formulas, and EFO the subclass of all existential first-order formulas, i.e. all formulas that do not contain any universal quantifiers and in which existential quantifiers only occur in the scope of an even number of negation symbols. The set of all atomic subformulas of a formula ϕ is denoted by at(ϕ). A free variable of a first-order formula is a variable x not in the scope of a quantifier ∃x or ∀x. The set of all free variables of a formula ϕ is denoted by free(ϕ), the set of all variables of ϕ by var(ϕ). The notation ϕ(x1, . . . , x k ) indicates that free(ϕ) = {x1, . . . , x k }. A sentence is a formula without free variables. For a formula ϕ(x1, . . . , x k ), a τ (ϕ)-structure A, and elements a1, . . . , a k ∈ A, we write A |= ϕ(a1, . . . , a k ) to say that A satisfies ϕ if the variables x1, . . . , x k are interpreted by the elements a1, . . . , a k , respectively. We let

ϕ(A) := (a1, . . . , a k ) ∈ A k A |= ϕ(a1, . . . , a k ) .
We shall study the complexity of the following problem for fragments L ⊆ FO:

L-Evaluation Input: Formula ϕ ∈ L, τ (ϕ)-structure A. Problem: Decide if ϕ(A) = ∅.
Note that we have turned the actual problem of evaluating the input query, i.e. computing the set ϕ(A), into a decision problem here. This is appropriate for the complexity theoretic considerations made in this paper. The natural parameterization of query-evaluation is by the length of the input formula:

Parameterized L-Evaluation Input: Formula ϕ ∈ L, τ (ϕ)-structure A. Parameter: ||ϕ|| Problem: Decide if ϕ(A) = ∅.
FO-Evaluation is PSPACE-complete [START_REF] Stockmeyer | The Complexity of Decision Problems in Automata Theory[END_REF], and Parameterized FO-Evaluation is complete for the parameterized complexity class AW [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] [5]that it is W[1]-hard.

Conjunctive Queries. A conjunctive query is a firstorder formula of the form ∃x1 . . . ∃x k α1 ∧ . . . ∧ αn), where α1, . . . , αn are atoms. The class of all conjunctive queries is denoted by CQ. CQ-Evaluation is NP-complete [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF], and Parameterized CQ-Evaluation is W[1]-complete [START_REF] Papadimitriou | On the complexity of database queries[END_REF]. Both hardness results are immediate consequences of the simple observation that for every k there is a conjunctive query of length O(k 2 ) saying that a graph has a k-clique. Actually, it is easy to see that CQ-Evaluation and Homomorphism are basically the same problem.

The graph G(ϕ) of a first-order formula ϕ has vertex set G(ϕ) := var(ϕ) and edge set E G(ϕ) := (x, y) x = y, ∃α ∈ at(ϕ) : x, y ∈ var(α)

For a class C of graphs we let CQ(C) := {γ ∈ CQ | G(γ) ∈ C}.

Theorem 14 (Chekuri and Rajaraman [START_REF] Ch | Conjunctive query containment revisited[END_REF]). Let C be a class of graphs of bounded tree-width. Then CQ(C)-Evaluation is in PTIME.

Remark 2. Chekuri and Rajaraman define the graph of a formula differently; they take the incidence graph between atoms and variables. Consequently, they obtain a different notion of tree-width. But this difference is irrelevant here.

Our version of the theorem has first been stated by Kolaitis and Vardi [START_REF] Ph | Conjunctive-query containment and constraint satisfaction[END_REF].

We refer the reader to [START_REF] Flum | Query evaluation via tree-decompositions[END_REF] for a discussion of the different concepts.

Theorem 15. Let C be a class of graphs of unbounded treewidth that is closed under taking minors and τ a vocabulary that is at least binary. Then CQ(C)[τ ]-Evaluation is NPcomplete.

Proof: Without loss of generality we can assume that τ = {E} for the binary relation symbol E. Observe that for every directed (n, n)-grid G there is a conjunctive query γG with G(γG) = Gn,n such that for every directed graph D we have

D |= γG ⇐⇒ HOM(G, D) = ∅.
Since C is closed under taking minors, by Robertson and Seymour's Excluded Grid Theorem 4 it contains all grids, thus for every directed square grid S the query γS belongs to CQ(C). Thus we can reduce Directed Grid Homomorphism to CQ(C)[τ ]-Evaluation. Then the statement of the theorem follows from the NP-completeness of directed grid homomorphism (Theorem 13). 2

Corollary 16. Assume that PTIME = NP. Let C be a class of graphs that is closed under taking minors and τ a vocabulary that contains at least one binary relation symbol.

Then the following three statements are equivalent:

(1) CQ(C)-Evaluation is in PTIME.

(2) CQ(C)[τ ]-Evaluation is in PTIME.

(3) C has bounded tree-width.

With a little extra work, on the parameterized level we get an even cleaner picture; we can drop the restriction of being closed under taking minors that we put on the class C of underlying graphs in Theorem 15.

Theorem 17. Let C be a class of graphs of unbounded treewidth and τ a vocabulary that is at least binary. Then Parameterized

CQ(C)[τ ]-Evaluation is W[1]-complete un- der parameterized T-reductions.
In the proof, we will use the following lemma which is an extension of the second part of Theorem 13.

Lemma 18. Let C be a class of graphs such that for every n ≥ 1 there is a graph G ∈ C with G = Gn,n and E G ⊇ E Gn,n . Then the following problem is W

K := k 2 . Let G ∈ C such that G = GK,K and E G ⊇ E G K,K . Since C is computable, such a G can be found effectively. Now we let A * k be a directed graph with underlying graph G such that HOM(A * k , A * k ) = {id}. Such an A *
k exists by Lemma 12. Let B be an arbitrary graph. Recall that f is a bijection from {1, . . . , K} → {{i, j} | 1 ≤ i < j ≤ k} that maps l to the lth element in the lexicographic order of {i, j} 1 ≤ i < j ≤ k . We define the directed graph B * k as follows:

B * k := (a, e, i, p) a ∈ B, e ∈ E B , 1 ≤ i ≤ k, 1 ≤ p ≤ K such that i ∈ f (p) ⇐⇒ a ∈ e ∪ (i, p) k + 1 ≤ i ≤ K, 1 ≤ p ≤ K}, E B * k := (a, e, i, p), (a , e , i , p ) a, a ∈ B, e, e ∈ E B , 1 ≤ i, i ≤ k, 1 ≤ p, p ≤ K, (i, p), (i , p ) ∈ E A * k , i = i =⇒ a = a , p = p =⇒ e = e ∪ (a, e, i, p), (i , p ) a ∈ B, e ∈ E B , 1 ≤ i ≤ k, k + 1 ≤ i ≤ K, 1 ≤ p, p ≤ K, (i, p), (i , p ) ∈ E A * k ∪ (i, p), (a, e, i , p ), a ∈ B, e ∈ E B , 1 ≤ i ≤ k, k + 1 ≤ i ≤ K, 1 ≤ p, p ≤ K, (i, p), (i , p ) ∈ E A * k ∪ (i, p), (i , p ) k + 1 ≤ i, i ≤ K, 1 ≤ p, p ≤ K, (i, p), (i , p ) ∈ E A * k .
Then it can be proved analogously to Lemma T Parameterized Directed-C-Homomorphism. The only place in the reduction above where we used our assumption that C is computable was when for a given K we computed the graph G ∈ C with G = GK,K and E G ⊇ E G K,K . Now we can no longer compute such a G, we merely know that it exists. To circumvent this problem, we simply do the reduction described above for every graph G with G = GK,K and E G ⊇ E G K,K . Let us explain the procedure in detail: We are given a k and a directed graph B and want to decide whether B contains a k-clique, using an oracle for Parameterized Directed-C-Homomorphism. As above, we let K := k 2 . For every graph G with G = GK,K and E G ⊇ E G K,K we do the following: As described above, we compute directed graphs A * k and B * k such that the underlying graph of A * k is G and there is a homomorphism from A * k to B * k if, and only if, B has a k-clique. Then we use our oracle and let it decide if there is a homomorphism from A * k to B * k . The problem is that the answer we get may be wrong if the graph G we started with is not contained in C. We distinguish between two cases. If the oracle answers 'no' for all G, in particular it answers 'no' for all G in C (remember that at least one such G exists). Therefore, we know that the answer is correct. If we get the answer 'yes' for some G, we can try to compute a homomorphism from A * k to B * k using Lemma 2. Then we can easily check if the answer was correct. If we find a correct 'yes'-instance, we know that B contains a k-clique. Otherwise, we know that for all G in C our oracle answers 'no', and thus that B does not contain a k-clique.

2

We are now ready to prove Theorem 17

Proof: Again, without loss of generality we assume that τ = {E}. By the Excluded Grid Theorem 4, for every n ≥ 1 there exists a graph Gn ∈ C such that Gn,n Gn. We let G n be a connected component of Gn such that Gn,n G n and µn : Gn,n G n a minor map such that a∈Gn,n µn(a) = G n . We can always find such a minor map because G n is connected. We let G n be the graph with universe G n := Gn,n and edge set

E G n := (a, b) ∃a ∈ µn(a), b ∈ µn(b) : (a , b ) ∈ E G n . Then E G n ⊇ E Gn
Remark 3. In the proof of Theorem 17 we used the fact that equality, =, was part of the vocabulary. We dont know yet whether the theorem remains true without this requirement.

Remark 4. Yannakakis [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF] proved that the evaluation of acyclic conjunctive queries is possible in polynomial time (and therefore tractable both in the classical sense of combined complexity and fixed-parameter tractable). This does not contradict Corollaries 19 and 16 because the class of acyclic conjunctive queries is not of the form CQ(C) for a class of graphs. However, the underlying graph of a conjunctive query whose vocabulary contains at most k-ary relation symbols, for a k ≥ 2, has tree-width at most k -1. Thus in particular, if the vocabulary is fixed, acyclic conjunctive queries have tree-width bounded by the arity of the vocabulary.

Remark 5. A conjunctive query with negation is a formula of the form ∃x1 . . . ∃x k λ1∧. . .∧λn), where the λi are atomic or negated atomic formulas. It is easy to see that our results extend to conjunctive queries with negation.

Towards First-Order Evaluation

Definition 3. A fragment L ⊆ FO is closed if it satisfies the following condition: If ϕ ∈ L, α is an atom in ϕ, and β a quantifier-free formula with var(α) = var(β), then the formula ϕ obtained from ϕ by replacing α by β is also contained in L.

The motivation for this definition is that closed classes of first-order formuls somehow resemble classes of conjuctive queries of the form CQ(C) for a class C of graphs. There is no direct formal correspondence between the two notions, though, because we have to admit negated atoms here.)

Let L1, L2 ⊆ FO. We say that L1 is effectively contained in L2 (and write L1 ≤ eff L2) if there is an algorithm that computes, given a formula ϕ1 ∈ L1, an equivalent formula ϕ2 ∈ L2.

Theorem 20. Let L be a closed class of EFO-sentences that is recursively enumerable. Assume that FPT = W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF].

Then Parameterized L-Evaluation is in FPT if, and only if, there exists a k ≥ 1 such that L ≤ eff EFO k .

Proof: The backward direction is well-known.

To prove the forward direction, we assume that Parameterized L-evaluation is in FPT. Let ϕ ∈ L. By standard techniques we transform ϕ into a sentence ϕ in prenex normal form in which negation symbols only occur in front of atomic subformulas. In doing so, we may have to rename some of the variables, but we do not have to duplicate any atoms. In other words, there is a canonical way to associate an atom α of ϕ with every atom α of ϕ. Now we bring the quantifier-free part of ϕ into disjunctive normal form. Switching existential quantifiers and disjunctions, we obtain a formula ϕ of the form i∈I γ ϕ i , where the γ ϕ i are conjunctive queries with negation. If we do this in the straightforward way, ϕ and ϕ will have precisely the same set of atoms, but every atom of ϕ may occur several times in ϕ . Consider the class C of all graph G(γ ϕ i ), for all ϕ ∈ L. We claim that there is a parameterized m-reduction from Parameterized CQ(C)[{E}]-Evaluation to Parameterized L-Evaluation. To see this, let γ ∈ CQ(C) [{E}]. Then there is a formula ϕ ∈ L such that for some γ ϕ i occurring in ϕ we have G(γ ϕ i ) = G(γ). Because all the literals involve only binary relations, it is easy to see that we can replace the literals of γ ϕ i in a suitable way by a conjunction of atoms such that the resulting formula is γ; equivalently we can replace the atoms by quantifier-free formulas. We do the corresponding substitution in ϕ and replace all other literals of ϕ by a quantifier free formula that is not satisfiable (for example, a conjunction of atoms x = x). Thus in ϕ every γ ϕ j with j = i is replaced by an unsatisfiable formula and γ ϕ i is replaced by γ. Therefore the resulting formula γ is equivalent to γ. Now we go back from ϕ to ϕ. We get a formula γ equivalent to γ that can be obtained from ϕ by replacing atoms by quantifier-free formulas with the same variables. Since the fragment L is closed, γ is contained in L. Thus for every γ ∈ CQ(C) [{E}] there is an equivalent γ ∈ L, and since L is recursively enumerable and equivalence of conjunctive queries is decidable, such a γ can actually be computed. This proves our claim.

Since we assumed Parameterized L-Evaluation to be fixed-parameter tractable, by Theorem 19 the class C has bounded tree-width, say w. Now we apply a result of Kolaitis and Vardi [START_REF] Ph | Conjunctive-query containment and constraint satisfaction[END_REF] saying that every conjunctive query of tree-width at most w can be effectively translated into an equivalent EFO w+1 -formula. (Actually, we use an extension of this theorem for conjunctive queries with negation.) Thus all the γ ϕ i are equivalent to EFO w+1 -sentences. This implies that ϕ and thus ϕ is equivalent to an EFO w+1formula. Furthermore, our proof shows that the translation is effective. 2 Remark 6. The previous theorem can be extended to formulas with at most k free variables, but is clearly wrong for formulas with more than k free variables.

Conjecture 21. Assume that FPT = W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. Let L ⊆ FO be closed and recursively enumerable. Then Parameterized L-evaluation is in FPT if, and only if, there exists a k ≥ 1 such that L ≤ eff FO k .

The idea to prove the conjecture would be to use an analogue of Kolaitis and Vardi's results for FO, which is contained in [START_REF] Flum | Query evaluation via tree-decompositions[END_REF] (Theorem 5.29).

Conclusions

The results of this paper give a good understanding on when the evaluation of conjunctive queries becomes a tractable problem. The main contribution is to show that evaluating conjunctive queries is tractable for those queries that have a bounded tree-width structure (under the hypothesis that NP = PTIME and FPT = W [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]). Beyond conjunctive queries, it was known that for each k, FO k could be evaluated in PTIME and in FPT. The second contribution of the paper is to propose a converse of this: Tractability of query evaluation implies an expressive power limited by the number of variables. This is formalized in conjecture 21, which we could prove only for the existential fragment of FO. A third contribution of independent interest, is that colored grid homomorphism problem is NP-complete and, if parameterized by the grid size, W[1]-complete.

  Figure 1(b)). It is easy to verify that hn ∈ HOM(Sn, Pn+1).

Lemma 6 .

 6 HOM(Sn, Pn+1) = {hn}.Proof: Let h : Sn → Pn+1 be an arbitrary homomorphism. We shall prove that h = hn. Let i1 := h((1, 1)). Then i1 ∈ C P n+1 1

Lemma 7 . 1 )

 71 HOM(Sn, Sn) = HOM(S n , S n ).Proof: HOM(S n , S n ) ⊆ HOM(Sn, Sn) is trivial. To see the converse, let g : Sn → Sn be a homomorphism. Then for all a ∈ Sn we have col S n (g(a)) = hn(g(a)) = hn(a) = col S n (a), since hn • g = hn by Lemma 6. 2 Proof (of Lemma 5): By the previous lemma, it suffices to show that HOM(S n , S n ) = {id}. So let h ∈ HOM(S n , S n ). We will repeatedly use the following observation, holding for all a, b ∈ S n : d S n (a, b) ≥ d S n (h(a), h(b)) (We have h((1, 1)) = (1, 1) and h((n, n)) = (n, n), because (1, 1) and (n, n) are the only vertices of their respective colors. Now we consider the vertices (n, 1) and (1, n). Since they are the only vertices a ∈ C S n 2 with d S n ((1, 1), a) ≤ n-1 and d S n ((n, n), a) ≤ n -1, we have h((n, 1)), h((1, n)) ∈ {(n, 1), (1, n)}. Remember that (4, 1) ∈ C S n 2 , and note that d S n ((1, 1), (4, 1)) = 3 and d S n ((n, 1), (4, 1)) = n -4. Since there is no a ∈ C S n 2 with d S n ((1, 1), a) ≤ 3, d S n ((1, n), a) ≤ n -4, we must have h((n, 1)) = (n, 1). Similarly, since there

Theorem 11 .

 11 Let c ≥ 2. Then c-Grid Homomorphism is NP-complete. Furthermore, Parameterized c-Grid Homomorphism is W[1]-complete. Directed grids. Let DGrid denote the class of all directed graphs whose underlying graph is a square grid. We show how our proof can be modified to prove NP-completeness of DGrid-Homomorphism and W[1]-completeness of its parameterized version. Lemma 12. Let D be a directed acyclic graph with a directed Hamiltonian path. Then HOM(D, D) = {id}. Proof: Let H be a Hamiltonian path of D. Define a linear order ≤ on D by letting a ≤ b if, and only if, a occurs before b on H. Suppose that h : D → D is not the identity. Then there exist a, b ∈ D such that a ≤ b and h(b) < h(a). Then the interval of H that connects a with b must be mapped to a directed path from h(a) to h(b), which is impossible because D is acyclic. 2

( 1 )( 2 )

 12 ,n . We let C := {G n | n ≥ 1}. Recall Lemma 18. We shall prove that Parameterized Directed-C -Homomorphism ≤ fp m Parameterized CQ(C)[τ ]-Evaluation. For every n ≥ 1, we define a conjunctive query γn ∈ CQ(C) such that for every directed graph D we have: HOM(G n , D) = ∅ ⇐⇒ D |= γn.(2)Let Gn ∈ C be the graph, G n ⊆ Gn its connected component, and µn : Gn,n G n the minor map used to define G n .We choose a variable x b for every b ∈ Gn (such that x b = x b for b = b ) and define three sets of atoms:A1 := x b = x b (b, b ) ∈ E Gn , ∃a ∈ Gn,n : b, b ∈ µn(a) A2 := Ex b x b (b, b ) ∈ E Gn , ∃(a, a ) ∈ E G n : b ∈ µn(a), b ∈ µn(a ) A3 := x b = x b (b, b ) ∈ E Gn , b, b ∈ G n .Let x be a tuple that contains all the x b , A := A1 ∪ A2 ∪ A3 and γn := ∃x α∈A α.Note first that G(γn) = Gn, thus γn ∈ CQ(C). Now let D be a directed graph. To prove the forward direction of (2), assume that h : G n → D is a homomorphism. Then to see that D |= γn, for every a ∈ G n we interpret all variables x b with b ∈ µn(a) by h(a). For every connected component C of Gn \ G n , we pick one element c and interpret all x b with b ∈ C by c. Then all atoms in A1 and A3 are satisfied, and it can be easily checked that this is also the case for the atoms in A2. Conversely, suppose that D |= γn. Then by A1 and because µn(a) is connected in Gn, for every a ∈ G n there is a unique element d ∈ D that interprets all the x b with b ∈ µn(a). We let h(a) := d, then A2 guarantees that this gives us a homomorphism h : G n → D. 2 Corollary 19. Assume that FPT = W[1]. Let C be an arbitrary class of graphs and τ a vocabulary that contains at least one binary relation symbol. Then the following statements are equivalent: Parameterized CQ(C)-Evaluation is in FPT. Parameterized CQ(C)[τ ]-Evaluation is in FPT.

( 3 )

 3 CQ(C)-Evaluation is in PTIME.

( 4 )( 5 )

 45 CQ(C)[τ ]-Evaluation is in PTIME. C has bounded tree-width. Proof: The implications (3) ⇒ (4), (3) ⇒ (1), (4) ⇒ (2), and (1) ⇒ (2) are trivial. (5) ⇒ (3) by Theorem 14, and (2) ⇒ (5) by Theorem 17.

  In the following, τ always denotes a vocabulary. E always denotes a binary relation symbol and C1, C2, . . . denote unary relation symbols. A τ -structure A consists of a non-empty set A, called the universe of A, and a relation R A ⊆ A r for each r-ary relation symbol R ∈ τ . If G is a c-colored graph and a ∈ G we define the mapping col G : G → {1, . . . , c} by col G

	In this paper we only
	consider finite structures. If C is a class of structures, C[τ ]
	denotes the subclass of all τ -structures in C. If A is a τ -
	structure and B ⊆ A, then B A denotes the substructure
	induced by A on B, i.e. the τ -structure B with universe B
	and R B = R A ∩ B r for every r-ary R ∈ τ . A graph is
	an {E}-structure G = (G, E G ), where the binary relation
	E G is symmetric and anti-reflexive (i.e. graphs are undi-
	rected and loop-free). A directed graph is an {E}-structure
	D = (D, E D ), where E D is anti-reflexive. A c-colored graph,
	for a c ≥ 1, is an {E, C1, . . . , Cc}-structure G, where (G, E G )
	is a graph and C G 1 , . . . , C G c are disjoint sets (possibly empty)
	whose union is G.

  Definition 1. A parameterized problem P ⊆ Σ * × Π * is fixed-parameter tractable if there is a computable function f : Π * → N, a constant c ∈ N and an algorithm that, given (I, π) ∈ Σ * × Π * , decides if (I, π) ∈ P in time f (π)|I| c . FPT denote the class of all fixed-parameter tractable parameterized problems.

	Definition 2. Let P ⊆ Σ * × Π * and P ⊆ (Σ ) * × (Π ) * be
	parameterized problems.
	(1) A parameterized T-reduction from P to P is an al-
	gorithm with an oracle for P that solves any instance
	(x, y) of P in time f (|y|) • |x| c in such a way that for all
	questions "(x , y ) ∈ P ?" to the oracle we have |y | ≤
	g(|y|) (for computable functions f, g : N → N and a
	constant c ∈ N). P is fixed-parameter T-reducible to
	P (we write P ≤ fp T P ), if there is a parameterized
	T-reduction from P to P .
	(2) A parameterized m-reduction from P to P is an al-
	gorithm that computes for every instance (x, y) of P
	an instance (x , y ) of P in time f (|y|) • |x| c such that
	|y | ≤ g(|y|) and (x, y) ∈ P if, and only if, (x , y ) ∈ P
	(for computable functions f, g : N → N and a con-
	stant c ∈ N). P is fixed-parameter m-reducible to P
	(we write P ≤ fp m P ), if there is a parameterized m-
	reduction from P to P .

  be a class of structures. Then the following problem is fixed-parameter T-reducible to Parameterized C-Homomorphism.

Parameterized C-Homomorphism Construction Input: Structures A ∈ C and B. Parameter: ||A|| Problem: Decide if there is a homomorphism from A to B and, if this is the case, compute such a homomorphism. Proof: Given A ∈ C and B, we first check if there is a homomorphism from A to B. If this is not the case, we reject. Otherwise, if |B| ≤ |A| we can find a homomorphism from A to B by exhaustive search, the time this requires can be bounded by a function only depending on ||A||. If |B| > |A|, there is a b ∈ B such that there is a homomorphism from A to B \ {b} B . By simply testing all b, we can find such a b and remove it from B. We repeat this procedure until we arrive at a substructure B ⊆ B of size at most |A| such that there still is a homomorphism from A to B . Now we can find such a homomorphism by exhaustive search. 2 Corollary 3. If Parameterized C-Homomorphism is in FPT then Parameterized C-Homomorphism Construction is also in FPT. Remark 1. In problems like Parameterized C-Homomorphism, the class C is not necessarily computable. When we say that Parameterized C-Homomorphism is in FPT for a non-computable C, we mean that there is a computable function f : N → N, a constant c ≥ 1, and an algorithm that, given structures A and B, decides if there is a homomorphism from A to B in time f (||A||) • ||B|| c if A happens to be in C. If A ∈ C, the answer given by the algorithm may be wrong. (However, since f is computable we can always assume that the algorithm stops after g(||A||) • ||B|| c steps, for some computable function g.) Similarly, we can define what it means that Parameterized C-Homomorphism is W[1]-complete under parameterized m-reductions or parameterized T-reductions.

  class C of structures has bounded tree-width if there is a k such that tw(A) ≤ k for all A ∈ C. A minor of a graph G is a graph H that is obtained from a subgraph of G by contracting edges. Equivalently, H is a minor of G if there is a mapping µ : H → Pow(G) such that for all a ∈ H the subgraph µ(a) G is connected, and for all (a, b) ∈ E H there are a ∈ µ(a), b ∈ µ(b) such that (a , b ) ∈ E G . We call µ a minor map from H to G. We write H G to denote that H is a minor of G and µ : H G to denote that µ is a minor map from H to G. The connection between grids and tree-width is made by the following deep Excluded Grid Theorem:

Theorem 4

(Robertson and Seymour [12]

). Let C be a class of graphs. Then C has bounded tree-width if, and only if, there is a grid that is not a minor of any graph in C.

  3, 1), . . . , (n, n)

	Then it is an immediate consequence of Lemma 12 that
	Figure 2. The directed grid S d 8
	HOM(S d n , S d n ) = {id} for all n ≥ 1.
	We can now proceed completely analogously to the case of
	2-colored grids. For every k ≥ 2 and every undirected graph
	H we define a directed graph H d k and prove that H contains a k-clique if, and only if, there is a homomorphism from S d K to H d k . Moreover, we do this in such a way that, given H and k, S d K and H d k can be computed in polynomial time.
	Thus we obtain:
	Theorem 13. DGrid-Homomorphism is NP-complete.
	Furthermore, Parameterized DGrid-Homomorphism is
	W[1]-complete.

  Parameterized Directed C-Homomorphism. This even shows that Parameterized Directed-C-Homomorphism is W[1]-complete under parameterized m-reductions (for computable C). For every graph B and natural number k we define directed graphs A * k and B * k such that the underlying graph of A * k belongs to C and there is a homomorphism from A * k to B * k if, and only if, B has a kclique. Furthermore, we will do this in such a way that A * k only depends on k, the mapping k → A * k is computable, and B * k can be computed from (B, A * k ) in polynomial time. So let k ≥ 1 and

	[1]-complete under
	parameterized T-reductions:
	Parameterized Directed-C-Homomorphism
	Input: Directed graph A whose underlying
	graph is in C, directed graph B.
	Parameter: ||A||
	Problem: Decide if there is a homomorphism
	from A to B.
	Proof: Let us first assume that C is computable. We shall
	prove that
	Parameterized Clique
	≤ fp m

  9 that B contains a k-clique if, and only if, there is a homomorphism h : A * k → B * k . Moreover, it is easy to see that, given B and A * k , B * k can be computed in polynomial time. It remains to deal with non-computable classes C. For such classes, we can only prove that

	Parameterized Clique
	≤ fp

Acknowledgments

We thank Jörg Flum, Georg Gottlob and Victor Vianu for helpful discussions and comments.


Paul Lagneau-Ymonet

Angelo Riva
email: angeloriva@ebs-paris.com

ABOUT THE INCAS PROJECT

Keywords: Financial markets, Legal origin, Nineteenth century, Traded volumes, France

The aim of the proposed mobility scheme is to give birth to a European consortium and network of faculties and advanced graduate students specialized in the comparative analysis of institutional change in Asia and Europe. The partners have chosen Japan as a reference point because of its comparability with Europe as shown by previous studies, its historical influence on development and further institutional changes in Asia, and the expertise accumulated

Introduction

'Law and Finance' theory considers that civil-law countries have lower financial development than common-law countries, because of their weaker legal protection of corporate shareholders and creditors. Consequently, firms in civil-law countries have restricted access to external finance. This harms their performances and reinforces ownership concentration. [START_REF] Porta | The Economic Consequences of Legal Origins[END_REF] At the macro level, it contributes to lower economic growth. [START_REF] Levine ; Levine | The legal environment, banks[END_REF] Among civil-law countries, France scores poorly, because of the slower adaptation of its institutions to changing economic and business needs. [START_REF] Beck | Does the law and finance hypothesis pass the test of history?[END_REF] Not only do critics of the 'Law and Finance' approach highlight its ahistorical character, they also contest its main argument. In a recent special issue of this journal, the guest editors concluded that 'business history suggests that legal origins do not matter' 4 and formulated an ambitious research agenda. They called for research on the early development of stock markets in European civil-law economies, in order to document interactions between regulators and regulated as well as actual business practices, beyond formal rules. According to the finance and growth literature [START_REF] Levine | Stock Markets, Banks, and Economic Growth[END_REF] and historical studies on financial development, [START_REF] Navin | Historical perspectives on financial development and economic growth[END_REF] liquidity is more important than listing or market capitalization for economic growth: the higher the liquidity, the lower the risk premium that investors demand, and hence the lower the cost of capital for issuers and the higher the investment. Even though 'overtrading' is also crucial in the occurrence of manias, panics, and crashes, 7 scholars have often neglected trading volumes [START_REF] Rajan | The great reversals[END_REF] because of the difficulties in putting together historical series. Drawing on newly-available archival records, [START_REF] Lagneau-Ymonet | Nouvelles des archives. Aux sources de l'histoire sociale"; and Lagneau-Ymonet and Riva[END_REF] we contribute to the 'Law and Finance' debate by documenting a striking counter-example: the early development of the Paris Bourse, second only to London before the First World War. We provide original estimates of the traded volumes at the Paris Bourse at the turn of the 20th century. These volumes amounted to four times the French GDP. This magnitude was mainly due to forward trading, which was three times the size of GDP (counted on both sides). 10 Since its creation in 1724, the Bourse had been primarily a forward market, despite a ban on such operations until their legalization in 1885. We also document the key role played by the official Paris stockbrokers in the process that led from the legitimation to the legalization of forward operations that had long been equated with gambling. To do so, we bring to light the formal and informal rules and the actual practices through which forward contracts were negotiated. We then explain the disputed adaptation of these rules and practices to business needs and regulators' expectations by analyzing the organization of the Bourse and the guild running it, its rivalries with other financial intermediaries, and the dynamic power plays with judges and the government. By seeking to organize the fair ordering of trading through social control, institutional innovations, and legal strategies, the official stockbrokers built the legitimacy of forward operations and eventually obtained their full legal recognition. The process was disputed and non-linear. Nevertheless, the 1885 Act made possible the creation a new field of law -securities law (droit boursier) -that had been hindered by the controversies on forward operations. The first securities law passed in 1890 allowed further regulatory changes that culminated in the 1898 reform of the Paris financial center. This reform enhanced the transparency of financial transactions and supported the development of the number of listed securities. The reform also stabilized the Bourse by effectively dealing with counterparty risk and significantly decreased transaction costs. [START_REF]Histoire de la Bourse; Hautcoeur and Riva[END_REF] Consequently, traded volumes as a ratio of GDP reached heights similar to the 2006 level. The rest of the paper is structured as follows. The next section addresses the question of financial liquidity and stability in the specific context of the Paris Bourse and provides original estimates of traded volumes. Section 3 describes the legislation on forward operations and stockbrokers; it relates the pivotal role of the jurisprudence. The fourth section analyzes the stockbrokers' strategies to cope with the threats incurred by legal uncertainties. They raised their social status, strengthened the reliability of the organization of the Bourse and developed actions to shape the jurisprudence. Section five focuses on the 1885 law that legalized forward operations. The final section concludes.

Liquidity and Stability

At the end of the 19 th century, the tension between stability and liquidity of stock markets was the subject of intense debate in Europe. [START_REF] Neymarck | Organisation des marchés financiers[END_REF] Although liquidity was already considered a crucial quality of stock markets, frequent financial crises affected both the financing of the economy and personal wealth. In France, the debate focused on the legal status of forward operations. They were performed without deposit of securities and money and most of the transactions were settled by the payment of the difference between the transaction prices and the repurchase prices, with no actual delivery of the securities. [START_REF] Locré | Des marchés à terme. Études légale; Badon-Pascal La crise de la bourse; Courtois, Défense de l' agiotage; Déloison, Traité des valeurs mobilières; Buchère, Traité théorique et pratique des opérations[END_REF] Although they were the most common instruments for trading since the foundation of the Paris Bourse in 1724, forward operations were equated with gambling. Legislators refused to recognize them, but without forgoing their contribution to the development of the market, and more specifically to the issuance of public debt. This ambiguity is the main reason why judicial authorities did not strictly uphold forward operations, before their full legal recognition in 1885. Clients could therefore trade with no risk and endanger the solvency of their brokers: if they won, they cashed in; when they lost, they could refuse to pay. This amplified the systemic risk, as exemplified in 1882 by the collapse of the Lyon Bourse (the second largest French exchange) and the bail-out of the Paris Bourse. [START_REF] Riva | Danger on the Exchange"; and White[END_REF] Defaulting clients could be kicked out of the Bourse by the official brokers, but a thriving over-the-counter (OTC) market in Paris as well as six regional exchanges in the country mitigated this threat. This pressure from rival intermediaries, fueled by the push for a greater market depth by large market participants, combined with the greed of the official stockbrokers to explain the role they played in manias, panics, and crashes throughout the century.

According to Banner, [START_REF] Banner | [END_REF] at the very beginning of the 19 th century, forward trading exceeded the volume of cash transactions by a factor of 10. In the 1830s, the ratio was 1 to 50. [START_REF] Vincens | Exposition raisonnée de la législation commerciale[END_REF] Fresh archival records provide more accurate estimates for the end of the century. Fig. 1 compares two series: the volumes of spot transactions handled by the clearing house of the Bourse, and the volumes of forward transactions settled through the actual delivery of securities. Available archival data for 1906 gives us an insight into the magnitude of the phenomenon captured by these series. 17 Only 11% of the forward volumes ended with the actual delivery of securities; that same year, around 80% of the spot transactions were recorded by the clearing house. These data confirm secondary sources indicating that forward operations settled through the actual delivery of securities were residual. Nevertheless, delivered forward-traded securities multiplied by four between 1877 and 1881. Under the assumption that these proportions did not vary from the 1870s to the dawn of the 20 th century, forward-traded volumes in 1881 amounted to five times the French GDP. After the 1882 crash, volumes stagnated until 1887.

Then they followed an upward trend until the First World War. Spot transactions followed a similar trend, although they only accounted for 0.7% of the GDP in 1881.

Fig. 2 Traded volumes in Paris (as a ratio of French GDP, transactions counted on both sides)

Source: see Data Appendix

Institutional Threats to Forward Trading

The official brokers had unlimited liability for the completion of the transactions they performed under their legal monopoly. Despite the ban on forward operations, they expanded this unlimited liability to the latter.

Meeting regulators' expectations and containing competition from the OTC market explain this decision.

However, the discrepancy between the legal framework and the actual business practices attributed a pivotal role to the judges. The Bourse's president described this situation as a 'Sword of Damocles' . 20

The legal ban on forward operations

The ban on forward operations appeared in the decree (September 24, 1724) that had instituted the Paris Bourse, in the aftermath of the collapse of Law's system. For similar reasons -restraining 'speculation' and the disorders it caused among the Parisian business community -, the ban was re-enacted by decree on October 2, 1786. Forward operations were deemed fictitious, and hence illegal, unless the transactions were settled within two months by the actual delivery of the securities that the seller was obliged to possess when the contract was made. During the French Revolution, manipulations were so severe that the Bourse was officially closed and forward traders could be fined, pilloried and jailed.

The Napoleonic codes did not directly address forward operations. The preliminary works to the 1804 Civil Code indicate that the lawmakers were still marked by the financial disorders of the Revolution. Therefore, anti-speculative views prevailed, as stated in the Law of October 12, 1795 on the police of the Bourse and in the decree of June 16, 1802 on exchanges. [START_REF] Locré | La législation civile, commerciale et criminelle[END_REF] Risk could be the object of a contract (e.g., an insurance contract), but the Civil Code did not recognize uncertainty as a 'serious cause' for contracting. Uncertainty-based contracts -and forward contracts were deemed such -were therefore equated with bets and gambling was not given any legal protection (art. 1965, on the so-called 'exception de jeu [the bet exception]').

The 1805 financial crisis and economic downturn had caused the default of at least 10 stockbrokers and hence increased government mistrust. Consequently, the draft of Commercial Code was revised, in order to 'moralize' finance through specific rules for stockbrokers. [START_REF]Regnaud de Saint-Jean d' Angély[END_REF] Yet the 1807 Code of Commerce only devotes 17 articles to them and three to the organization of stock exchanges. If strictly interpreted by judges, these rules would have prevented stockbrokers from carrying out forward operations without the prior deposit of securities and cash. For instance article 85, paragraph 3 prohibited them from granting credit to their clients. Most importantly, there was no specific rule in the Code on securities trading. Article 90 only mentioned that securities trading would be regulated by pending governmental regulation. Precisely because of the issue of forwarding operations, this regulation was only passed in 1890, after their legalization. The silence of the law had two crucial consequences: on the one hand, judges were free to base their decisions on the prohibitions decreed by the Ancien Régime; on the other hand, the organization of trading activities relied on the offi cial stockbro-; on the other hand, the organization of trading activities relied on the official stockbrokers, without their rules having been recognized by the government as required by law. Courts judged them as private rules.

In 1809, Reynier's infamous bankruptcy discredited the Bourse and its intermediaries in general: his forward operations on French public bonds amounted to 1,305,000 francs (about 2% of all the public debt), forcing 19 stockbrokers out of business. This affair profoundly shaped the rules on financial transactions, which were added in the 1810 Penal code: 23 articles 419, 421 and 422 equated the forward sale of public bonds without previous deposit with forbidden betting, punishable by a custodial sentence and a heavy fine. Until the 1885 law, the legal framework remained unchanged: it was pretty hostile to forward operations, with room for judicial interpretations according to the circumstances, in particular to tame the market through its official intermediaries. 24

The contested monopoly of the agents de change

The financial intermediation from the Ancien Régime survived the French revolution as a contested mo-survived the French revolution as a contested monopoly granted by the government to a guild of appointed merchants. The Le Chapelier Law (June 14-17, 1791) banned guilds and unions, and proclaimed free enterprise. Consequently, brokerage was liberalized.

But the financial disorders of the last decade of the century were so intense that the public authorities soon restored a legal monopoly, based on that of the pre-revolutionary era, for financial intermediation, as they did for other activities: [START_REF] Kaplan | La France malade du corporatisme[END_REF] the only persons entitled to perform financial intermediation were the agents de change, pure stockbrokers appointed by the Ministry of Finance (officiers ministériels), holders of an office. The organizational features of the system of office were restored as a governmental device of financial intermediation. 26 Article 76 of the 1807 Code of Commerce broadly defined their monopoly, to cover the trading of 'public bonds and other securities that can be quoted [effets publics et autres susceptibles d' être cotés]' . In addition to the hybrid status there was a numerus clausus: no more than 60 official stockbrokers would be entitled to organize the Bourse through a guild-like body: the Compagnie des Agents de Change, with its peer-elected governing body, the Chambre Syndicale, chaired by a president, the Syndic. The setting of the Bourse also reenacted pre-revolutionary rules and it demonstrated the agents' dual role (facilitating transactions and participating in their control): they should operate in public, in a restricted area, in the middle of the Exchange building, with the open outcry as price-discovery mechanism and fixed commissions as payment.

Each stockbroker was legally bound to engage his unlimited liability for the transactions carried out under their monopoly: the "faits de charge". Failure to fulfill this obligation exposed brokers to fraudulent bankruptcy (punishable by forced labor). The legal liability did not encompass forward operations insofar as the law did not recognize them. Nevertheless, the individual interest of each stockbroker in preserving his reputation and their collective interest in satisfying the expectations of the public authorities (market reliability), in order to keep their monopoly as large as possible, prompted the agents to extend their individual and collective guarantee to these operations: the net debts of one had to be paid by his fellows. Refusal would have opened the door to their long-time rivals: the coulissiers.

In parallel to the Bourse, informal intermediaries (coulissiers) had developed an OTC-like market (coulisse).

They traded unlisted securities and performed operations forbidden by the rules of the Bourse. The coulissiers also competed in the core activity of the agents de change: forward operations on large issues of bonds (often public and/or foreign). This competition enhanced the institutionalization of the Bourse through a process of differentiation from the OTC market, leading to a beneficial complementarity. 27 Therefore, legal proceedings against the coulissiers were exceptional, even though the latter always lost (e.g., the highly publicized 1859 trial). The government informally favored retaliation solely in the case of durable bearish speculation by the coulissiers on public bonds, while it appreciated their activity when they contributed to the success of public bond issues and the international strength of the financial center. [START_REF] Hautcoeur | How to regulate a financial market[END_REF] Agents only sued when the coulissiers' market share threatened their profitability. On these occasions, the legal status of forward operations was part of the jurisdictional dispute: since the legal bans only mentioned the agents, the coulissiers argued that forward operations were only prohibited for them because of their specific legal status. On the contrary, the agents promoted the largest possible definition of their monopoly, including all securities, whether traded on spot or through forward operations. This exposed them to greater potential losses.

To extend the guarantees to clients and expand the business, the agents de change organized partnerships with wealthy associates. Because only an individual could be holder of an office, the legality of the partnerships and the nature of the associates' liability were also matters of legal debate. In 1862, after a long and disputed process of legal drafting, the agents obtained from the government the introduction into the French Commercial

Code of a specific corporate form exclusively for their partnerships, based on the société en commandite (art 75, modified by the law of July 2 nd 1862): each agent became the only unlimited liable general partner while the other associates in the firm would act as limited partners.

The dynamics of the jurisprudence

The discrepancy between the legal framework and business practices endowed judges with a role of pivotal importance. The stockbrokers adapted their practices to the judges' expectations and the lobbying and litigations of the former influenced the latter. Regime changes also catalyzed the jurisprudence of forward operations. By demonstrating their legitimism to each new ruler who badly needed to tap into the domestic capital market, the agents gained recognition of the business they performed. Moreover, individual savings gradually became dependent on financial markets, if not invested in often unaffordable real-estate. Therefore, financial turmoil could affect the support of the bourgeois for the rulers, giving them good reason to consider financial regulation as a matter of 'public order' .

Until 1805, the courts of justice refused to uphold forward operations, but the financial turmoil of that year provoked a first reversal in the jurisprudence. To make the business community pay for the disorder its speculation had provoked, and drawing on the 1786 decree, the judges upheld forward contracts, even those without the actual delivery of the securities, provided their duration was no longer than two months and provided the agents had operated in a suitable manner (including a discount clause in the contract). [START_REF]The "clause d' escompte" allows the buyer to transform the forward operation into a cash operation by calling for[END_REF] This jurisprudence, which was quite favorable to the agents, lasted less than two decades: incapable of containing massive speculation on the Spanish debt, they suffered a complete jurisprudential reversal following the political hardening of the Restauration.

In Under the July Monarchy, the jurisprudence softened. The judges maintained the prohibition of forward operations without delivery, but they were more willing to uphold those settled by the actual delivery of the securities. The courts then introduced a further distinction, drawing on article 422 of the Penal Code, between forward sales, prohibited without prior deposit of securities even if settled by their delivery, and forward purchases without the prior deposit of cash. The latter were deemed licit, as long as the stockbrokers could prove the 'seriousness of the transaction' . They should demonstrate their bona fide in the appreciation of their clients' 'morality' and solvency, based on their social status, lifestyle and other proxies for wealth such as publicly-known real estate. This incremental change was abruptly stopped by the default of four agents, which in 1842 resulted in stockbroker Bagieu's criminal conviction for betting on public bonds.

After the 1848 Revolution, the courts decided that the Ancien Régime's ban was no longer applicable and developed less stringent interpretations of the current laws. For instance, payments and deliveries related to trading were exempt from the prohibition on stockbrokers from granting credit to their clients stated in In the early days of the Third Republic, most judges abandoned the valuation of the client's notability to focus exclusively on compliance with the rules of the Bourse. Nonetheless, when public bonds were at stake or if the case turned into a scandal, some judges still equated forward selling with gambling. In the aftermath of the 1882 crash, this minority view reversed the jurisprudence: many clients were unable to pay but others took advantage of the exception de jeu to repudiate their losses.

Making Forward Trading Legitimate

To cope with the 'sword of Damocles' represented by the institutional threats on forward operations, the agents first tried to make them legitimate, and thus upholdable by judges, as a precondition for their legalization by the legislators. To reach this goal, they developed three mutually reinforcing strategies. They gained a dominant position among the Parisian business elites, developed their market organization and advocated the legitimacy of serious business practices run by serious men in front of the judges.

The rise of the agents' status

The debates about speculation, and especially forward operations, gave competing dominant fractions of French society the opportunity to defend their interests and legitimate their positions. [START_REF] Charle | Les élites de la République[END_REF] The Bourse made it possible to imagine or even to achieve (although infrequently) a faster rhythm of capital accumulation, compared to the intergenerational rise in notability, based on land-ownership and, to a lesser extent, on commerce or production. This does not imply that notables did not trade financial instruments, or that financiers discarded property ownership. On the contrary, deals of all kinds intermingling old families and new money soon became commonplace. [START_REF] Bergeron | Ferragus, une 'sociologie-fiction' de la confiance"; and Reffait[END_REF] But, notables could still exploit the hostile legal framework, punctually repudiate their losses at the Bourse and, more generally, scorn the homines novi of the finance world. Reciprocally, financiers invested in real estate to diversify their wealth and secure their social status. As Louis Bergeron 33 pointed out, the French Revolution did not put money at the heart of the new social hierarchy, but private property instead.

Over the century, the stockbrokers' status varied dramatically. In 1801, when Bonaparte decided to restore official intermediation, a quarter of the newly appointed agents had been in charge before the Revolution.

Nicolas Mollien, Bonaparte's main financial advisor, deliberately favored experience, while he also compensated bankers' straw men and newcomers with political connections. 34 Favoring old ties was not sufficient:

among the first 115 agents, 4 committed suicide, 12 were officially dismissed, 30 were forced to resign, and 8 left for other occupations. To stabilize the group, the government granted the agents the right to designate their successors (decree of May 29, 1816), which would be first endorsed by the Chambre Syndicale, then approved by the general assembly of the Compagnie, and eventually appointed by the ministry of finance. Such a process gave the Chambre the upper hand in the selection process, it promoted peer-monitoring and it also lengthened the temporal horizon of the agents. They could build family-based strategies for the transmission of their business, rather than go bust trying to get rich too quickly.

Yet, stockbroking long remained poorly regarded, compared to the status of propriétaire or other lucrative occupations with higher standing. [START_REF] Daumard | La bourgeoisie parisienne[END_REF] In 1824, in the midst of the Forbin-Janson vs. Perdonnet case, the Chambre added personal wealth and family credentials as recruitment criteria. Therefore, candidates were expected to bring money, connections and prestige (especially among legal professions) to the guild. In doing so, the Chambre also set the conditions for a more integrated and integrative group, composed of self-elected individuals sharing a common ethos. This was made up of dispositions (obedience and reliability) and aspirations (social climbing into high society) reflecting the agents' singular position, between the raison d'Etat and market dynamics, within a collective endeavor, which both supported and constrained them. Between 1818 and 1859, about 25 % of the agents did not last more than 5 years. Nonetheless, over the rest of the century, turnover decreased while the family transmission of business increased. [START_REF] Hautcoeur | Les opérateurs du marché financier[END_REF] After its considerable rise under the Second Empire and its contribution to the financing of the war indemnity to Germany, a new aristocracy of financial wealth took over the Third Republic. Most agents were not part of this aristocracy dominated by bankers, industrialists and crony politicians, but stockbrokers had become legitimate, well-established members of the bourgeoisie (Tab. 1).

The building-up of an organization

The government of the Restauration, in need of a huge issue of public bonds, granted the Chambre Syndicale large regulatory powers and full arbitration and disciplinary powers over the stockbrokers with the decree (ordonnance) of May 29, 1816. The Chambre developed a reliable organization to cope with the threats inherent to stockbroking and to demonstrate the seriousness of the agents' business. Initially, despite its large regulatory and disciplinary powers, it had difficulty in monitoring the agents. They were willing neither to give up profit opportunities nor to hand the control of their business over to the group: in the aftermath of the 1823 crisis, six brokers defaulted. The ministry of Finance revoked the Chambre, and designated the stockbrokers who should form the new governing body. The new jurisprudence of the Perdonnet vs. Forbin Janson case was the punishment for the brokers' defaults and the Chambre's lack of due diligence in monitoring them.

In making such an example, the ministry signaled that stability was not optional; it was the only way for the agents to preserve their monopoly. This triggered a rationalization of trading, clearing and settlement on the one hand, and close monitoring of the brokers by the Chambre on the other.

For each security, the first forward price of the day was established by comparing all the orders received since the close of the previous session. Then, the agents performed an open-outcry continuous auction around a pit.

They standardized the types of orders, the clauses attached and the back-office procedures. 37 They published a daily list of forward prices, even though the legal status of these transactions had not changed, and hence conferred more transparency. In 1844, building on the growing support of the bankers and the ministry of finance, who had considered the criminal conviction of the stockbroker Bagieu in 1842 to be detrimental to the business community at large, [START_REF]Chambre Syndicale des Agents de Change de Paris[END_REF] the agents obtained the informal authorization to publish the forward prices on the official list, previously devoted exclusively to spot prices.

To ensure reliability, transparency was not enough: clearing and settlement were crucial. The latter reassured the clients and its regularity was one of the best ways to demonstrate the agents' professionalism and the seriousness of their operations. From 1808 onward, the process always gave clients the possibility of actual delivery of securities. Monthly bilateral and decentralized clearing (liquidation générale) was reformed in 1808, after the Banque de France threatened to close the agents' accounts because of messy transfers and lack of controls. The Chambre then implemented the central clearing: each agent should clear his clients' accounts and then at a fixed date, all agents netted their residual balances, on a bilateral basis. By 1834, the procedure was reliable enough to be quoted in example by the Member of Parliament and former stockbroker Baillot to counter a proposition to renew and enforce the ban on forward operations; in 1836, the Banque de France agreed to combine the calendar of its monthly operations with the agents' central clearing and settlement.

A decade later, the agents were confident enough in their bookkeeping and in the group they constituted to adopt multilateral clearing: from 1843 on, each of them only established his netted position vis-à-vis the others. After 1848, the clearing and settlement of the Bourse helped to convince the judges that forward operations were not gambling.

Last but not least, the common fund soon became the organizational centerpiece to cope with defaults and subsequent counterparty risk, [START_REF] Riva | Danger on the Exchange[END_REF] demonstrate the reliability of the Bourse and cement the cohesion between agents. Created in 1818, as a sinking fund to reimburse debts collectively contracted in the event of a crash, the fund was perpetuated 4 years later. Individual contributions proportionate to each agent's turnover provided the Chambre Syndicale with discretionary resources to help distressed agents [START_REF] Often | the syndic demanded a backdated letter of resignations that allowed the Chambre to take full control of the broker's firm. 41[END_REF] and to cover the losses in case of defaults. The fund was first used as a liquidity and bail-out facility, during the 1830 Revolution. It was indeed a powerful instrument, especially as a means to obtain political support in times of financial and political crisis. Again in 1848, the revolution provoked a deep financial crash; thanks to the common funds, the heavy losses brokers suffered were settled without losses for their clients; by absorbing huge losses, the agents could gain and maintain the support of the new regime and benefit from the judges' benevolence. The common fund acted not only as a central counterparty, but also as the cornerstone of the voluntary collective guarantee of the Compagnie des Agents de change on the Bourse's transactions. The wealth of the agents and their families as well as their borrowing capacity could be mobilized through the fund, as happened in many crises.

In the 1830s, the Chambre Syndicale started the regular biannual control of brokers' standardized accounting. It also carried out one-off controls when the forward positions of a broker observed around the pit were deemed dangerous. As an arbitrator acting as a commercial court for exchange contracts, the Chambre systematically gave satisfaction to the clients against brokers when the disputed operations did not exactly respect the rules of the Bourse. This was a way to avoid lawsuits that could be lost in the courts. As a disciplinary body, the Chambre took care of the orderly functioning of the market by punishing stockbrokers who did not abide by the trading rules.

Despite fierce debate among agents, not always willing to support the monetary and regulatory burdens, the Chambre Syndicale developed these kinds of interventions. They were a powerful means of legitimation, especially in time of crisis. Despite some adjustments, like the introduction of bi-monthly settlement and delivery for the more volatile securities to reduce counterparty risk, this setting remained stable until the beginning of the 1890s: after the 1885 legalization, the securities law promised by article 90 of the 1807 Commercial Code was passed and the internal rules of the Bourse subsequently reformed.

The making of the jurisprudence

Over the first decades of the 19 th century, the Chambre tried to align the jurisprudence, its internal rules and the agents' actual business practices, incrementally adjusting each one to fit the others. 'Sirs, it is of the utmost importance for the Compagnie', argued the Syndic in 1833, 'to see a wise and enlightened jurisprudence being formed on all the topics related to our profession, in order to replace, as far as possible, the rules promised to us by Article 90 of the Commercial Code '. 41 To this end, the Chambre centralized the litigation opposing the agents and their clients, by imposing its formal authorization for any legal action taken by an agent against his clients. Starting in 1820, the measure was opposed by most agents, since it could be detrimental to their individual interests, but as they learned through the Forbin-Janson scandal, such selection could also protect the group from bad publicity and harsh reversals. Most importantly, it only brought before the courts those cases that were favorable to and winnable for the agents. After 1823, "the Chambre Syndicale always took the greatest care that judges only had to rule on indisputably clear-cut cases in favor of the official stockbrokers". 42 Because of its position and its constant exchanges with legal scholars, lawyers, judges and policy-makers, the governing body of the guild was in a better position than its members to appreciate their chances of winning cases. If not, agents were 'invited' (an understatement) to settle their disputes either bilaterally or with the Chambre as arbitrator. By these means, the Chambre also put pressure on recalcitrant agents to select their clients and give them credit according to their notability and wealth (following the judges' expectations).

In exchange, the agents could count on being advised and defended by leading lawyers, paid by the common fund as long their cases were of common interest for the group. Moreover, the Chambre archived all the documents related to financial law and jurisprudence, as well as the notes and files exchanged with lawyers, judges and politicians. This cumulative knowledge and experience helped to support cases, whether brought to court or privately settled.

The Chambre also tried, as far as possible, to keep the legal disputes within the jurisdiction of the capital.

Provincial courts and judges were generally less favorable to brokers, as in 1882. In Paris, judges were more familiar with stock-exchange transactions and more easily lobbied. Members of the Chambre frequently paid social visits to judges. Moreover, after the Revolution of July 1830, former legal counsels of the Chambre were appointed to the "most prestigious positions in the courts of the capital". 43 Last but not least, agents and judges rubbed shoulders professionally and socially. As the agents' status rose due to its recruitment policy, the Chambre Syndicale could also count on the brokers' individual (family) connections and their ascending collective prestige.

The effectiveness of this tactic can be appreciated by comparing the decisions obtained by the agents with those obtained by the coulissiers when suing clients refusing to pay for their failed forward operations. The analysis of 150 decisions indexed by legal scholar Edouard Badon-Pascal between 1857 and 1877 clearly confirms the judges' bias in favor of the agents. [START_REF] Badon-Pascal | Des marchés à terme[END_REF] The 1866 crisis also illustrates the power gained by the guild to prevent legal actions. 7 agents were in distress, 5 had been forced to sell their businesses, mainly because of faithless clients. 45 The Minister for Finance and banker Achille Fould protected the Compagnie from regulatory backlash by setting up a commission, chaired by the governor of the Banque de France. This commission emphasized the liquidity provided by forward operations and the stabilization of the Bourse that would come from their legal recognition. The Syndic declared that 'the report matches our views and desires so well that it could not have been better for us if the most enlightened of our legal advisors had drafted it' . 46 In parallel, the imperial prosecutor hampered the cases brought to the courts against insolvent agents, and judges of the Paris courts 'showed a kindness and zeal in rejecting demands for declarations of bankruptcy, which could have made people question their impartiality' . 47 Obtaining a four-month moratorium, the Chambre privately settled most of the disputes with insolvent agents' creditors and debtors.

The Legalization of Forward Operations

The 1882 crash ravaged the French stock exchanges, after a decade of numerous large issues (to pay the war indemnity to Germany and later to fund infrastructures), supported by the development of banks draining their customers' money from throughout the country. The Union Générale, founded in 1878 in Lyon, fearlessly competed with the main financial institutions in France, especially the house of Rothschild, and quickly became a systemic financial institution with a network of interlocking banks. [START_REF] White | The Crash of 1882[END_REF] To sell securities and obtain deposits, it successfully targeted ultramontane and Catholic conservatives through anti-Semitic and nationalistic arguments. This social group was particularly frustrated by the empowerment of the Third Republic and considered the Union Générale as a vehicle of political revenge. The competition was fierce, bribed newspapers fueled the bullish market and attracted many lay people. It became ever more difficult for the agents to refuse the execution of all the forward orders that professional clients transmitted. Once again, they accused the stockbrokers and their monopoly of hindering the growth of the market. 49 In January 1882, after frauds and market manipulations, the Union Générale went bankrupt, triggering the most severe crash ever in Paris. [START_REF] Bris | Les krachs boursiers en France"; and Bouvier[END_REF] Investors of all kinds were unable or unwilling to pay; 14 out of 60 agents became insolvent. The losses amounted 140 million francs (0.6% of French GDP in 1881). The common fund could not absorb such a sum but the agents raised 60 million francs among their partners and relatives, reimbursed by November 1882, while the Chambre contracted an 80 million franc loan from the Banque de France on behalf of the guild, reimbursed in a few weeks. Six agents reimbursed their debts by the beginning of February; of the eight others, five were insolvent mainly because of Union Générale-related debts. Nonetheless, the Compagnie overcame the liquidity crisis, met their obligations and no clients suffered any losses due to defaulting agents. In 1882, the Chambre authorized the agents to sue 151 clients to demonstrate their bad faith. But judges, particularly in regional courts, often ruled against the prevailing tolerant jurisprudence, in an uncoordinated reaction to the collapse of the stock market. Judges made null and void forward contracts for 117 million francs, i.e., 84% of the agents' total losses. 51 The crash of 1882 and its aftermath constituted a critical moment, offering the Compagnie and the Paris Chamber of Commerce, together with legal professionals, economists and politicians in tune with financiers, the opportunity to push decisively for the legal recognition of forward operations. On the one hand, it was clear that forward trading was crucial for liquidity and thus for the development of the market; on the other hand, the legal status of forward operations was for many investors an incentive to trade without risk, since the jurisprudence was not a sufficient threat for faithless clients. It was no longer possible to leave the liabilities of forward contracts exclusively on the agents' shoulders.

A few days after the crash, the Member of Parliament Alfred Naquet proposed the full legalization of forward contracts. 52 The Chamber of Commerce immediately endorsed Naquet's proposal. 53 The Minister of Justice

Gustave Humbert set up an extra-parliamentary commission 'to examine the modifications to be introduced into the legislation relating to the companies and the trading of securities' (decree of February 14, 1882).

Among its 17 members, the agents de change were represented by Syndic Moreau, their colleague Lecomte, and a former agent, Girod, who was at that time director of the Comptoir d'Escompte, a prominent French bank. The lawyer and senator Bozerian chaired the commission and the Chambre immediately appointed him as counsel. 54 It also paid good money to a syndicate of newspapers, including Le Voltaire, which published Naquet's op-eds, to influence public opinion. 55 In June, the government transmitted the extra-parliamentary commission's report to Parliament, with an explanatory memorandum by well-known jurist and law professor Lyon-Caen, the commission's rapporteur. [START_REF] Acd | parliamentary documents[END_REF] It recommended the legalization of all forward contracts and suggested only restricting the 'exception de jeu' to transactions in which the counterparties had formally agreed in advance not to deliver the underlying securities or commodities, a contract impossible at the Bourse.

In Parliament, Naquet defended his proposal of complete legalization of forward operations, drawing on comparative law, an informed description of the professional practices and emerging economics, including Pierre-Joseph Proudhon's analysis of speculation. [START_REF] Acd | Quand Pierre-Joseph Proudhon découvre[END_REF] He insisted on the 'serious elements of appreciation' and 'profound calculations' required by forward operations, but argued against any protection for laypeople reckless enough to risk their money. Parliament voted for Naquet's proposal; the Senate, more conservative, only endorsed the suggestion made by the commission. The topic then lost momentum: the crash had been overcome, and Naquet abandoned the subject. He resigned from Parliament to become a senator and fight for his signature piece of legislation: the 1884 reintroduction of divorce. Nonetheless, the law was adopted without further discussion and eventually published in the Official Journal on April 8, 1885. Drawing on this law, the Cour de Cassation also clarified in the same year the agents' and coulissiers' jurisdictions: the monopoly of the former would be limited to listed securities, while the coulissiers gained the right to trade the others. However, this dispute would only be settled by the fiscal upholding of the agents' monopoly in 1898. Again in 1898, the Cour de Cassation eventually ruled against the 'exception de jeu' , even when parties had a priori agreed not to deliver anything, a type of transaction frequent among coulissiers.

The 1885 law definitely reallocated the risk inherent to forward operations, shifting it from the stockbrokers to their clients. It paved the way for a new stream of financial regulation: securities law ('droit boursier'). 58 In 1890, the government passed the decree on securities trading announced in the 1807 Commercial Code and two years later, it approved the agents' revised rulebook. In other words, the agents' private arrangement was given legal force. This institutional setting allowed for further regulatory changes, crowned by the reforms of the French financial markets in 1898. 59

Conclusion

This paper documents the fact that at the turn of the 20 th century, the Paris Bourse was a very liquid market, contrary to the expectations of 'law and finance' literature. Overall traded volumes amounted to four times the French GDP, a ratio similar to the Paris Stock Exchange at the turn of the 21 st century. These volumes were mainly due to forward trading, which was three times as large as French GDP. Taken together, the Paris Bourse and the OTC market traded more than six times the GDP.

Throughout the 19 th century, the Bourse had been primarily a forward market, despite a ban on these op- By keeping constant the proportion between forward and spot transactions registered in 1906, we estimate the forward traded volumes over the period 1898-1907. Despite the potential bias of the 1906 data and the assumptions, these estimates give a good idea of the magnitude of the traded volumes.

Fig. 1

 1 Fig. 1 Cleared spot transactions and settled forward transactions at the Paris Bourse, 1872-1912 (in billions of current francs)

Fig. 2

 2 Fig. 2 depicts series obtained by the interpolation of 1906 archival data with financial transaction tax data for the Paris Bourse and its OTC market over a period when the rates of taxation were constant. 18 It indicates that between 1899 and 1906, the Paris financial center traded about six times the value of French GDP, with the

  1823, five of them went bankrupt. In an official extraordinary hearing chaired by the Minister of Justice, the Court of Appeal of Paris fixed the new jurisprudence (August 9, 1823): the agent Perdonnet lost against Forbin-Janson, his aristocratic and rich debtor. Although the court explicitly recognized the felony of the latter, it refused to uphold the forward contracts. The verdict was confirmed by the Cour de Cassation, the highest French Court (August 11, 1824). Neither the 1824 petition signed by prominent Parisian bankers, nor the plea by the banker and Member of the Parliament Casimir Périer (February 27, 1826) could modify it.

  art. 85, § 3 of the Commercial Code. Forward operations were upholdable if deemed 'serious' , independently from the actual delivery of securities. Evidence accepted by the judges still included the notability of the client (social status and real-estate property) relative to the value of the transactions, and the agents' due diligence with respect to Bourse rules. This change was also eased by the replacement of judge Séguier as first President of the Paris Court (1810-48), notoriously opposed to financial practices he considered speculative, by judge Troplong (1848-52), a close ally of Louis-Napoléon Bonaparte. According to Troplong, financial activities should be promoted, given their contribution to the development of new industries, especially railways. 30 In 1860 and 1868, the Cour de Cassation (under the Troplong presidency) endorsed this jurisprudence.

Tab. 1 :

 1 Changing social characteristics of the Paris agents de change in percentage (1810-1914) Sources: Personal files; Charle (1987); Verley (2007).

  erations until their legalization in 1885. Through private contracting and collective actions, the official Paris stockbrokers played a key role in legitimizing and eventually legalizing these operations. Because of the ban on forward operations, the liabilities linked to their contested monopoly and the jurisprudence, the agents de change sought to organize the fair ordering of trading through social control, institutional innovations, and legal strategies.Jurisprudence appears to have been adaptive enough to support the development of the market. Nonetheless, the 1882 crisis showed the limits of market regulation centered exclusively on supervising the behavior of brokers. Without legalizing forward transactions, the only way to stabilize the market would have been to sacrifice liquidity.The 1885 act paved the way for the 1890 securities law and thus opened a new field of law. This in turn allowed for further regulatory changes that culminated in the 1898 reform of the Paris financial center. This reform enhanced the transparency of financial transactions and supported the development of the number of listed securities. The reform also stabilized the Bourse by effectively dealing with counterparty risk and significantly decreased transaction costs. This development of securities law and its consequences on the actual functioning of the market made the 'Belle Époque' of the Paris Bourse possible.8. Data AppendixData plotted on Fig.1and Fig. 2 come from the DFIH (Data for Financial History) database, based at the Paris School of Economics (for these series, credits: Angelo Riva). 60 Data from Fig. 1 come from the annual reports of the Chambre Syndicale, presented to the end-of-the-year General Assembly of the Compagnie des Agents de Change. They measure transactions counted on one side. Data from Fig. 2 are obtained by the interpolation of detailed archival data for 1906 with data on the financial transaction tax (FTT). 1906 archival data 61 are the base of our estimates and come from a survey by the Ministry of Finance to assess the effects of the FTT in view of a reform of its rates. The Ministry of Finance conducted a detailed survey of the accounting books of 12 stockbrokers at the beginning of 1907. The accounting books of each broker were analyzed for a month in 1906 (the accounting books of broker A were analyzed for January, of broker B for February and so forth). The Ministry then summed up the registered transactions and multiplied by 70 (the total number of stockbrokers at that time) to obtain the total volumes traded in 1906, split into the different types of operations. As a consequence, traded volumes are counted on both sides. Moreover, the 1906 data are sensitive to the choice of the 12 brokers. Despite the mechanisms to control price-competition, 62 trading activity was not equally distributed among brokers. 63 Because of the close relationships between the Ministry of Finance and the Chambre Syndicale, whose members regularly checked the agents' accounts, we can assume that the Ministry selected 12 representative brokers to avoid potential bias in the estimates, as far as possible.In 1893, the French government introduced an FTT, and each month up until 1907 it published, in the Bulletin de Statistique et Législation Comparées, the amounts paid by the operators of both the Bourse and the OTC market in Paris. It is hard to use the tax revenues to estimate traded volumes because tax rates varied according to the types of operations (repo vs. others) and securities (French public bonds vs. others). Nevertheless, the 1906 data allow for an interpolation with the FTT data over a period where the rates of the tax are kept constant. Thanks to this interpolation we obtain the estimates of the total volumes traded on both markets.

INCAS is a Marie Skłodowska-Curie Actions R.I.S.E funded project under the European Commission's H2020 Programme.

The project INCAS aims at creating a top-level research and advanced training network on institutional change in Asia, in comparative perspective with Europe. The coordinator, Ecole des Hautes Etudes en Sciences Sociales (France), promotes this network together with Oxford University (UK), Freie Universität Berlin (Germany), and in collaboration with Waseda University