Benoît Groz

Aurélien Lemay

Sławek Staworko

Piotr Wieczorek

Inference of Shape Graphs for Graph Databases

Keywords: 2012 ACM Subject Classification Information systems → Graph-based database models Keywords and phrases RDF, Schema, Inference, Learning, Fitting, Minimality, Containment. Digital Object Identifier 10.4230/LIPIcs.ICDT.2022.7

We investigate the problem of constructing a shape graph that describes the structure of a given graph database. We employ the framework of grammatical inference, where the objective is to find an inference algorithm that is both sound, i.e., always producing a schema that validates the input graph, and complete, i.e., able to produce any schema, within a given class of schemas, provided that a sufficiently informative input graph is presented. We identify a number of fundamental limitations that preclude feasible inference. We present inference algorithms based on natural approaches that allow to infer schemas that we argue to be of practical importance.

Introduction

Traditionally, in relational databases, defining the schema is the mandatory first step before a database can even be populated with data. However, novel database models, such as graph databases, quite intentionally allow to store and process data without declaring any schema. This facilitates the evolution of the structure of a database while the applications around it are being developed. In fact, often a suitable schema formalism is proposed after a particular database model has established its place in practice. In those circumstances a natural problem of schema inference arises: given a schema-less database construct a schema that captures the structure of the database. This problem has been identified as an important research direction [START_REF] Abiteboul | Research directions for principles of data management (Dagstuhl Perspectives Workshop 16151)[END_REF] and is well motivated since the knowledge of database structure is instrumental in any meaningful data processing task such as querying or transformation.

In the present paper, we present a principled approach to the problem of schema inference for graph databases. We consider RDF graphs and Shape Expression Schemas (ShEx) [START_REF] W3c | Shape expressions schemas[END_REF][START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF]. ShEx builds on the success of XML Schema and allows to describe the structure of an RDF graph by defining patterns of arrangement of RDF nodes. More precisely, ShEx specifies a collection of node types, each type defined by a regular expression that constrains the types of the outbound neighborhood of a node. Take for instance the RDF graph storing bug reports, presented in Figure 1 together with its shape expression schema. The schema requires a bug report to have a description and a user who submitted it. Optionally, a bug report may have an employee who verified it. Also, a bug report can have a number of related bug reports. A user has a name and an optional email address while an employee has a name and a mandatory email address. We point out that just like with XML Schema the Bug → descr : str, submittedBy : User, verifiedBy : Employee?, related : Bug* User → name : str, email : str? Employee → name : str, email : str Figure 1 An RDF graph with bug reports (top right) together with a shape expression schema (bottom) and the corresponding shape graph (top left). str is a built-in type for literal string nodes.

nodes of the RDF graph need not be typed and it is the task of a validation algorithm to find a valid node typing [START_REF] Prud'hommeaux | Shape Expressions: An RDF validation and transformation language[END_REF][START_REF] Labra Gayo | Validating and describing linked data portals using RDF Shape Expressions[END_REF][START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF]. Furthermore, some nodes may need to be assigned more than one type, for instance the node emp 1 needs to satisfy the types User and Employee.

We focus our investigation on a practical subclass ShEx 0 that defines types with collections of atoms with arities ranging over 1, ?, +, and *. This fragment does not allow disjunction or union types but can adequately approximate schemas with those features. ShEx 0 is particularly suited to capture the topology of RDF graphs obtained by exporting relational databases in a number of formalisms proposed for this task, such as R2RML, Direct Mapping, and YARRRML [START_REF] Sequeda | On directly mapping relational databases to RDF and OWL[END_REF][START_REF] Sequeda | Survey of directly mapping SQL databases to the Semantic Web[END_REF][START_REF] Boneva | Relational to RDF data exchange in presence of a shape expression schema[END_REF]. More importantly, the class ShEx 0 enjoys a sought-after feature of an equivalent graphical representation in the form of a shape graph whose nodes are types and edges are labeled by a symbol and a multiplicity (see Figure 1).

We present a principled approach to the problem of graph database schema inference, where we start with the fundamental question: What is an inference algorithm?. We answer it using the framework of grammatical inference [START_REF] Gold | Complexity of automaton identification from given data[END_REF], which in recent years has been successfully applied to a number of database formalisms ranging from queries [START_REF] Carme | Interactive learning of node selecting tree transducers[END_REF][START_REF] Staworko | Learning twig and path queries[END_REF] to schemas [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF][START_REF] Ciucanu | Learning schemas for unordered XML[END_REF] and transformations [START_REF] Lemay | A learning algorithm for top-down XML transformations[END_REF][START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF]. In essence, an inference algorithm needs to be both sound, i.e., produce a schema that validates the input graph, and complete, i.e., able to infer any goal schema with a sufficiently informative input graph. This formal framework allows us to tackle another fundamental question: When is inference feasible? Indeed, we identify classes of schemas that are not learnable, which reveals two principal challenges in schema inference: 1) distinguishing unbounded arities * and + from bounded ones 1 and ?, and 2) distinguishing recursive types from their finite non-recursive unravelings.

A suitable ShEx 0 inference algorithm needs to identify the types and their definitions. ShEx 0 assigns to every node of a graph a set of types by using the notion of embedding, which is an extension of the standard graph simulation. Consequently, our first attempt is to use graph simulation to identify sets of nodes whose outbound neighborhood shares structural similarity, and therefore, should have the same type. Interestingly, this approach yields a very reasonable inference algorithm that generalizes the structural information of the input graph, and in particular, easily introduces recursion in the constructed schema. The generalization is however very eager, and in particular, the algorithm clumps together any two types that are related by subtype relation such as Employee ⊆ User where every node of type Employee has also type User. Indeed, this inference algorithm produces a shape that is singular, having no two types that cannot be distinguished with the help of simulation, and consequently it prohibits schemas with subtypes like the schema in Figure 1.

To address this shortcoming we investigate using the context in which nodes are used: their inbound neighborhood. Indeed, the nodes of type User and the nodes of type Employee are used in different contexts, although their use may partially overlap e.g., the node emp 1 is used both as an employee and as a user. An inference algorithm based on using context information constructs a schema that belongs to the class of deterministic shape graph, which permits every edge label to be present at most once in a type definition. This class of schemas is incomparable with singular shape graph. For instance, the schema in Figure 1 is deterministic but is not singular. We find, however, that an indiscriminate use of the context information leads to overfitting, and in particular, it may fail to introduce recursion and may produce voluminous schemas. It appears that an inference algorithm must choose carefully the information to identify the set of types. We propose, as a proof of concept, a hybrid inference algorithm that extends the simulation-based approach with a modest amount of context information that consists of a single incoming edge. This algorithm produces schemas that are context-singular, a generalization of singular schemas that allows subtyping between types used in different contexts.

Finally, we survey a number of graph databases and inspect their schemas. Our analysis shows that ShEx 0 and the proposed subclasses lack certain features present in real-world schemas, most notably union types, but we can approximate them very well. This makes our algorithms an excellent solution for preparing the first draft of a schema to be refined by a knowledgeable architect.

Organization. The paper is organized as follows. In Section 2 we present basic notions, including shape graphs and their embeddings. In Section 3 we formally state the problem of inference. In Section 4 we present a simulation-based inference algorithm for the class of singular shape graphs. In Section 5 we present negative implications of unrestrained use of context information in inference. In Section 6 we propose a hybrid approach combining the simulation-based approach with elements of context information. In Section 7 we present an analysis of schemas of a number of graph databases. We discuss related work in Section 8. We summarize our findings and outline future research directions in Section 9.

Basic notions

Throughout this paper we apply a functional notation to relations, and conversely, often view functions as relations. For instance, for a binary relation

R ⊆ A × B we set dom(R) = {a ∈ A | ∃b ∈ B. (a, b) ∈ R}, ran(R) = {b ∈ B | ∃a ∈ A. (a, b) ∈ R}, R(a) = {b ∈ B | (a, b) ∈ R} for a ∈ A, and R -1 (b) = {a ∈ A | (a, b) ∈ R} for b ∈ B.
Intervals. We use the standard notation [i; j] for 0 ≤ i ≤ j ≤ ∞ to denote intervals that represent nonempty sets of consecutive natural numbers. By I 0 we denote the set of all intervals. Our schema formalisms use only four basic intervals (M 0 ) given with their shorthand notation: Graphs and schemas. We employ a generic model of a graph that we use to model both RDF and the subclass ShEx 0 that allows type definitions consisting of collections of atoms using basic intervals [START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF][START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF]. Our methods do not inspect data values of literal nodes, and consequently, we will abstract them using their type alone but this requires us to record the number of some types of edges as illustrated in Figure 2a. When drawing graphs we typically omit the label 1 and simple intervals are denoted with natural numbers e.g., 2 stands for [2; 2] which indicates two identical edges. We point out a dichotomy of node kinds and their types: literal nodes can only have literal types and non-literal nodes can only have non-literal types. While it might be tempting to remove literal types from consideration and focus on data-free graphs, we keep literal types and nodes because without them it is difficult to define reasonable schema families without subtypes.

1 is [1; 1], ? is [0; 1], + is [1; ∞] and * is [0; ∞]. A simple interval has the form [i; i] for 0 ≤ i < ∞,
We assume a finite set Σ of edge labels and an enumerable set of node identifiers N = U ∪L, where U is an infinite set of identifiers used to represent both URIs and blank nodes, and L is a finite set of types of literal nodes e.g., str representing strings. We assume that U ∩ L = ∅.

Definition 1. A graph G is a triple (N G , E G , arity G ), where N G ⊆ N is a finite set of nodes, E G ⊆ (N G ∩ U) × Σ × N G
is a set of labeled oriented edges, and arity G maps every edge to an interval. A shape graph is a graph that uses only basic intervals and by ShEx 0 we denote the set of all shape graphs. A simple graph is a graph that assigns to every edge a simple interval and this simple interval is 1 unless the edge leads to a node in L. By G 0 we denote the set of simple graphs. A simple graph G is data-free if N G ∩ L = ∅.

In Figure 2b we present a more concise version of the graphs from Figure 1 adapted to our graph model. For M ⊆ M 0 , we write ShEx 0 (M ) to restrict the choice of arities to M . For an edge e = (n, p, m) we let source(e) = n, lab(e) = p, and target(e) = m. For a given node n of G we identify its outbound neighborhood out G (n) = {e ∈ E G | source(e) = n}. Given two graphs G 1 and G 2 by G 1 G 2 we denote their disjoint union. In the sequel, we often refer to shape graphs as schemas and their nodes as types. We also abuse the standard tree terminology and say that nodes n and n are siblings if there is a node m that has outgoing edges to n and to n .

Embeddings. We recall next, and illustrate in Figure 2b, the notion of embedding that allows to define the semantics of shape graphs as schemas [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF] and is instrumental in our inference methods. Here, by id A we denote the identity relation on a given set A.

Definition 2 (Embedding). [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF] An

embedding of a graph G in a graph H is a binary relation R ⊆ (N G × N H ) ∩ (U × U ∪ id L ) such that for any (n, m) ∈ R

3.

for every e ∈ out G (n) we have that (target(e), target(λ(e))) ∈ R. The embedding R is total if dom(R) = N G . We write G H if there exists a total embedding of G in H. An autoembedding of G is an embedding of G in itself. Figure 2b presents an example of the embedding between the concise versions of RDF graph and the shape graph in Figure 1. It is known that there exists exactly one maximal embedding between two graphs [START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF] (since the union of embeddings is also an embedding), and constructing maximal embeddings between pairs of shape graphs and between simple graphs and shape graphs is in P [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF]. In the sequel, by G:H we denote the maximal embedding of G in H, by G the maximal autoembedding of G, and we use both relation symbols using infix notation. The language of a shape graph H is L(H) = {G ∈ G 0 | G H}. We recall from [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF], that embeddings can be composed, and in particular, G H implies L(G) ⊆ L(H), but the converse does not necessarily hold as illustrated in Figure 3. Throughout the paper we use the following terminology. A simple graph G satisfies a shape graph H, and H recognizes G, iff G ∈ L(H). Two shape graphs H and K are equivalent, in symbols

H ≡ K, iff L(H) = L(K). A node n of a simple graph G has type t of a shape graph H iff n G:H t. Given two types t 1 and t 2 of a shape graph H, a type t 1 is a subtype of t 2 , in symbols t 1 ⊆ H t 2 , iff ∀G ∈ L(H). ∀n ∈ N G . n G:H t 1 ⇒ n G:H t 2 . Finally, a type t of H is recursive iff it is part of a loop in H.

Inference of shape graphs

In this section we introduce the framework of grammatical inference, present a number of limit point arguments that help to identify main challenges in inferring shape graphs, and finally, we present the construction of graph aggregation that we use to infer shape graphs.

Grammatical inference

In this paper we investigate the problem of shape graph inference, which consists of constructing a shape graph for a given input simple graph. To this end we adopt the framework of grammatical inference [START_REF] Gold | Complexity of automaton identification from given data[END_REF], which has originally been proposed for word languages and has been successfully applied to a number of database formalisms ranging from queries [START_REF] Carme | Interactive learning of node selecting tree transducers[END_REF][START_REF] Staworko | Learning twig and path queries[END_REF] to schemas [START_REF] Bex | Learning deterministic regular expressions for the inference of schemas from XML data[END_REF][START_REF] Ciucanu | Learning schemas for unordered XML[END_REF] to transformations [START_REF] Lemay | A learning algorithm for top-down XML transformations[END_REF][START_REF] Laurence | Learning sequential tree-to-word transducers[END_REF]. In essence, the framework requires the inference algorithm to be capable of inferring any goal schema given a sufficiently informative input. We are interested in inference from positive data: the input consists of a graph that belongs to the goal language. To prevent collusion, namely a solution where a characteristic input graph encodes the goal schema using an elaborate scheme, the inference algorithm is required to be robust under extension: it must infer the goal schema even if the characteristic graph is accompanied by other potentially less informative graphs that satisfy the schema. Formally, G extends G consistently with schema

H iff there is G such that G = G G and G, G , G ∈ L(H).

Definition 3. A class of shape graphs C is learnable from a class of graphs G iff there is an inference algorithm learner such that Soundness For every input graph G ∈ G the inference algorithm returns a schema learner(G) = H such that H ∈ C and G ∈ L(H). Completeness For every goal schema H ∈ C there exists a characteristic graph G H ∈ L(H)

such that for any G that extends G H consistently with H we have learner(G) ≡ H. Furthermore, we say that C is learnable in polynomial time if the inference algorithm works in polynomial time. We also say that C is learnable in polynomial data if there exists a polynomial that bounds the size of the characteristic graph as a function of the size of the goal schema.

As an illustrative example of grammatical inference consider the problem of inferring basic intervals M 0 from a given sample of its members {i 1 , . . . , i k }. Take the function fit M0 that returns the smallest basic interval that contains all the elements given on the input. Naturally, fit M0 is a sound inference algorithm since it returns an interval that contains all the elements given on the input. It is also a complete inference algorithm because we can construct characteristic samples for every element of M 0 . For instance, for the goal interval

+ = [1; ∞] a characteristic sample is {1, 2}. Indeed, fit M0 ({1, 2}) = + but more importantly fit M0 (X) = + for any X subset of [1; ∞] that includes {1, 2}.
Now, consider the full class of intervals I 0 and take the function fit I0 as a inference algorithm. It is naturally sound since fit I0 (X) = [min(X); max(X)] but it is not complete since it cannot infer an unbounded interval [i 0 ; ∞] from a finite input set. In fact, I 0 is not learnable because one can show that there is no sound and complete inference algorithm for I 0 (from positive samples alone). Next, we present a general characterization of classes of languages that are not learnable. We will use it as a tool for identifying key challenges in schema inference.

Limit point

We recall that a class of languages C has the limit point property iff C contains an ascending chain of languages L 1 L 2 . . . whose limit point L ∞ = i L i also belongs to C. It is a folklore result that the limit point property precludes learnability (from positive examples) [START_REF] Angluin | Inductive inference of formal languages from positive data[END_REF]: essentially, no finite amount of examples from the goal language allows to distinguish between the limit point L ∞ and some language L i in the ascending chain. We formally show that it also holds for the framework we adopt in this paper. Proposition 4. No class of shape graphs with the limit point property is learnable from simple graphs.

The limit point argument allows us to identify a number of limitations of inference of shape expressions schemas. Lemma 5. For any M ⊆ {1, ?, *, +} with at least two elements the class ShEx 0 (M ) has the limit point property.

Proof sketch. It suffices to consider sets of 2 multiplicities and in Figure 5 we present three cases. The limit point arguments for all remaining cases are constructed very similarly to ShEx(?, *) in Figure 5a (details in appendix).

L 0 : L 1 : a?
Consequently, we obtain the following corollary.

Corollary 6. ShEx 0 is not learnable from simple graphs.

A closer look at the limit point arguments offers an insight into the reasons why inferring ShEx 0 is not feasible. Firstly, we observe in Figure 5a that one of the challenges in distinguishing between L i and L ∞ is in deciding based on finite input example when to use unbound arity * as opposed to ? (similar argument holds for + and ?, etc.). Secondly, in Figures 5b and5c we observe an analogous difficulty in deciding between other pairs of arities, but more importantly, we also observe a different difficulty: whether to choose a simple recursive type (L ∞ ) or allow some arbitrary non-recursive unfolding of it (L i ). To summarize, the constructions in Figure 5 point to two key challenges of inferring shape schemas for graph databases: 1) distinguishing between bounded and unbounded arities, and 2) introducing recursive types especially from a possibly acyclic input example.

Graph aggregate

The inference algorithms that we propose in this paper construct schemas with an operation that generalizes the standard graph quotient. Recall that the graph quotient operation essentially reduces to a single node every set of nodes that are equivalent w.r.t. a given equivalence relation. In the context of schema inference, we are interested in grouping together nodes that we deem to have the same type but we point out that the underlying relation "n and m are deemed to have the same type" needs not be transitive in general. In fact, we do not even assume that this relation is reflexive because we may wish to intentionally ignore nodes of the input graph that we do not find informative enough.

Definition 7. A node grouping of a simple graph G = (N G , E G , arity G ) is a collection P ⊆ 2 N G of sets of nodes of G such that any N ∈ P with N ∩ L = ∅ is a singleton. Given
N H = P, E H = {(N, a, N ) ∈ P × Σ × P | ∃(n, a, n ) ∈ E G , n ∈ N ∧ n ∈ N }, arity H (N, a, N ) = fit M {arity G (n, a, n ) | n ∈ N , (n, a, n ) ∈ E G } | n ∈ N .
The requirement N ∩ L = ∅ follows from the dichotomy of node kinds and their types. To ensure that the aggregate is technically a (shape) graph, we assume that any subset of N is also a node identifier and for any ∈ L we interpret { } as . In the sequel, when the set of intervals M is known from the context, we omit it in the aggregate and simply write G ÷ P .

In essence, for a given input graph G, our inference algorithms explore the lattice (P G , ) of all node groupings P G of G from

P ⊥ = {{n} | n ∈ N G } to P = {N G \ L}∪{{ } | ∈ N G ∩L}.
The structure of this lattice is consistent with the containment relation:

P 1 P 2 iff G ÷ P 1 ⊆ G ÷ P 2 .
This connection to containment is essential for guiding inference algorithms with characteristic graphs. When the goal schema is G ÷ P for a node grouping P then for every relevant P P the characteristic graph needs to contain an example showing G ÷ P ⊇ G ÷ P .

Example 8. Consider G 0 and H 0 in Figure 2b, and take the node grouping that corresponds to the typing of G 0 w.r.t.

H 0 : P = {{b 1 , b 2 , b 3 , b 4 }, {u 1 , u 2 , e 1 }, {e 1 }, {str}}. The aggregate G 0 ÷ M0 P is in fact (equivalent to) H 0 .
The above example shows that G 0 carries sufficient information that with the right partition allows to infer the goal schema H 0 .

The task is to identify a method that allows to group nodes of the input graph that are deemed to have the same type and at the same time can introduce unbounded arities and recursion in type definitions. A natural attempt at grouping nodes of a graph would be to use bisimulation. But as we illustrate in Figure 4 this fails to introduce unbounded arities and recursive types. In fact, it has been studied in the literature [START_REF] Goasdoué | RDF graph summarization for first-sight structure discovery[END_REF] and found to fail to generalize appropriately the input graph.

Singular shape graphs

In this section we address the two key challenges of inference by grouping nodes with the help of graph simulation relation. This yields an inference algorithm for a subclass of singular shape graphs. The inference algorithm allows to infer unbounded arities and recursive types even from acyclic input graph. The price is the ability to distinguish types from their subtypes. Shape graphs assign types to nodes using an embedding, which is an adaptation of the standard notion of graph simulation. Consequently, we explore an approach of grouping together nodes that are comparable with the simulation relation. To that effect, for a given simple graph G we construct the graph G* by changing the arity of every edge to *, and then, any autoembedding of G* is a simulation relation on G and vice versa. Hence, we use the maximal autoembedding G* to assess the relative amount of schema information that a node supplies: if m G* n, we consider m to provide no more schema information than n does. We introduce useful short-hands. We say that n sim-dominates m iff m G* n and m = n. Also, n properly sim-dominates m is n sim-dominates m and n G* m. We say that n and m are sim-equivalent if m G* n and n G* m. Finally, a node is sim-maximal if it is sim-dominated only by sim-equivalent nodes.

Using simulation to group nodes has an important drawback: the inability to distinguish types from their subtypes. Indeed, if t 1 ⊆ t 2 , then any node that has type t 1 is simulated by nodes of type t 2 that characterize the type t 2 . We return to this problem in Section 6 where we show how to handle inference of restricted cases of subtypes. We point out that permitting arbitrary subtypes allows to construct ascending chains, which can be then easily used in limit point arguments, as evidenced for instance in Figure 5b. This allows us to conclude that inferring subtypes is inherently problematic. Furthermore, we show that even forbidding subtypes does not suffice to guarantee learnability. Proposition 9. Let FlatShEx 0 be the subclass of shape graphs where no two different types are comparable by the containment relation. For any subset M ⊆ M 0 with at least two elements FlatShEx 0 (M ) is not learnable.

Consequently, stronger restrictions are needed and we propose the class of singular schemas whose types can all be distinguished with the graph simulation relation. Definition 10. A type t of a shape graph H is singular iff t is not sim-dominated by any type in H. A shape graph is singular iff it has only singular types and by SinShEx 0 we denote the set of all singular shape graphs.

Intuitively, singularity ensures that for any two types t 1 and t 2 , there exist nodes of type t 1 that can be distinguished from all nodes of type t 2 with the help of simulation. In the following example we show that simulation needs to be used carefully when identifying groups of nodes of the same type.

Example 11. To keep the example simple, we limit the intervals used in shape graphs to {1, ?, *}. In figures we use a dotted green arrow n m to indicate that n simdominates m. Take the graph G 2 in Figure 6, identify its sim-maximal nodes Max = {n 0 , n 1 , n 2 , str}, and consider the node grouping P 0 = {{n 0 }, {n 1 }, {n 2 }, {str}}. This grouping is too sparse: the aggregate G 2 ÷ P 0 does not recognize G 2 . Consider then the grouping where every sim-maximal node is accompanied by all sim-dominated nodes: The node grouping P max is not a good starting point for an inference algorithm because it might be overly eager as we illustrate next. Consider the graph G 3 in Figure 7. The node m 2 is sim-dominated by m 1 and m 3 . The grouping P max = {{m 0 }, {m 1 , m 2 }, {m 2 , m 3 , m 4 }, {str}} forces * on the edge from {m 0 } to {m 1 , m 2 }. It is, however, not necessary to add m 2 to any group: P 1 = {{m 0 }, {m 1 }, {m 3 , m 4 }, {str}} already yields H 3 that is singular, recognizes G 3 , and is a tighter fit than G 3 ÷ P max . merge S and T in P 10: return G ÷ M P end only groupings where every sim-maximal node n belongs to precisely one node group, which can be accessed with a lookup operation P [n]. The algorithm begins by identifying all sim-maximal nodes (line 1) and grouping together all sim-equivalent nodes (lines 2-4). Next, as long as the aggregate G ÷ M P does not recognize the input graph, the algorithm iteratively identifies a node m that is absorbed by a node group P [n] such that m ∈ P [n] (lines 5-7). Among all eligible pairs of m and P [n] we choose one according to the following order Φ: 1. siblings first any m that has a sibling n ∈ Max such that P [n] contains all siblings of m that sim-dominate it. Finally, the algorithm merges any node groups that prevent the shape graph G ÷ M P from being singular (lines 8-10). We point out that the preference order Φ may indicate multiple equally preferred pairs and the algorithm may choose an arbitrary one: regardless of the choice the output always recognizes the input graph and when the input contains a characteristic graph, the algorithm will always converge on the goal schema. Φ prevents the algorithm sim-learner from performing unnecessary generalization: when executed on the graph G 3 in Figure 7 it returns the schema H 3 . Furthermore, when run on G 2 in Figure 6 the algorithm returns the schema H 2 , which illustrates that it is capable of inferring recursive types even from acyclic input graphs.

P max = {{n 0 }, {n 1 , n 3 }, {n 2 , n 4 }, {str}}. While G 2 ÷ P max recognizes G 2 ,

I C D

In general the algorithm is sound for SinShEx 0 , but here we only claim that sim-learner 1,* is sound and complete for the shape graphs using 1 and *. Theorem 12. SinShEx 0 (1, *) is learnable in polynomial time and data from simple graphs.

In Section 6.2 we take advantage of Φ to show completeness for a larger class but it remains an open question if the full class of singular shape graphs is learnable in polynomial time and data (but the existing evidence suggests it is unlikely [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF]). The full class is however learnable with an algorithm that exhaustively explores the exponential space of possible singular shape graphs and uses an exponentially-large characteristic graph to help navigate this space.

Theorem 13. SinShEx 0 is learnable from simple graphs.

Deterministic shape graphs

In this section we investigate the potential ramifications of attempting to improve the process of identifying the set of types by exploiting the context in which nodes are used in the graph. More precisely, two nodes n and n are used in the same context of node m and label a if there are two edges (m, a, n) and (m, a, n ), and in that case the nodes n and n should have the same type. Such premise leads us to the class of deterministic shape expressions schemas that allow at most one type to be used in a given context.

Definition 14.

A type t of a shape graph H is deterministic iff for every label a ∈ Σ the type t has at most one outgoing edge with label a. A deterministic shape graph has only deterministic types and by DetShEx 0 we denote the set of all deterministic shape graphs.

Interestingly, the powerset method for determinization of finite automata can be adopted for inference of DetShEx 0 . We illustrate this algorithm in Figure 8 but refrain from formally introducing it because we do not wish to promote it in this paper. Later in this section we provide its alternative semantic characterization that will allow us to identify the pitfalls of an indiscriminate use of context information for shape graph inference. Some caveats follow. Firstly, not every simple graph can be recognized by a deterministic shape graph. For instance, the graph G 1 in Figure 2a satisfies no deterministic schema because G 1 has a node with two outgoing b-edges, one of which leads to a literal node and the other to a non-literal node. Consequently, we limit the inputs to data-free graphs, simple graphs with no literal nodes. Secondly, the limit point in Figure 5b shows that DetShEx 0 is not learnable, and thus, we recall from [START_REF] Staworko | Containment of shape expression schemas for RDF[END_REF] a subclass DetShEx - 0 that we show learnable with the determinization algorithm. Formally, a reference to a type t ∈ N H is any edge e ∈ E H that leads to t i.e. target H (e) = t. A reference e is *-closed if arity H (e) = * or all references to source H (e) are *-closed. DetShEx - 0 is the class of deterministic shape graphs that do not use + and any type using ? is referenced at least once and all references to it are *-closed. Theorem 15. DetShEx 0 is not learnable from data-free graphs. DetShEx - 0 is learnable from data-free graphs in polynomial data.

I C D T 2 0 2 2 7:12

Inference of Shape Graphs for Graph Databases

It can be proved (see appendix) that the determinization algorithm outputs the containmentminimal shape graph in DetShEx - 0 that satisfies the input data-free graph G. This makes the determinization algorithm an embodiment of the minicon principle which postulates for constructing the minimal consistent schema. This principle has a negative ramifications. Proposition 16. For any n there exists a graph G n of size quadratic in n such that the containment-minimal shape graph in DetShEx - 0 that validates G is of size exponential in n. We conclude that an indiscriminate use of the context information has negative impact on inference of shape graphs: the obtained schemas risk being too verbose and overfitted. Also, nontrivial classes of shape graphs are too rich to benefit from blindly following the minicon principle.

Hybrid approach

In this section we pursue a hybrid approach that extends the simulation-based approach with a limited amount of context information to enable inference of shape graphs with subtypes.

We then identify the subclass that our hybrid algorithm is able to infer among shape graphs using arbitrary basic intervals.

Context-singular shape graphs

We extend the simulation-based approach with context information limited to the labels of incoming edges. This allows to infer subtypes as long as they are used in different contexts.

For instance, this extension can infer the schema in Figure 1, where Employee ⊆ User but Employee is used in the context of verifiedBy and User is used only in the context submittedBy.

Here, the contexts in which a type t is used in a shape graph H are described by the labels of incoming edges: ctx-lab H (t) = {a ∈ Σ | ∃s ∈ N H . (s, a, t) ∈ E H }. Singularity of shape graph requires that no type is sim-dominated by another type. We relax this by allowing a sim-dominated type as long as it is used in at least one context where none of its sim-dominating types are.

Definition 17. Given a shape graph H, a type t of H is context-singular if and only if ctx-lab

H (t) ⊆ {ctx-lab H (t ) | t ∈ N H , t H* t , t = t }. H is context-singular if it
has only context-singular types. CtxSinShEx 0 is the set of all context-singular shape graphs.

To adapt sim-learner to inference of context-singular shape graphs we introduce an uncoupling operation that for a given graph creates a distinct clone of a node for every of its incoming edges, so that all incoming edges of a node have the same label. Formally, the uncoupling of a graph G is Ḡ = (N Ḡ, E Ḡ, arity Ḡ), where

N Ḡ = {uncouple(n) | n ∈ N G }, uncouple(n) =        {n} if n ∈ L, {(⊥, n)} if ctx-lab G (n) = ∅, {(a, n) | a ∈ ctx-lab G (n)} otherwise, E Ḡ = {(η, a, trg(a, m)) | (n, a, m) ∈ E G , η ∈ uncouple(n)} trg(a, m) = m if m ∈ L, (a, m) otherwise, arity Ḡ(η, a, trg(a, m)) = arity G (n, a, m) for (n, a, m) ∈ E G and η ∈ uncouple(n).
B. Groz, A. Lemay, S. Staworko, and P. Wieczorek

7:13

When each node has incoming edges with the same label, using the context information is simpler. For instance, a type t of an uncoupled shape graph H is context-singular iff there is no type t such that t H* t and ctx-lab H (t) ⊆ ctx-lab H (t ). Consequently, for uncoupled graphs we define a contextualized variant of the autoembedding relation:

n ctx K m iff n K m and ctx-lab K (n) ⊆ ctx-lab K (m).
We adapt terminology and say that n ctxdominates m iff m ctx K n and n = m. Also, n is ctx-maximal if any node that ctx-dominates n is also ctx-dominated by n. Now, the inference algorithm hybrid-learner is a modification of sim-learner where we replace every occurrence of G by Ḡ and every occurrence of by ctx . We illustrate hybrid-learner on an example.

Example 18. We run hybrid-learner in Figure 9 on the graph G 0 introduced in Figure 2. In the uncoupling of G 0 we indicate with m n that m ctx G0* n. In this example we use the complete set of basic intervals M 0 = {1, ?, +, *}. The algorithm begins with the node grouping P 0 = {{(r, b 1 )}, {(v, e 1 )}, {(s, e 1 ), (s, u 2 )}, {str}} obtained from the ctx-maximal nodes in G 0 . Because G 0 ÷ P 0 does not recognize G 0 , the algorithm uses Φ to identify nodes that can be absorbed: (r, b 4 ) can be absorbed in P 0 [(r, b 1 )] only. After this operation the node grouping P 1 still does not yield a shape graph that recognizes G 0 . In the next step, (r, b 3 ) being ctx-dominated by its sibling (r, b 4 ) is absorbed in P 1 [(r, b 1 )]. The resulting node grouping P 2 again fails to recognize G 0 . Finally, the node (s, u 1 ) is absorbed in P 2 [(s, e 1 )] and the resulting node grouping P 3 yields G 0 ÷ P 3 ≡ H 0 which recognizes G 0 .

Uncoupling G0 of G0 (r, b3) (r, b1) (s, u1) (v, e1) (s, e1) (r, b4) (⊥, b2) (s, u2) str r
The algorithm hybrid-learner is a sound inference algorithm for CtxSinShEx 0 and analogously to sim-learner it is also complete for CtxSinShEx 0 (1, *). The full class of context-singular shape graphs is learnable with an exhaustive exploration of the exponential search space with exponentially large characteristic graphs. Theorem 19. CtxSinShEx 0 (1, *) is learnable in polynomial time and data from simple graphs. CtxSinShEx 0 is learnable from simple graphs.

Absorption-protected shape graphs

In this section we characterize the subclass of CtxSinShEx 0 , using all basic intervals M 0 = {1, ?, +, *}, for which hybrid-learner is sound and complete. To do that we first identify the information that needs to be contained in the input graph for hybrid-learner to infer the right arity on the edge of a the goal shape graph.

Let us fix a goal shape graph H and an edge (t, a, s) ∈ E H . For hybrid-learner to output H, it must be able to construct from a characteristic graph G two groups of nodes P t and I C D T 2 0 2 2

7:14

Inference of Shape Graphs for Graph Databases P s that characterize the interval arity H (t, a, s). In particular, they must contain sufficient information to indicate whether the interval is unbounded (+ and *) and whether it is nullable (? and *).

Characterizing an unbounded interval is relatively simple. It suffices to introduce in G a ctx-maximal node n t of type t that has at least two outgoing a-edges to nodes n s and m s of type s, one of which, say n s should also be ctx-maximal. Naturally, the nodes n t and n s will be put by hybrid-learner in the groups P t and P s respectively. Because of the first rule of the preference order Φ, the node m s will also be added to P m .

Characterizing a nullable interval is more challenging since it requires making sure that P t and P s absorb information that is more volatile. Namely, we need to make sure that G has a ctx-maximal node n t and a node m t of type t without any a-edge to a node of type s. Since n t is ctx-maximal, it will be absorbed in P t but since m t is not a ctx-maximal node, G must protect it from being absorbed by any group other than P t . The node m t can be absorbed into a group P s , representing a type s , if s dominates a version η of the type t from which we remove the edge (t, a, s). Naturally, m t is protected if no such node exists, and then the second rule of Φ ensures that m t ends up in P t . Otherwise, the type t allows protection from an absorption if t has an incoming edge with unbounded arity and none of the siblings of t dominate η. Then m t also ends up in P t because of the first rule of Φ for same reasons as explained for unbounded intervals.

To characterize the classes of schemas that allow protection from absorption we need to introduce a construction of the type η. Formally, let H be a shape graph H, η ∈ N \ N H a fresh node identifier, and e ∈ E H an edge from t to s with unbounded arity. The absorption-protection test graph APT * (H, e, η) is a shape graph H defined as:

N H = N H ∪{η}, E H = E H ∪{(η, a, s )|(t, a, s ) ∈ out H (t) \{e}}, arity H (f ) = * for f ∈ E H .
Essentially, we add the type η, for every outgoing edge e from t other than e, we add an outgoing edge with the same label as e from η to the same node as the endpoint of e , and we set arities of all edges to *. Next, we formally characterize the class of shape graphs that hybrid-learner is capable of identifying (we use sim-domination because η in APT * (H, e, η) does not have any incoming edges). Definition 20. A type t of a shape graph H is absorption-protected iff for every edge e ∈ out H (t) with nullable arity one of the following conditions holds: 1. t is the only node that sim-dominates η in APT * (H, e, η) or, 2. t has an incoming edge with unbounded arity and t is the only node among its siblings that sim-dominates η in APT * (H, e, η). An absorption-protected shape graph is a context-singular shape graph that has only absorptionprotected types. By AbsShEx 0 we denote the set of all absorption-protected shape graphs.

We illustrate absorption protection in the following example.

Example 21. In Figure 10, H 1 is not absorption-protected because of the edge e = (t 1 , a?, str). The copy η of t 1 without the edge e is sim-dominated by the type t 2 of H 1 . H 2 is absorption-protected. Even if for the type s 1 we create a copy η without the edge (s 1 , a?, str) and find it is sim-dominated by s 2 , the type s 1 has an incoming unbounded r-edge and the type s 2 is not a sibling of s 1 .

We point out that the shape graph in Figure 1 is absorption protected, which explains why in Example 18 the algorithm correctly infers the schema H 0 . We finish by formally stating the learnability result. Theorem 22. AbsShEx 0 is learnable in polynomial time and data from simple graphs. APT * (H1, e, η) where e = (t1, a?, str) H2 Figure 10 Two shape graphs, H1 is not absorption-protected because t1 is not, but H2 is.

Schemas of existing graph databases

In this section we present an analysis (Table 1) of a number of graph databases in order to find out to what extent their schemas can be captured with shape graphs and the subclasses that we propose, and consequently, to assess the usefulness of the proposed inference algorithms.

We have analyzed: the Berlin SPARQL Benchmark [START_REF] Bizer | The Berlin SPARQL benchmark[END_REF], the Tpc-h benchmark converted to RDF with Direct Mapping [START_REF]TPC benchmarks[END_REF][START_REF] W3c | A direct mapping of relational data to RDF[END_REF], the Nobel Prize database [START_REF] Asif | Enhancing the Nobel Prize schema[END_REF], an RDF serialization of the Dblp database (retrieved from https://www.rdfhdt.org/datasets/ on 14.01.2021), the Springer Nature knowledge graph SciGraph [START_REF] Iana | Building a conference recommender system based on SciGraph and WikiCFP[END_REF], the Covid19 knowledge graph [START_REF] Reese | KG-COVID-19: A framework to produce customized knowledge graphs for COVID-19 response[END_REF], and SHACL constraints in the version 4 of Yago knowledge base [START_REF] Suchanek | Yago: A core of semantic knowledge[END_REF]. For each database we have defined appropriate schemas using ShEx, which is a fully fledged schema language and properly contains ShEx 0 (cf. [START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF]). Complete schemas and more details can be found in the appendix. We have found that the ShEx schemas for the above databases require the use of disjunction and union types, features that are absent in ShEx 0 [START_REF] Staworko | Complexity and expressiveness of ShEx for RDF[END_REF][START_REF] W3c | Shape expressions schemas[END_REF]. We illustrate them on the following example inspired by DBLP. It states that a book has either creators (authors) or editors but never both, has a single title, and references an arbitrary number of articles and books. We say that this base type definition has 3 clauses, one uses disjunction, and one uses a union type. Union types are trivial when used only under * since a : (t 1 ∪ t 2 )* is equivalent to a : t 1 *, a : t 2 *. For every schema we have measured the quantities of the following objects: nontrivial (and trivial) union types, clauses, clauses with disjunction, clauses with nontrivial (and trivial) use of a union type.

To help assessing the usefulness of the proposed inference algorithms, for every ShEx schema we have constructed its straightforward ShEx 0 -approximation as illustrated on the Then in each ShEx 0 we have measured the number of all (base) types, those that are singular (Sin), context-singular (CtxSin), and absorption-protected (Abs). Additionally, we have counted the number of types that are signature-independent (σ-ind): types whose set of labels of outgoing edges is incomparable with others.

We first analyze our findings for the graph databases and knowledge graphs (first 6 rows). We observe that the numbers of nontrivial union types and disjunctions are relatively small. Also, deterministic types are relatively low in some databases because of use of union types: even trivial use of union types in a type definition precludes determinism. We point to the differences in signature-independent and singular types, on average 69% vs. 79% resp., which indicates that using simulation to identify types has advantages over an approach that reduces a type to the labels of its outgoing types. While the numbers of singular types are relatively large, 79% on average, the numbers of context-singular types, 94% on average, are even more impressive, and the significant improvement validates our approach of incorporating the context information in the inference process.

For the knowledge base Yago the results indicate that our algorithms would offer little improvement over simpler approaches (σ-ind) that attempt to identify types by using the labels of their outgoing edges. We attribute this to the use of rich hierarchies of classes which introduce many subtype relationships between types. We point out, however, that those class hierarchies are defined with ontologies that specify rules that allow to type the graph. Our methods do not take advantage of this typing information, and therefore, are not geared towards inference for knowledge bases. Alternative tools for inference from typed graphs should be used (see our preliminary results on the topic in [START_REF] Groz | Inference of shape expression schemas typed RDF graphs[END_REF]).

We conclude that inference algorithms for the proposed classes CtxSinShEx 0 and AbsShEx 0 are an attractive choice for the first draft of the schema for (untyped) graph databases and knowledge graphs to be later on improved by a data specialist, especially when the type hierarchy is relatively flat.

Related work

Several approaches have been investigated in the late 90's to summarize graph data, defining schema models, and algorithms to infer schemas from graph data, then viewed as semi-structured data [START_REF] Buneman | Adding structure to unstructured data[END_REF][START_REF] Fernandez | Optimizing regular path expressions using graph schemas[END_REF][START_REF] Nestorov | Representative objects: Concise representations of semistructured, hierarchial data[END_REF][START_REF] Nestorov | Extracting schema from semistructured data[END_REF]. A large part of the literature focuses on graph summarization [START_REF] Bonifati | Graph summarization[END_REF], where the purpose is to obtain a concise representation of an input graph that can be used to formulate queries against the data. Our approach takes a different perspective of the same problem, where the input data is considered as evidence from which we must infer an unknown target schema. Using the grammatical inference framework enables us to offer strong guarantees, and lay the ground for a principled fundamental approach. To the best of our knowledge this is a first, and this complements the traditional approach in the literature that consists in evaluating algorithms empirically on real-life graph data to measure the tradeoff between compactness and the accuracy of the description.

A Dataguide [START_REF] Goldman | Dataguides: Enabling query formulation and optimization in semistructured databases[END_REF] of a graph represents as a DFA all the paths that can be navigated from a root node in the graph. Dataguides are thus similar in spirit to our determinization procedure, but do not represent the arity of paths and assume that specific entry points have been specified; the root nodes. This approach, like determinization, can identify subtypes, and cycles (provided the cycles are presented in the input data). Several approaches have been proposed to infer schemas for tree-structured data [START_REF] Garofalakis | XTRACT: learning document type descriptors from XML document collections[END_REF][START_REF] Min | Efficient extraction of schemas for XML documents[END_REF][START_REF] Chidlovskii | Schema extraction from XML: A grammatical inference approach[END_REF][START_REF] Bex | Inference of concise DTDs from XML data[END_REF][START_REF] Bex | Inferring XML schema definitions from XML data[END_REF] or JSON data [START_REF] Baazizi | Schema inference for massive JSON datasets[END_REF][START_REF] Baazizi | Parametric schema inference for massive JSON datasets[END_REF]. The schemas inferred include DTDs, tree automata, and XML Schema, and thus are expressive enough to represent the arity of edges. However, these approaches focus on tree-structure and do not consider cycles (as expressed via mechanisms such as ID/REF). The tree structure means that the schema can be inferred recursively, and thus the task is essentially about inferring efficiently a regular expression representing for the children of each tree node.

More recently, the inference of schemas for graphs has focused on RDF and property graphs [START_REF] Kondylakis | RDF graph summarization: principles, techniques and applications[END_REF]. Several applications [START_REF] Fan | Query preserving graph compression[END_REF][START_REF] Zhang | Assg: adaptive structural summary for RDF graph data[END_REF][START_REF] Khatchadourian | ExpLOD: Summary-based exploration of interlinking and RDF usage in the linked open data cloud[END_REF][START_REF] Tran | Managing structured and semistructured RDF data using structure indexes[END_REF] rely on graph (bi)simulation to build a quotient graph w.r.t. an equivalence relation. The quotient graph merges all nodes that belong to the same equivalence class. Those proposals generally do not assign arities to the edges with a few exceptions such as [START_REF] Tsuboi | An algorithm for extracting shape expression schemas from graphs[END_REF]. Variants [START_REF] Campinas | Efficiency and precision trade-offs in graph summary algorithms[END_REF][START_REF] Schätzle | Large-scale bisimulation of RDF graphs[END_REF][START_REF] Tran | Managing structured and semistructured RDF data using structure indexes[END_REF] consider both forward and backward bisimilarity, which means that types can be defined based on both the incoming and outgoing edges. Full bisimulation is rather rare in heterogenous graphs and even limiting it to the 1-hop neighbourhood does not help [START_REF] Goasdoué | Incremental structural summarization of RDF graphs[END_REF][START_REF] Čebirić | A framework for efficient representative summarization of RDF graphs[END_REF][START_REF] Čebirić | Compact summaries of rich heterogeneous graphs[END_REF][START_REF] Goasdoué | RDF graph summarization for first-sight structure discovery[END_REF], so the authors introduce weak and strong equivalence relations that relax rather aggressively the bisimulation relation through transitive co-occurrence of edge labels, to achieve more compact graph summaries. Type hierarchies essentially collapse in summaries built on weak or strong equivalence whenever they would collapse for hybrid-learner. Actually, weak equivalence systematically collapses hierarchies (except for nodes without outgoing edges). Even these summaries may become large for big, encyclopedic graphs, such as DBPedia or YAGO. One solution they suggest is to use methods based on mining frequent patterns [START_REF] Čebirić | Summarizing semantic graphs: a survey[END_REF]. An alternative approach to such problematic graphs is to use semi automatic methods where the construction of schema is interactively guided by domain experts [START_REF] Boneva | Semi automatic construction of shex and SHACL schemas[END_REF].

Other ideas include clustering nodes according to thresholds on the number of shared edge labels [START_REF] Tsuboi | An algorithm for extracting shape expression schemas from graphs[END_REF]. In [START_REF] Arenas | A principled approach to bridging the gap between graph data and their schemas[END_REF] integer linear programming is used to optimize the tradeoff between the number of partitions and how well each partition fits to the schema, however, the fitness is defined using outbound neighborhood, and not the context. Finally, some approaches complement the structural information with types that may be already present in graphs [START_REF] Campinas | Efficiency and precision trade-offs in graph summary algorithms[END_REF][START_REF] Goasdoué | RDF graph summarization for first-sight structure discovery[END_REF] or, in the case of property graphs, by inferring the typing from node labels [START_REF] Lbath | Schema inference for property graphs[END_REF].

Among results on grammatical inference, [START_REF] Heinz | Learning in the limit with lattice-structured hypothesis spaces[END_REF] shows that a family of well-behaved inference algorithms can be interpreted as constructing a least upper bound for the input in the lattice of languages from the class, where the order is defined as the containment of languages. Our inference algorithm follows a similar approach. It does not compute a least upper bound among the whole class of graph schemas, but rather inside the lattice of the graph aggregates of the input graph (see Section 3.3).

Conclusions and future work

We have presented a principled approach to the problem of inference of shape graphs, which are a subclass of shape expression schemas for graph databases. We have employed the framework of grammatical inference to identify key challenges: identifying arities on edges and identifying recursive types. To confront these challenges we have explored an approach of inferring shape graphs using simulation relation on the nodes of the input graph. This approach addresses well the identified challenges at the price of identifying subtypes, which we argue to be a fundamental limitation. To overcome it we extend the simulation based approach with a modest amount of context information. The resulting inference algorithm allows to infer a rich class of schemas, which we argue to be of practical importance with an empirical study of real-life schemas of graph databases. Future research directions include exploring techniques for inference of disjunctions [START_REF] Boneva | Schemas for unordered XML on a DIME[END_REF] and adapting the proposed methods to the emerging standard for Property Graph Schemas. We also plan to pursue the question of inference of shape graphs from typed graphs, our preliminary results are very promising [START_REF] Groz | Inference of shape expression schemas typed RDF graphs[END_REF].

  An RDF graph (above) and its abstraction as a simple graph (below) An embedding G0 H0 (concise versions of graphs from Figure1).

Figure 2

 2 Figure 2 Graphs and embeddings.

Figure 3

 3 Figure 3 Containment does not imply an embedding: K0 and K1 are equivalent but K1 K0 and K0 K1.

Figure 4

 4 Figure 4 Aggregate of G0 by grouping P0 induced by the bisimulation relation of G0.

Figure 5

 5 Figure 5 Limit points for various subclasses of ShEx0

Figure 6

 6 Figure 6Example of inference using graph simulation. G2 ÷ P0 does not recognize G2.

Figure 7 Algorithm 1 1 : 6 : 7 :

 71167 Figure 7 Example of inference using graph simulation. G3 ÷ Pmax is overgeneralized.

2 .

 2 single choice any m and n ∈ Max such that all nodes that sim-dominate m are in P [n]. 3. all else any n ∈ Max and m ∈ N G such that m ∈ N G \ P [n] and n sim-dominates m.

Figure 8

 8 Figure 8 Determinization of a graph.

Figure 9

 9 Figure 9 Execution of hybrid-learner on G0. m n means that n sim-dominates m.

  Book → (creator : Person+ | editor : Person+), title : Literal, ref : (Article ∪ Book)*.

  Graphs for Graph Databases example for the above type definition of Book Book → creator : Person*, editor : Person*, title : Literal, ref : Article*, ref : Book*.

D T 2 0 2 2 7:4 Inference of Shape Graphs for Graph Databases

and often we use i for [i; i]. Throughout this paper, we employ the point-wise addition operation [i

1 ; j 1 ] ⊕ [i 2 ; j 2 ] = [i 1 + i 2 ; j 1 + i 2 ]. A set of intervals M is proper if any interval is contained in an interval in M .

For a proper M we define the function fit M that maps any finite nonempty set of natural numbers (occurrences) into a smallest interval in M containing it.

I C

  there exists a witness of embedding of n in m w.r.t. R, i.e., a function λ : out G (n) → out H (m) such that 1. for every e ∈ out G (n) we have that lab(e) = lab(λ(e)),

	2. for every f ∈ out H (m) we have that	{arity G (e) | λ(e) = f } ⊆ arity H (f ), where
	stands for the point-wise sum of all the intervals.

2 0 2 2 7:8 Inference of Shape Graphs for Graph Databases shape

  graph H = (N H , E H , arity H ), where

a proper set of intervals M , the aggregate of G by P w.r.t. M , in symbols G ÷ M P , is the I C D T

  it is not singular because {n 0 } G2÷Pmax* {n 2 , n 4 }. Although originally n 0 was sim-maximal, afterwards it became subsumed by the group {n 2 , n 4 }. It is then absorbed by {n 2 , n 4 } and we get the node grouping P + max = {{n 1 , n 3 }, {n 0 , n 2 , n 4 }, {str}}, which yields the singular shape graph H 2 that recognizes G 2 .

Table 1

 1 Analysis of schemas for a number of graph databases.

				Base types			Union		Clauses
		total Det σ-ind Sin CtxSin Abs	types	total	union	disj.
	Dblp	11	5	6	8	10	7	2 (3)	135	2 (9)	1
	Berlin	8	8	5	5	8	7	0 (0)	47	0 (0)	0
	Tpc-h (dm)	8	8	8	8	8	8	0 (0)	67	0 (0)	0
	Nobel	11	8	7	7	10	8	1 (0)	66	2 (0)	1
	SciGraph	18	10	16	17	18	16	1 (2)	162	1 (7)	1
	Covid19	22	11	11	19	19	19	2 (0)	295	3 (0)	0
	Yago	49	14	28	28	30	21	2 (13)	1174 4 (490)	0

This author has been partially supported by Polish National Science Center grant NCN 2016/23/B/ST6/01438.


Keywords: Health services research, clinical psychology, qualitative research, hospitals, France

staff in regards to the religious past of French hospitals, and indicate the necessity but also the caution with which research can and must investigate the weight of

Contribution à l'étude clinique des institutions de soins. Le fantasme de l'institution malfaisante A contribution to the clinical study of healthcare institutions. The « malicious institution » fantasy.

Héloïse Haliday 1

Résumé :

Cet article veut éclairer, à partir d'une recherche-action coopérative dans un CHU français, une construction mentale inconsciente à la racine du phénomène de « paranoïa institutionnelle » : le fantasme de l' « institution malfaisante ». Grâce à l'analyse thématique de plus de 80 entretiens au cours d'une enquête de terrain d'un an, nous montrons que le fantasme de l'institution malfaisante procède d'une triade d'éléments constitutifs : 1) un flou concernant l'établissement et l'incarnation de sa direction, 2) la reconnaissance de la puissance symbolique de cet établissement, notamment de son pouvoir de contrainte et 3) l'attribution par projections agressives d'intentions négatives à l'institution, qui la transforment en retour en un objet persécuteur. Ce fantasme témoigne de la persistance d'une « mystique hospitalière » chez les professionnels de soin, autrement dit d'une conception de l'hôpital empreinte d'une dimension religieuse. Nous plaidons en conclusion pour que le champ de la clinique institutionnelle continue à investiguer la vie psychique des établissements de soins, psychiatriques ou non.

Mots-clés : Clinique institutionnelle ; hôpital ; recherche qualitative ; fantasme.

Summary :

In France, the lens with which clinical psychology gazes through institutional matters seems limited to what happens between patients and professionals. It pays little interest to the interactions between the administration of the institution, i.e. organizational matters, and the daily clinical setting of mental health care. Unconscious institutional dynamics seem to receive much more attention from management sciences, which sometimes use psychoanalytical concepts to shed light on managerial and organizational problems. This article, based on an action-research study in a French university hospital, aims to shed light on one of the unconscious mental constructs which could be at the root of what several authors in psychiatry have identified as "institutional paranoia": the fantasy of a malicious institution.

We hypothesize that this fantasy, which attributes harmful intentions towards its agents to the institution, is a recurrent avatar of the typical problem institutional psychology deals with.

It is therefore even more specific to hospitals, due to the abundantly documented tensions which they have been faced during the last two decades.

We were initially appointed to conduct a "cooperative action research" project in a French University Hospital Centre between October 2018 and September 2019, in order to write a preliminary research report on the quality of working life as experienced by its personnel.

Four ethnographic qualitative research techniques were used to assess the needs of healthcare professionals : individual and group interviews with teams from all departments (health care, administrative, logistical and technical), on formal or informal times, participant observations in services which were later recorded in a written logbook, interprofessional working groups called "thematic commissions" that met for five sessions of 3 hours each and the creation of a digital "suggestion box" accessible on the hospital's intranet. Our results show the fantasy of the malicious institution deserves to be isolated due to its three constitutive elements: 1) a blurry institutional governance and incarnation of the hospital's leadership, 2) the recognition of the symbolic power of the institution, including its coercive power, and 3) the attribution of negative intentions to the institution by aggressive projections, which in turn transform it into a persecuting object. We discuss the link between the feeling of belonging to the institution and the feeling of abandonment as experienced by Introduction La clinique institutionnelle issue de la psychiatrie n'a aujourd'hui plus à prouver sa spécificité comme champ, ni son utilité comme ensemble de connaissances et de compétences à l'usage des professionnels du soin [START_REF] Drieu | 46 commentaires de textes en clinique institutionnelle[END_REF]. Il est cependant regrettable que ce corpus circonscrive la clinique institutionnelle à ce qui se passe entre patients et professionnels et n'investisse pas plus la question des interactions entre l'administration de l'établissement et la clinique quotidienne dans les soins. Les dynamiques institutionnelles inconscientes semblent faire l'objet d'une attention bien plus grande du côté des sciences du management, auxquelles sont rattachées des contributions anglo-saxonnes convaincantes usant de concepts psychanalytiques pour éclairer les problèmes managériaux et organisationnels [6 ; 32-34].

Pourtant, le lieu de prédilection historique de la clinique institutionnelle comme champ et comme corpus est avant tout l'hôpital, seule structure publique où se conjuguent deux « prendre soin » en cascade : celui des patients, redoublé par le soin à apporter à l'institution elle-même. Nous définirons pour les besoins de cet article l'établissement comme la structure concrète et administrative de l'hôpital, l'institution comme le réseau d'échanges économiques et relationnels qui s'y déploie, et l'organisation comme l'ensemble des processus conçus par ceux qui travaillent dans un établissement donné afin d'articuler les obligations réglementaires et la bonne marche des interrelations. S'il ne fait aucun doute, tant pour les chercheurs français que leurs confrères internationaux, que les structures hospitalières des pays développés ont été fortement mises au travail depuis le début des années 2000 par des demandes de reconfigurations successives visant une certaine efficience médico-économique, et si plusieurs lois récentes ont par ailleurs marqué les esprits en France2 , il reste impossible de postuler un effet direct des politiques publiques sur les organisations de travail et les pratiques de soins. Les conséquences des changements de cap au niveau national résultent de multiples transformations et adaptations des réglementations, notamment à l'échelle locale des établissements de santé eux-mêmes. Les recherches de langue française se sont ainsi appesanties sur le rôle médiateur des cadres de proximité, qui se vivent comme des jointures entre les nécessités administratives et cliniques [7 ; 9], et font état d'une souffrance au travail majorée par cette position d'entre-deux. La littérature internationale, quant à elle, montre en réalité que d'où qu'elles viennent, les personnels hospitaliers sont avant tout sensibles aux réorganisations de leurs activités lorsque celles-ci ne sont pas faites de manière concertée [START_REF] Haliday | Le management en santé au service de la qualité de vie au travail des professionnels[END_REF]. Certaines évolutions ont été plus étudiées que d'autres par les chercheurs français, notamment l'introduction de la tarification à l'activité et celle, concomitante, de l'informatique dans les services de soins [START_REF] Haliday | Comment qualifier l'impact des réformes de santé sur la qualité de vie au travail des soignants ? Leçons de l'implémentation de la tarification à l'activité et de l'informatisation des services de soins dans les hôpitaux français[END_REF]. Il est remarquable que ces choix aient portés sur l'introduction d'outils techniques : on pourrait ici supposer que les impacts tant positifs que négatifs liés aux caractéristiques intrinsèques de ces nouveaux moyens de l'activité étaient peut-être plus facilement distinctibles de la volonté ou intention des échelons managériaux que dans le cas de changements purement organisationnels. Nous mettrons quant à nous, dans le présent écrit, l'accent non sur ce que le temps long nous apprend des évolutions hospitalières, que nous pouvons et devons relier aux politiques publiques en matière de santé, mais sur la réalité psychique des personnes concernées par ces réorganisations successives. Si notre enquête est locale, nous supposons toutefois qu'elle permet quelques généralisations et hypothèses sur l'expérience subjective des professionnels hospitaliers.

Cet article souhaite plus précisément éclairer l'une des constructions mentales inconscientes qui nous paraît à la source de ce que plusieurs auteurs en psychiatrie ont repéré sous le nom de « paranoïa institutionnelle » : le fantasme d'une institution malfaisante. Nous faisons l'hypothèse que ce fantasme, qui attribue à l'institution des intentions nuisibles envers ses agents, est un avatar récurrent de la clinique institutionnelle hospitalière du fait des tensions dans lesquelles se trouvent pris les hôpitaux français. Cela nous amène à considérer que l'institution malfaisante est l'une des principales représentations contre lesquelles les administrations hospitalières doivent aujourd'hui lutter pour « prendre soin de ceux qui nous soignent »3 . Nous montrerons que le fantasme de l'institution malfaisante mérite d'être isolé au motif qu'il procède d'une triade particulière d'éléments constitutifs : 1) un flou concernant l'établissement et l'incarnation de sa direction, 2) la reconnaissance de la puissance symbolique de cet établissement, notamment de son pouvoir de contrainte et 3) l'attribution par projections agressives d'intentions négatives à l'institution, qui la transforment en retour en un objet persécuteur. Si les relations institutionnelles dans une structure donnée peuvent emprunter la voie d'une opposition entre persécuteurs et persécutés pour de nombreuses raisons différentes, nous proposerons en discussion que cette représentation est partiellement spécifique à l'hôpital en tant qu'elle s'appuie sur les reliquats de son histoire religieuse.

Méthodologie de l'étude support

Cet article tire ses conclusions d'une démarche de « recherche-action coopérative » [1 ; 5 ; 11 ; 20 ; 31] Les entretiens étaient de type exploratoire pour les groupes, à partir de la question suivante : « quels sont pour vous les thèmes à aborder dans le projet social ? ». Les entretiens individuels ou en binôme étaient semi-dirigés, assortissant la question exploratoire de départ de questions spécifiques au métier exercé par les interviewés : « comment se sent-on au CHU quand on est médecin/infirmier/cadre ? », « qu'est-ce qui manque ou pourrait être amélioré dans votre pratique ? ».

Du fait de la situation sociale délicate à l'orée de la réécriture du projet d'établissement, il a été choisi de ne pas enregistrer ces entretiens et ces focus groups mais de recourir à une prise de notes verbatim par ordinateur, après accord écrit (par mail) et oral donné par les agents. Les verbatims étaient à chaque fois mis au propre et anonymisés dans un fichier à part afin de conserver une trace de la prise initiale, puis envoyés aux personnes concernées pour relecture afin de garantir une transparence du processus. Quelques échanges par mails ont également été consignés.

C'est à partir de l'analyse thématique à laquelle nous avons procédé pour produire notre rapport de recherche que s'est imposé le thème de l'institution malfaisante, que nous présenterons donc en commentant les paroles des professionnels que nous avons rencontrés. Sur le terrain où nous avons effectué notre recherche, il nous a en effet semblé que pouvait être repéré un ensemble de personnes, qui ne faisait pas pour autant groupe (autrement dit qui n'était qu'une somme d'individus non-conscients du fait que leur sentiment vis-à-vis de l'institution était leur principal point commun), portant en eux la conviction, tirée de l'expérience mais interprétée d'une façon particulière, que l'institution disposait de multiples leviers pour aider ses personnels dont elle ne se servait volontairement pas. Ce premier constat rend difficile l'application directe de la notion d'« alliance inconsciente », très présente en psychanalyse des groupes [START_REF] Kaës | Les alliances inconscientes[END_REF][START_REF] Kaës | Un singulier pluriel: la psychanalyse à l'épreuve du groupe[END_REF], à leur situation.

Nous proposerons en discussion

Si la représentation de l'institution malfaisante dit beaucoup de celui qui la porte, elle témoigne aussi des phénomènes que peut traverser toute institution, auxquels il est par conséquent nécessaire de faire attention si l'on veut pouvoir soigner le système relationnel à des fins de diminution ou de dépassement des souffrances institutionnelles [START_REF]Dépasser les souffrances institutionnelles[END_REF]. Il serait par ailleurs erroné de prêter à l'ensemble des professionnels porteurs de ce fantasme une faible motivation pour leur activité : plusieurs personnes chez qui nous avons entendu se déplier la représentation de l'institution malfaisante étaient au contraire très engagées dans leur travail avec leurs collègues et les patients, car elles concevaient leur investissement pour les autres comme une façon de lutter contre la nuisance institutionnelle5 .

L'institution nébuleuse

Le premier prérequis au développement de la représentation de l'institution malfaisante consiste en l'absence de représentation claire et incarnée des strates décisionnaires de l'établissement. Cette absence d'incarnation de la gouvernance permet l'instauration d'un doute, chez les professionnels, sur ce qui se passe symboliquement et relationnellement audessus d'eux, autrement dit un discret changement de focale de l'établissement vers l'institution. Nous citons ici des extraits d'échanges de plusieurs participants lors d'une séance de commission thématique où la question de l'incarnation de la gouvernance a petit à petit été discutée :

« On a le sentiment qu'on est gouvernés mais c'est qui ce « il » qui a décidé que ? On a l'impression de subir de on ne sait même pas qui : on veut bien subir mais on aimerait bien savoir qui nous l'inflige quoi. Ce « il y a des choses qui sont connues de tout le monde mais qui continuent à être cautionnées » (GM3010P)

« j'ai eu une mauvaise expérience, mais il n'y a rien de fait, s'il y a des situations dangereuses, de mises en danger du personnel. Aucun soutien, voire la hiérarchie va vous enfoncer. […] Soit on se fiche des gens soit on ne voit rien. » (GM1001C) « Quand j'ai été en difficulté […] j'ai tiré toutes les sonnettes d'alarme et on m'a répondu « vous êtes mal comme tous les cadres de l'hôpital […] j'en veux énormément à l'institution, je l'avais dit je n'allais pas bien et j'étais perdue » (LM0702C)

Cela est transparent à la lecture : l'institution, si elle ne vient pas en aide à ses agents,

devient

  menée dans un Centre Hospitalo-Universitaire français au cours de l'année 2018-2019. Nous étions missionnée pour produire un rapport préliminaire à la réécriture de son projet social d'établissement, destiné à éclairer les demandes de ses agents en matière de « qualité de vie au travail ». Depuis la loi du 31 juillet 1991, les hôpitaux publics sont en effet contraints de rédiger des « projets d'établissement » comprenant a minima un projet médical, un projet de soins et un projet dit « social » -depuis la loi de modernisation du système de santé du 26 janvier 2016, ce document doit également comporter un projet psychologique. La particularité du volet social du projet d'établissement étant de concerner les conditions de travail de tous les personnels, celui-ci est auréolé d'une attente qui contient souvent en elle-même les germes de sa propre déception. Nous avons coordonné cette démarche sur la base de points systématiques avec le Directeur des Ressources Humaines et le Directeur Général. Il s'agissait de faire état des remontées du terrain obtenues grâce à un recueil de données opéré selon quatre techniques classiques de la recherche qualitative ethnographique [3] : entretiens individuels et groupaux avec les équipes volontaires, tous services confondus (soignants, administratifs, logistiques et techniques), sur des temps formels ou informels, observations participantes dans les services consignées dans un journal de bord, groupes de travail interprofessionnels dits « commissions thématiques » réunis pendant cinq séances de 3h chacune et création d'une « boîte à idées » numérique accessible sur l'intranet de l'hôpital. Au total, 82 entretiens ont été réalisés dont 11 en binôme, pour un total de 93 personnes interviewées formellement, à tous niveaux de la hiérarchie. Les réunions et immersions d'une journée dans les services sont au nombre de 26. Ces entretiens et ces réunions ont concerné les grands secteurs professionnels du CHU : personnels médicaux et paramédicaux, personnels administratifs (dont équipe de direction), personnels logistiques et techniques. A ces rencontres sont venues s'ajouter les séances de focus groups dits « commissions thématiques », qui ont au total rassemblé plus d'une quarantaine de membres actifs.

  et conclusion une piste d'explication à l'intensité des projections agressives et de la déception des professionnels vis-à-vis de cette structure particulière qu'est l'hôpital public. Un type particulier de paranoïa institutionnelle : le fantasme de l'institution malfaisante Cet article souhaite s'insérer dans l'histoire des réflexions sur un phénomène repéré dans le champ psychiatrique sous le nom de « paranoïa institutionnelle ». La notion de paranoïa institutionnelle est particulièrement intéressante en ce qu'elle décrit une ambiance collective spécifique en contexte de soins psychiatriques et généraux : si elle est majoritairement mentionnée par des auteurs situés dans le champ de la santé mentale [23-24 ; 26-27], elle apparaît aussi du côté des travaux sur le burn-out et la santé au travail à l'hôpital [8]. Cette notion ne fait toutefois jamais l'objet d'une définition propre ou d'une explicitation conceptuelle, encore moins d'études de cas ciblées qui permettraient d'en cerner les coordonnées principales. La seule élaboration complète que nous ayons trouvé sur le sujet provient d'un article tapuscrit du psychiatre Nicholas Fish daté de 1972 : « Un leadership faible ou inefficace peut engrainer la paranoïa institutionnelle. Un manque de communication entre les personnels de l'association [NB : au sens large du terme] la nourrit. Les insécurités personnelles des membres servent souvent de facteurs causaux […] » 4 [12].

L

  'institution malfaisante L'usage du terme « malfaisant » se réfère moins aux actes concrets quotidiens organisés par les managers du CHU (et notamment son équipe de direction) qu'à l'intention qu'ont fini par lui supposer certains agents, de façon plus ou moins consciente, et derrière laquelle se cache un processus de personnification de l'établissement et un mécanisme projectif destiné à supporter l'agressivité montante envers l'employeur. Nous suivrons le fil freudien tenu par Paul-Claude Racamier, selon lequel les « machines institutionnelles » sont de véritables organismes, des « individualités collectives » [28] 7 . Fantasmatiquement, l'institution dans son ensemble possède une individualité ; il peut par conséquent lui être supposé une intentionnalité propre. Cette supposition d'intentionnalité est essentielle, car si elle est soutenue par les actes et les expériences vécues, elle relève avant tout de l'activité de représentation fantasmatique et d'interprétation subjective par les agents de la réalité établissementale. L'idée que l'institution ne veut pas faire s'enracine, nous semble-t-il, dans un motif communément déplié par les professionnels porteurs de la représentation de sa malfaisance : « Si je dis, de toute façon ça ne sert à rien » (GM1212RU-2), formulation emblématique de la notion de « silence organisationnel » [19 ; 25 ; 35]. Ce silence, s'il est le plus souvent défini comme l'ensemble des attitudes des personnels d'une structure donnée, est en réalité luimême vecteur d'une conception personnifiée des organisations. Les vécus et les discours que nous rapportons ci-dessous représentent à notre sens la formulation aboutie du fantasme de l'institution malfaisante. Ils offrent une piste de recherche intéressante en ce qu'ils questionnent la corrélation possible entre vécu de mal-être individuel et probabilité d'être mu, à son insu parfois, par le fantasme de l'institution malfaisante. Beaucoup des professionnels qui nous ont parlé ainsi avaient derrière eux l'histoire d'une ou plusieurs alertes lancées, pour eux ou pour les autres, qui n'avaient pas été suivies d'effet :

  l'institution malfaisante, et corresponde alors bien à la définition d'une alliance inconsciente, à savoir une « formation psychique intersubjective construite par les sujets d'un lien et d'un ensemble[…] pour renforcer en chacun d'eux certains processus, certaines fonctions ou certaines structures dont ils tirent un bénéfice tel que le lien qui les conjoint prend pour leur vie psychique une valeur décisive »[START_REF] Kaës | Les alliances inconscientes dans Depuis qu'Otar est parti[END_REF]. Cette supposition se heurte toutefois au poids que peut prendre la vulnérabilité de chacun dans sa sensibilité à la représentation de l'institution malfaisante. Si certaines caractéristiques individuelles, notamment l'estime de soi basée sur la performance au travail, sont considérées comme des facteurs individuels prédictifs d'un risque de burnout plus élevé[START_REF] Langballe | The Predictive Value of Individual Factors, Work-Related Factors, and Work -Home Interaction on Burnout in Female and Male Physicians : A Longitudinal Study[END_REF], nous pouvons, à la lumière de nos développements, faire l'hypothèse qu'une expérience de burnout non-élaborée serait un facteur augmentant la probabilité de développer la conviction de travailler pour une institution aux intentions nuisibles.Conclusion. Vers une administration des soins informée de la clinique institutionnelle ?Nous avons tenté de montrer, dans cet article, que l'on peut repérer, au moyen d'une écoute clinique, des mouvements psychopathologiques particuliers dans les liens entre un établissement de soins et ses professionnels. Afin d'éclairer et d'approfondir la notion de « paranoïa institutionnelle », qui émane du champ de la psychiatrie mais semble pouvoir s'appliquer aux autres disciplines dans le monde de la santé, nous avons proposé qu'un phénomène spécifique pouvait être isolé, consistant en le fantasme que l'institution hospitalière serait malfaisante, autrement dit mal intentionnée envers ses professionnels. Cet avatar de la paranoïa institutionnelle donne des clés de compréhension des dynamiques institutionnelles dans les établissements de santé, qui ouvrent la voie à un dialogue avec les sciences de gestion et les administrations hospitalières. Loin de la définition trop stricte qu'a pris l'innovation aujourd'hui -celle d'un impératif permanent de nouveauté -, peut-être fautil considérer que la transposition de concepts issus de la clinique psychiatrique pour l'analyse institutionnelle des relations dans des contextes de soins peut avoir des effets de nouveauté, en tant qu'elle trace un chemin de recherche et d'action supplémentaire pour faire valoir les connaissances et compétences organisationnelles issues du monde psychiatrique aux autres disciplines médicales et aux administrations hospitalières.Remerciements : L'auteure remercie chaleureusement MM. Didier Hoeltgen et Jean-François Tirefort ainsi que l'ensemble des équipes qui ont participé à l'aventure de ce rapport de recherche, tout particulièrement les professionnels engagés dans les commissions thématiques.Liens d'intérêt : Pour réaliser sa mission, l'auteure a été recrutée comme psychologue clinicienne rattachée à la DRH du CHU de Clermont-Ferrand.

  « il » il prend un peu ses responsabilités : quand vous tapez à une porte ce n'est pas « il » qui va ouvrir ! […] quand « il » est décidé quelque chose c'est qui qui décide ? […]vu d'en bas ce n'est pas clair et on a l'impression qu'on essaye de nous flouter parce que c'est tellement flou qu'on râle après notre cadre car c'est qu'un rouage du service public. Il semble pourtant que l'institution, aux yeux des agents, n'a en rien perdu de sa puissance. Cette reconnaissance de la puissance symbolique de l'institution est à notre sens le deuxième prérequis du fantasme de l'institution malfaisante.

	« on nous dit « vous faites comme ça, point final ». Ca, ça n'améliore pas la « En tant que chef de service, je ne suis pas récepteur par défaut de
	façon de voir l'hôpital » (GM0605PH) l'information. Ce circuit de l'information, est-ce de la négligence ou de
	« il y a l'art et la manière et des fois la manière n'a pas été bonne, a eu l'intentionnalité ? […] » (HE2002PH).
	l'effet inverse [de celui] escompté » (LM0702C)
	Ainsi, si l'institution peut mais qu'elle ne fait pas, le doute s'introduit quant à ses « je ne connais pas les raisons de l'institution mais ils ne se rendent pas répondait du côté des agents l'impression de n'être pas vus par l'institution. Il est bien évident que l'établissement ne peut pas, objectivement, s'adresser à chacun de ses agents compte que c'est difficile pour les agents qu'il n'y ait pas de mobilité. C'est quasiment maltraitant » (GM3001C) intentions (« il y a des choses qui sont oubliées, mais exprès […] on se demande si des fois ce
	L'institution puissante n'est pas voulu », GM1405IM). Le dernier pas vers la représentation de l'institution
	individuellement, sauf à quelques occasions particulières (concours, promotion, retour à
	malfaisante consiste en la transformation du doute en l'attribution à cette institution d'une Les personnels reconnaissent donc le pouvoir symbolique de l'institution (« vous faites l'emploi) et à travers les personnels dédiés à ces activités ainsi qu'à l'encadrement. Lorsque C'est en discutant avec un chef de service que nous avons entendu l'importance de intention, d'une volonté de ne pas faire, qui découle à notre sens d'une projection de ça, point final »), ce qui peut les amener, si elle utilise trop sa force de contrainte, à concevoir nous posions la question de comment les agents se sentaient au CHU, ceux-ci nous offraient cette deuxième dimension du problème : l'agressivité des professionnels sur l'objet institutionnel.
	souvent des réponses similaires :
	« un pion dans cette immense machine » (HE0907RU)
	Tous les extraits cités ci-dessus font implicitement ou explicitement référence à une
	personnification de l'institution, c'est-à-dire à l'attribution à cette même institution d'une
	« On ne voit jamais les directions. Sur le fil il y a une coupure, mais ça ne date pas d'hier » (GM2103PH) intentionnalité corrélative à la reconnaissance de sa puissance. L'institution peut, et
	« l'institution elle est loin de nous, on ne rencontre jamais les directeurs de professionnels. L'institution bénéficie également d'une puissance de contrainte dont l'institution peut donc vouloir. Dans un contexte où la puissance institutionnelle n'est pas en
	toute façon, quand on les rencontre c'est qu'ils le demandent pour faire un point à leur arrivée mais on n'a pas de contacts » (GM0605PH) l'utilisation n'est jamais anodine : cause, c'est alors l'inertie organisationnelle qui amène les personnels à la représentation
	complète d'une institution malfaisante :

le seul visage qu'on a ! » (compte-rendu de commission CT32305S4)

Le champ lexical de la vision et du flou a également été utilisé dans d'autres espaces de parole, individuels comme de groupe (« Une sensation de brouillard, de flou… », GM0304PH ; « en bas on est dans le brouillard complet », GM0712RU). Celui-ci nous paraît plaider en faveur d'une interprétation en termes de défaut d'incarnation. Plusieurs professionnels nous ont d'ailleurs exprimé leur principale réclamation vis-à-vis des directions en ces termes :

« les directeurs on ne les voit pas, on ne sait pas qui c'est… » (GM0304PH)

A ce manque de visibilité, qui s'ajoute au manque de « lisibilité » des politiques institutionnelles (« ce n'est jamais personne […] comme une direction qui va dire « ce n'est pas nous, c'est le DG ». Et du coup ça quoi ça sert de lui parler si ce n'est pas lui ? », GM0406RU),

« on est des cases, des numéros » (HE1403PH) « on est un matricule, on est un numéro […] On est interchangeables, on nous le fait bien sentir » (GM2802RU)

Les occurrences de cette impression de ne pas compter pour l'institution (« Je ne me sens pas pris en compte par l'institution. La direction, à partir du moment où vous sollicitez quatre fois la direction ou le directeur depuis 2004 et qu'on n'a jamais daigné vous faire une réponse… » HE2805PH) ont été multiples, concernant des thématiques variées. Ne pas être correctement vu, donc accueilli, peut ouvrir un vide là où aurait dû se situer le sentiment d'appartenance. Se sentir contraint à la mobilité ou à la polyvalence occasionne pour le sujet qui le vit ainsi la réduction de son être à un corps et une force de travail alors dissociés de sa subjectivité ; ne pas bénéficier d'espaces de discussion et de concertation avec la hiérarchie amène les agents à conclure que leur voix ne peut structurellement pas être écoutée ; être rappelé sur ses congés afin de boucher un trou dans le planning fait ressentir à l'agent qu'il n'est « L'institution ? Impuissante non, elle a compris qu'elle ne l'était pas, mais inerte. La Direction des Affaires Médicales a compris qu'il n'y avait pas d'impuissance, mais il y a une immense inertie qui n'est pas la leur, qui est celle de l'institution […] » (GM0306PH) Si l'institution possède encore une certaine puissance et que l'inertie n'est pas celle de la direction à laquelle il répond, c'est qu'alors l'institution possède une vie propre qui va audelà de celles des organes administratifs repérés que sont les directions fonctionnelles. On pourrait ici comprendre la puissance dans son sens philosophique, celui de « capacité ou faculté actuelles d'accéder à une certaine forme d'être » 6 . Autrement dit, convoquer la notion de capacité de l'institution, de pouvoir ou de puissance implique qu'on lui suppose une existence propre : elle se trouve ainsi personnifiée dans les représentations que s'en font les l'ensemble des relations de pouvoir comme un « un jeu de dupes, puisqu'on n'a pas le contrôle » (HE2002PH). Mais plus encore, la supposition que les dés sont pipés dans la relation entre les personnels et l'institution, lorsqu'elle occasionne des décisions qu'ils ne comprennent pas, renforce les doutes que les agents entretiennent quant à ses intentions : « aujourd'hui on est très méfiants sur tout ce qu'on peut nous proposer, on se dit « qu'est-ce qu'il y a derrière, sur quoi on va se faire avoir ? » (GM2304PH) « L'objectif de l'hôpital est de ne pas être emmerdés […] l'information n'arrive pas mais c'est volontaire » (HE1403PH)

  une entité abandonnique. C'est ce sentiment de n'avoir pas été soutenus qui occasionne chez les professionnels douleur et rancune envers cette nébuleuse inerte : « Mais abandonner les siens à leur sort. Une identification entre personnes porteuses de cette même représentation devient alors possible, qui soude parfois une équipe contre son persécuteur désigné. Loin de nous l'idée, toutefois, que cette représentation est irréversible. l'attachement particulier des professionnels de soins à l'hôpital, de ce que l'on pourrait appeler une « mystique hospitalière française », donnant à ce type d'établissement un semblant de « substitut de collectivité religieuse se surinvestissant dans l'appartenance[…] devient alors un objet à attaquer ou à fuir (nous faisons ici référence aux travaux de Wilfried Bion sur les petits groupes[START_REF] Bion | Recherches sur les petits groupes[END_REF]), tandis qu'un nouveau groupe de référence doit être trouvé pour compenser le sentiment d'abandon vécu vis-à-vis de l'établissement. Il n'est pas impossible que ce nouveau groupe se constitue par contagion de la représentation de

	La qualification de l'établissement par des métaphores chargées d'affects et
	d'angoisse indique bien à quel point les professionnels se sentent avant tout récipiendaires de
	l'agressivité de l'institution (« il faut arrêter de penser qu'il y a des abrutis à tous les niveaux et
	la perte du sens du travail ou la douleur n'est pas immédiatement lié aux émotions lourdes à qui sont incapables de penser » (HE1312RU) ; « le CHU fonctionne parce que les cadres sont là, Bien au contraire : elle invite l'institution à travailler la valeur symbolique de ses actions. » [29].
	gérer mais au fait que les décisions ne font pas sens […] c'est important de savoir que il faut arrêter de penser qu'ils sont débiles, incompétents, feignants » (GM0712RU)), ce qui C'est bien, nous semble-t-il, la question de l'appartenance à l'institution qui est mise
	l'institution peut soutenir » (GM3001C). C'est, pensons-nous, la douleur de l'abandon qui justifie à leurs yeux, dans un deuxième temps, l'adoption de stratégies défensives. Deux en question dans le fantasme de l'institution malfaisante : si l'hôpital peut nuire à ses
	génère chez certains professionnels des sentiments de colère et d'agressivité qui sont Discussion. L'institution malfaisante, envers d'une mystique professionnels, rencontrés à plusieurs mois d'écart et qui ne se connaissaient pas, nous ont hospitalière française ? soignants, il
	projetés et leur reviennent, pour reprendre les mots de Lacan sur la structure de la proposé des interprétations qui semblaient valider cette hypothèse. Leurs réflexions, que
	persécution paranoïaque, « sous une forme inversée » [21]. nous reproduisons ci-dessous, sont précieuses pour comprendre les deux ressorts principaux
	La variété des métaphores utilisées pour désigner l'établissement nécessite d'ailleurs de la propagation de cette représentation de l'institution malfaisante :
	une attention toute particulière, car les représentations convoquées charrient avec elles des « Ils [mes collègues] se trompent de cible : ils sont en colère contre le CHU…
	on met tout sur le dos du CHU et du directeur et on ne va jamais prendre sa
	sous-textes fort différents et peuvent donner la mesure des ressentis d'un agent. Ainsi une responsabilité. […] C'est comme si leur colère, il y a quelque chose qui est
	infirmière nous a-t-elle dit en entretien : « Dans mon schéma à moi l'hôpital était une famille décentré, comme si c'est l'employeur qui est la cause de leur mal être » « Dieu peut, de potentia absoluta, mentir, voler ou tuer, damner les élus et sauver les (GM1807I) damnés, faire que le mal soit bien ou que la contradiction soit. La puissance absolue est
	« Les gens arrivent à avoir une vision assez négative du CHU et il y a un excédentaire à toute loi, logique, morale, ou physique. […] Ce que par elle il peut, Dieu, et je faisais tout pour cette famille et ils m'ont déçue », avant de comparer le CHU à une bouche-à-oreille dont les gens ne prennent pas conscience. [Exemple d'une cependant, ne le veut ni ne le fait. La puissance absolue est donc une puissance inactive, non
	va travailler elle a pollué négativement une dizaine de personnes. Le monde « pieuvre » et à un « rouleau compresseur » (GM0602I). Une ancienne recrue du CHU soignante] Par une non réponse institutionnelle dans ses besoins lorsqu'elle opératoire, mais non pas impuissante » [2]
	hospitalier parle beaucoup entre eux et on véhicule des choses qui sont rencontrée par hasard en ville avait quant à elle fait référence à une « mâchoire en fer », et négatives » (GM1211ASO)
	une autre professionnelle encore, rencontrée en réunion, avait utilisé la métaphore de la Il est aujourd'hui admis comme une évidence qu'exercer à l'hôpital n'a plus rien à voir
	famille maltraitante : avec son passé religieux, et qu'à l'acceptation d'un don de soi absolu seraient venus se
	Le premier extrait confirme la dimension projective nécessaire à la construction d'un
	substituer des calculs plus rationnels, la recherche d'un meilleur équilibre entre vie
	« J'ai l'impression qu'on met le doigt sur l'institution comme une famille : tel fantasme : l'institution, parce qu'elle est nébuleuse, floue, lointaine, est le réceptacle idéal l'institution parentifiée, les parents qui ne tiennent pas la route. […] En ce professionnelle et vie privée. Le soignant d'aujourd'hui, au sens large du terme (nous
	sens-là il y a une sorte d'institution maltraitante, une confusion des places, d'une colère déplacée. Le second extrait appuie quant à lui sur la dimension contagieuse de des genres, des générations, il n'y a pas de consistance de la hiérarchie » englobons là toutes les catégories professionnelles qui prennent soin des patients), ne
	(GM0406RU) cette représentation : si l'institution est une entité abstraite pour la plupart les agents, il n'est
	souhaite plus voir son désir de travailler dans le milieu hospitalier confondu avec une vocation

pas difficile que les difficultés vécues par un collègue instillent chez d'autres le doute essentiel à l'activité interprétative qui fera de chaque inaction du CHU l'effet et la preuve de son intention d'Cette façon de penser et fantasmer la puissance institutionnelle nous a rappelé la question, fort ancienne en théologie, de l'impuissance de Dieu. Nous citons ici un paragraphe de la philosophe Gwénaëlle Aubry afin de faire entendre la similitude des formulations de ces deux questions : d'abnégation. Pourtant, comme le soulignait récemment Philippe Rault-Doumax dans un ouvrage sur les partenariats entre cliniques privées et hôpitaux publics, il subsiste quelque chose, dans

Maître de conférences, Université de Bourgogne, Laboratoire Psy-DREPI EA7458. Heloise.haliday@u-bourgogne.fr

On citera par exemple la loi n° 2016-41 du 26 janvier 2016 dite de modernisation de notre système de santé, qui a introduit l'exigence d'un regroupement des établissements hospitaliers en GHT ; on pensera également, moins récemment, à la loi n° 2009-879 du 21 juillet 2009 portant réforme de l'hôpital et relative aux patients, à la santé et aux territoires, dite loi HPST, ayant présidé à la réunion des services en pôles, entités destinées à faciliter la gestion organisationnelle et budgétaire des activités.

Nous nous référons ici à la Stratégie Nationale de Santé lancée en décembre 2016 par Marisol Touraine.

Nous traduisons.

Certains cadres notamment ont insisté pour dire qu'ils travaillaient pour leurs agents et les patients, mais pas pour l'établissement.

Nous nous référons au Centre de Ressources Textuelles et Lexicales du CNRS : https://www.cnrtl.fr/definition/puissance. Consulté le 15/08/19.

L'idée qu'une « foule » peut être dotée d'attributs individuels était déjà présente chez Freud dans Psychologies des foules et analyse du Moi[START_REF] Freud | Psychologie des foules et analyse du moi[END_REF].