Cyrille Garnier

Fatma Briki

Brigitte Nedelec

Patrick Le Pogamp

Ahmet Dogan

Nathalie Rioux-Leclercq

Renan Goude

Caroline Beugnet

Laurent Martin

Marc Delpech

Frank Bridoux

Gilles Grateau

Jean Doucet

Philippe Derreumaux

Sophie Valleix

VLITL is a major cross-beta-sheet signal for fibrinogen A alpha-chain frameshift variants

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

Introduction

Fibrinogen is a 340-kDa glycoprotein, composed of two identical heterotrimers, each consisting of one Aα, one Bβ, and one γ-chain. [START_REF] Weisel | Mechanisms of fibrin polymerization and clinical implications[END_REF] Mutations altering any of these three chains are commonly associated with autosomal or recessive bleeding/thrombotic disorders (http://site.geht.org/base-fibrinogene/ ) without any clinical evidence of amyloidosis. However, a small fraction of Aα-chain variants are amyloidogenic and lead to massive Aα-chain deposition as amyloid fibrils in AFib-patient's kidneys. The first case of fibrinogen Aα-chain-derived amyloidosis (AFib) has been described by Benson in 1993, [START_REF] Benson | Hereditary renal amyloidosis associated with a mutant fibrinogen alpha-chain[END_REF] and until now, only the Aα-chain has been linked to AFib (http://amyloidosismutations.com/mut-afib.php). AFib is a rare, late-onset, autosomal dominant condition characterized by massive amyloid deposition in the glomerular compartment of the kidney. [START_REF] Benson | Hereditary renal amyloidosis associated with a mutant fibrinogen alpha-chain[END_REF] Heterozygous AFib-patients typically display a chronic kidney disease in the fourth/fifth decade of life leading to progressive end-stage renal failure. [START_REF] Gillmore | Diagnosis, pathogenesis, treatment, and prognosis of hereditary fibrinogen A alpha-chain amyloidosis[END_REF] Though amyloid mechanisms involved in AFib are still unknown, it was shown that AFib-fibrils were exclusively composed of the mutant Aα-chain, [START_REF] Benson | Hereditary renal amyloidosis associated with a mutant fibrinogen alpha-chain[END_REF][START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] suggesting that the wild-type Aα-chain does not contribute to amyloid deposition, analogous to what it was previously observed in patients with familial lysozyme, β2-microglobulin, and apoC-III amyloidosis. [START_REF] Valleix | D25V apolipoprotein C-III variant causes dominant hereditary systemic amyloidosis and confers cardiovascular protective lipoprotein profile[END_REF][START_REF] Valleix | Hereditary systemic amyloidosis due to Asp76Asn variant β2-microglobulin[END_REF][START_REF] Pepys | Human lysozyme gene mutations cause hereditary systemic amyloidosis[END_REF] The therapeutic approach of AFib consists only in supportive treatment by dialysis and by renal or combined hepatorenal transplantation. Recently, Benson's group suggests that preemptive hepatic transplantation may avert the progression of renal damage and may be a promising treatment for AFib prior to the need for renal dialysis or kidney transplantation. [START_REF] Fix | Liver transplant alone without kidney transplant for fibrinogen Aα-chain (AFib) renal amyloidosis[END_REF] Although the first case of AFib was recognized more than 20 years ago, we still do not know which specific part of mutant Aα-chain sequences directly participates in the β-aggregation process. To date, a total of 15 Aα-chain variants are known to be amyloid-prone in humans, and remarkably these amyloidogenic variants are all clustered in a small portion of Aα-chain from residues 517 to 555. [START_REF] Benson | Hereditary renal amyloidosis associated with a mutant fibrinogen alpha-chain[END_REF][START_REF] Gillmore | Diagnosis, pathogenesis, treatment, and prognosis of hereditary fibrinogen A alpha-chain amyloidosis[END_REF][START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF][START_REF] Rowczenio | Online registry for mutations in hereditary amyloidosis including nomenclature recommendations[END_REF][START_REF] Kang | Hereditary amyloidosis in early childhood associated with a novel insertion-deletion (indel) in the fibrinogen Aalpha chain gene[END_REF][START_REF] Uemichi | Hereditary renal amyloidosis with a novel variant fibrinogen[END_REF][START_REF] Uemichi | A frame shift mutation in the fibrinogen A alpha chain gene in a kindred with renal amyloidosis[END_REF][START_REF] Yazaki | The first pure form of Ostertag-type amyloidosis in Japan: a sporadic case of hereditary fibrinogen Aα-chain amyloidosis associated with a novel frameshift variant[END_REF] Missense Aα-chain variants have been reported in several AFibfamilies worldwide, with Glu526Val being the most common amyloidogenic Aα-chain variant. [START_REF] Rowczenio | Online registry for mutations in hereditary amyloidosis including nomenclature recommendations[END_REF] In contrast, amyloidogenic Aα-chain frameshift variants are "private" -ie that each of them has been reported in only a single family, and therefore available clinical information associated with these variants is very limited. [START_REF] Gillmore | Diagnosis, pathogenesis, treatment, and prognosis of hereditary fibrinogen A alpha-chain amyloidosis[END_REF][START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF][START_REF] Kang | Hereditary amyloidosis in early childhood associated with a novel insertion-deletion (indel) in the fibrinogen Aalpha chain gene[END_REF][START_REF] Uemichi | A frame shift mutation in the fibrinogen A alpha chain gene in a kindred with renal amyloidosis[END_REF][START_REF] Yazaki | The first pure form of Ostertag-type amyloidosis in Japan: a sporadic case of hereditary fibrinogen Aα-chain amyloidosis associated with a novel frameshift variant[END_REF] Two of them have exceptionally been associated with pediatric AFib-cases, [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF][START_REF] Kang | Hereditary amyloidosis in early childhood associated with a novel insertion-deletion (indel) in the fibrinogen Aalpha chain gene[END_REF] suggesting that frameshifts may be particularly aggressive and likely highly prone to self-aggregation; therefore, it is of particular interest to investigate the precise mechanisms responsible for their amyloidogenicity.

We report a novel "private" amyloidogenic Aα-chain frameshift variant (c.1620delT/Phe521Leufs) and show that renal fibrils of AFib patients are composed of a short polypeptide derived from the C-terminal part of the Phe521Leufs Aα-chain without evidence of a wild-type counterpart. This additional confirmation of what part of the mutant Aα-chain is deposited in the disease tissue of AFib-patients prompted us to explore how the mutant Phe521Leufs-chain contributes to Aα-chain amyloid formation.

Materials and methods

Genetic analysis

Blood samples from the family members were obtained after their written informed consents.

This study had the approval of the Ethics Committee of the Hospital of Rennes and was performed according to the Declaration of Helsinki. The entire coding region and flanking splice sites of exon 5 of FGA were sequenced as previously described. [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] The nomenclature of the fibrinogen Aα-chain deletion is based on the FGA transcript reference (NM_000508.3). For more clarity with the historically conventional nomenclature, the FGA variant is described as Phe521Leufs according to the mature protein without the signal peptide. According to the recommended Human Genome Variation Society (HGVS), which starts the amino acid numbering at the initiator methionine, Phe521Leufs corresponds to Phe540Leufs. In Table 1, all amyloidogenic Aα-chain frameshift variants are listed with the two nomenclatures. To convert the conventional mature protein amino acid numbering to the HGVS nomenclature, add 19 nucleotides for Aα-chain changes.

Histology and transmission electron microscopy of renal biopsies

Renal biopsies were processed according to standard techniques, as previously described. [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] Immunostaining for the specific antibody (rabbit polyclonal antibody from Dr. Merrill Benson, 1:100) corresponding to the abnormal fibrinogen Aα-chain (GAQNLASSQIQRN) was performed, as previously described. [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] Laser microdissection and tandem mass spectrometry (LMD/MS) analysis

The LMD and LC-MS/MS methods have been previously summarized in full text. [START_REF] Sethi | Laser microdissection and mass spectrometry?based proteomics aids the diagnosis and typing of renal amyloidosis[END_REF] In silico tools AMYLPRED2 is a consensus algorithm for prediction of amyloidogenic determinants combining 11 different methods, available at http://biophysics.biol.uoa.gr/AMYLPRED2/). [START_REF] Tsolis | A consensus method for the prediction of "aggregation-prone" peptides in globular proteins[END_REF] The cross-β TANGO score results from a statistical mechanics model based on simple physico-chemical principles of secondary structure formation. [START_REF] Fernandez-Escamilla | Prediction of sequencedependent and mutational effects on the aggregation of peptides and proteins[END_REF] The PASTA energy is indicative of the aggregation propensity and predicts which portions of the sequence are more likely to stabilize the cross-ß core of fibrillar aggregates. [START_REF] Walsh | PASTA 2.0: an improved server for protein aggregation prediction[END_REF]

Fibril formation

All five synthetic peptides were purchased from genepep prestation, France, and stock solutions were prepared at the final concentration of 2 to 6 mM and stored at -20°C. Fibril formation was induced in 10 mM MOPS buffer, 150mM NaCl, pH 7.2 at a final peptide concentration ranging from 0.125 to 1mM. Peptide solutions were incubated at room temperature without agitation or adjuvants from one day to two months.

Fluorescence experiments 100µL of the five peptides were added to 900 µL of fibrillation buffer containing Thioflavin T (5 µM final concentration). Fluorescence was measured with a Perkin-Elmer Luminescence Spectrometer LS55 with slit widths of 10 nm. The excitation was at 450 nm and emission spectra of ThT were recorded from 470 to 600 nm.

Transmission electron microscopy of aggregates formed in vitro

Aliquot of the five peptides (10 µl with a concentration of ~10mg/ml) were placed on carboncoated copper grids (300 mesh), washed and negatively stained for 1min with 1% (wt/vol) uranyl acetate, and wicked dry prior to analysis using a Philips CM12 transmission electron microscope operating at accelerating voltages of 120 kV.

X-ray microdiffraction experiments performed on in vitro aggregate samples and on ex vivo renal fibrils

All samples were pelleted by centrifugation at 5000g for 10 min. Small concentrated drops of samples were deposited on cylindical fibres of about 100µm diameter. X-ray microdiffraction was performed at the ESRF-European Synchrotron Radiation Facility (Grenoble, France) on the microfocus beam line ID13, as previously described. [START_REF] Briki | Synchrotron x-ray microdiffraction reveals intrinsic structural features of amyloid deposits in situ[END_REF]

Results

Phe521Leufs is a novel amyloidogenic « private » frameshift variant of fibrinogen Aα-chain associated with a severe form of renal amyloidosis Amyloidosis was initially diagnosed from a 27-year-old woman (patient I.1) who presented proteinuria (1.30 g/L) during routine medical screening at her first pregnancy (Figure 1A). Progressively, she developed nephrotic syndrome without hypertension (120/80 mmHg). On physical examination, she had no signs of peripheral or autonomic neuropathy, and all cardiac investigations were normal. A renal biopsy was performed and amyloidosis was diagnosed, but the etiology of her renal amyloidosis remained undetermined. Three years later, this patient was diagnosed with malignant hypertension (210/130 mmHg), and was treated with transfusion of fresh frozen plasma and association of several anti-hypertensive drugs, resulting in adequate control of blood pressure. However, she continued to develop uremia leading to acute renal failure requiring hemodialysis. One year later, she underwent her first renal transplantation, but amyloidosis recurred on the renal graft five years later, and she received her second renal graft. The etiology of this renal amyloidosis was reevaluated when one of her daughter (II.2) began to manifest proteinuria at 22-years old associated with glomerular amyloid deposits. This proband's daughter also developed an acute episode of malignant hypertension leading to acute renal failure and hemodialysis. In both of these affected AFib-probands, there was no history of bleeding or thrombotic disorders (even during surgical procedures and during the nephrotic phase), and all routine coagulation investigations were normal including Clauss fibrinogen activity level, fibrinogen antigen level, activated partial thromboplastin time, prothrombin time, thrombin time, and reptilase time, indicating absence of significant quantitative or qualitative fibrin clot abnormalities. Finally, hereditary AFib was confirmed on the basis of history of renal disease in two family members, documented evidence of renal dysfunction secondary to Congo red amyloid deposits in glomeruli, histological evidence of amyloid fibrils at electron microscopy, immunohistochemistry of renal biopsies, and detection of FGA mutation (Figures 1A-E). The two AFib-probands (I.1 and II.2) were heterozygous for a novel single base pair deletion (c.1620delT), expected to alter the reading frame of the Aα-chain mRNA at codon 521: Phe521Leufs (numbering according to the mature protein) or Phe540Leufs (according to the recommended HGVS nomenclature, including the signal peptide). This mutation was not detected in family members II.1 and II.3 who had no proteinuria, confirming that this novel Aα-chain variant segregated with renal disease in this kindred (Figures 1A and1E). This thymine deletion is expected to cause loss of the last C-terminal 62 amino acids of the wild-type Aα-chain and, instead, the incorporation of 27 new residues (521-LSVRLSLGAQNLASSQIQRNPVLITLG-547) before premature termination of the translation at codon 548 (Figure 1D and Figure 2B). Therefore, the genetic data were concordant with immunohistochemistry analysis showing that the Congo red glomeruli deposits positively stained with a specific antihuman Aα-chain monoclonal antibody that recognized the mutant C-terminal portion of all amyloidogenic frameshifts (Figure 1D). [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] Sequence alignment of Phe521Leufs with amyloidogenic Aα-chain frameshift variants reported thus far showed that all invariably truncate at codon 548, producing highly similar mutant C-terminal sequences with a common portion of 15 amino acids, ASSQIQRNPVLITLG, residues 533-547 (Table 1).

The C-terminus end of Phe521Leufs chain constitutes amyloid fibrils in vivo

To determine which part of the Aα-chain contributes to the formation of amyloid fibrils, renal deposits from proband II.2 were extracted by laser-microdissection/liquid chromatography and tandem mass spectrometry (LMD/MS), [START_REF] Sethi | Laser microdissection and mass spectrometry?based proteomics aids the diagnosis and typing of renal amyloidosis[END_REF] and the Phe521Leufs amyloid proteome was compared to the proteome obtained from AFib patients carrying the Glu526Val missense variant, the most common amyloidogenic Aα-chain variant.

Several independent samples (replicates) were analyzed for Phe521Leufs and Glu526Val variants. For both variants, the amyloid proteome profile indicated that Aα-chain showed the highest probability score in the deposits and the signature proteins (SAP and apoE) were present, giving confidence in the identification of amyloid (Figure 2A). Peptides corresponding to the new C-terminal sequence of Phe521Leufs were detected only in the case carrying this mutation and not in Glu526Val cases (Figure 2A). Detailed examination of the protein coverage of Phe521Leufs showed that the amyloid peptide contained all of the modified C-terminal sequence encoded by the Phe521Leufs allele (100% coverage) but not the wild-type C-terminal Aα-chain sequence after residue 521 (Figure 2B). In conclusion, the amyloid peptide characterized in Phe521Leufs deposits was a hybrid 49-mer fragment with the first 22 residues identical to the wild-type Aα-chain residues 499-520 (AFFDTASTGKTFPGFFSPMLGE), and the Cterminal 27 residues corresponding to the sequence encoded by Phe521Leufs (LSVRLSLGAQNLASSQIQRNPVLITLG) (Figure 2B). Therefore, our amyloid proteome analysis indicated that wild-type Aα-chain does not contribute to amyloid formation, and that only the C-terminal sequence generated by the Phe521Leufs allele is amyloid in vivo, a finding consistent with previous publications. [START_REF] Benson | Hereditary renal amyloidosis associated with a mutant fibrinogen alpha-chain[END_REF][START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF][START_REF] Yazaki | The first pure form of Ostertag-type amyloidosis in Japan: a sporadic case of hereditary fibrinogen Aα-chain amyloidosis associated with a novel frameshift variant[END_REF] VLITL is predicted to be a major cross-β-sheet signal of Phe521Leufs chain To explore why the mutant Phe521Leufs sequence contributes to amyloid formation, we first performed in silico analyses on the full-length sequences of Phe521Leufs and all frameshifts to search for motifs with a propensity to form amyloid (Table 1). [START_REF] Ventura | Short amino acid stretches can mediate amyloid formation in globular proteins: the Src homology 3 (SH3) case[END_REF][START_REF] Yoon | Detecting hidden sequence propensity for amyloid fibril formation[END_REF] We used AMYLPRED2, [START_REF] Tsolis | A consensus method for the prediction of "aggregation-prone" peptides in globular proteins[END_REF] which combines 11 individual algorithms, and PASTA2, [START_REF] Walsh | PASTA 2.0: an improved server for protein aggregation prediction[END_REF] which predicts which amino acid and β-sheet orientation is energetically favored. Combined algorithms indicated that, in all cases, the amino acid sequence encoded by each amyloidogenic frameshift variant created a common short stretch motif with high amyloidogenic propensity that involved a five-residue fragment (VLITL) (Figures 3A and3B). TANGO identified VLITL as the unique hot-spot with a high intrinsic propensity for β-aggregation regardless of pH and ionic strength (Figure 3A), and PASTA2 predicted that VLITL forms parallel in-register intermolecular β-sheets in amyloid (favorable pairing energy of -5.57, corresponding to 10.7 kcal/mol) (Figure 3B). Consistent with these predictions, VLITL is consistently present in Aα-chain frameshift variants associated with renal amyloidosis (Table 1), while VLITL is absent from the amino acid sequences of those that are not clinically amyloidogenic (http://site.geht.org/basefibrinogene/). 21,22 This genotype-phenotype correlationship suggests that nucleotide indel mutations producing mutant Aα-chains containing VLITL at their C-termini will be likely amyloidogenic (Table 1). More importantly, we show here that VLITL is part of renal fibrils of AFib-patient II.2 (residues 44-48 of the 49-mer amyloid peptide found ex vivo) (Figure 2B), reinforcing the view that VLITL indeed might confer amyloidogenic properties.

VLITL responsible for the amyloidogenic property of Phe521Leufs-derived peptides To experimentally verify that VLITL is the major amyloid sequence determinant of Aαchain frameshifts, we generated synthetic Aα-chain derived-peptides containing the predicted amyloid-prone VLITL motif, and compared their capacity for fibril formation with that of their VLITL-deleted counterparts. To this end, we designed AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG, the 49-mer fulllength Phe521Leufs-peptide identified in AFib-patient's deposits, and its corresponding VLITL-deleted control (AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G).

We also investigated the amyloid propensity of the ASSQIQRNPVLITLG-peptide, common to all amyloidogenic Aα-chain variants, and its VLITL-deleted counterpart ASSQIQRNP_G. Fibrillogenesis experiments were performed under the same physiological conditions and amyloid formation evaluated using ThT, a dye binding to βsheet aggregates with a characteristic maximum emission fluorescence intensity at 485 nm, TEM to determine the morphological features of aggregates, and X-ray microdiffraction (XRD) to ensure that aggregates possess the typical cross-β architecture. [START_REF] Makin | Diffraction to study protein and peptide assemblies[END_REF][START_REF] Nilsson | Techniques to study amyloid fibril formation in vitro[END_REF] A s s h o w n i n F i g u re s 4E-G). In contrast, ASSQIQRNP_G, did not exhibit any ThT spectral change (Figure 4E), and did not form aggregates (amorphous or fibrillar in nature) (data not shown), demonstrating that ASSQIQRNP_G does not form any kind of amyloid species under the same physiological conditions that the ASSQIQRNPVLITLG-peptide does.

Therefore, our experiments show that the 49-mer and 15-mer Phe521Leufs-derived peptides are readily amyloidogenic in vitro but lose their fibril-forming ability when VLITL is absent, supporting that their amyloidogenic behavior depends on VLITL amyloidogenic properties. Next, we experimentally verified whether VLITL itself forms amyloid in vitro. A ThT assay of VLITL showed typical amyloid enhancement of fluorescence emission at 485 nm (Figure 4I). In addition, TEM revealed twisted mature fibrils with a ribbon-like appearance (Figures 4J and4K) and XRD confirmed that VLITLfibrils are amyloid with a highly ordered and well-defined cross-β structure (Figure 4L).

Structural similarities between in vitro and ex vivo Phe521Leufs-derived fibrils

The structures of Phe521Leufs-derived fibrils generated in vitro were compared to those formed in AFib-patient kidneys (individual II.2). To this end, we performed ex situ XRD studies of Phe521Leufs-fibrils using kidney cuts obtained without denaturing extraction procedures to preserve the natural state of aggregates formed in vivo, offering the opportunity to gain structural information on fibrils in their natural cellular context (Figure 3H). [START_REF] Briki | Synchrotron x-ray microdiffraction reveals intrinsic structural features of amyloid deposits in situ[END_REF] XRD showed that the signal of the equatorial reflection from natural fibrils was very close to that of fibrils generated by ASSQIQRNPVLITLG, recapitulating the structural features of renal AFib-fibrils in physiological conditions (Figures 4C,4G,4H, and 4L). [START_REF] Riek | The activities of amyloids from a structural perspective[END_REF] Therefore, this mutant 15-mer Aα-chain derived-sequence likely governs the detailed structure of Phe521Leufs-fibrils formed in patient kidneys, and might constitute a valuable "minimalist" in vitro amyloid model.

Discussion

Here, in addition to report a new "private" Aα-chain amyloidogenic frameshift variant, the aim of this study was to focus on the molecular mechanisms by which fibrinogen Aα-chain frameshift variants become amyloidogenic in humans.

Our results show that VLITL is a key amyloid-prone motif located at the Cterminally mutant end of all Aα-chain frameshift sequences, conferring amyloidogenic properties to Aα-chain frameshift variants. In this study, we first characterized which part of the Aα-chain was deposited in Phe521Leufs-patient's tissues, and we demonstrated that a short 49-mer peptide deriving from the Phe521Leufs-allele formed the renal fibrils. These clinico-anatomopathological findings overlap those obtained from our French AFib-kindred carrying the Val522Alafs variant which had previously documented that a 49-amino acid peptide encoded by the Val522Alafs-allele was similarly deposited as fibrils in kidneys. [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] More recently, Yazaki et al. also confirmed that the carboxyl terminal region of the amyloidogenic Ser523Argfs variant, containing VLITL, constituted AFib-patient's renal deposits. [START_REF] Yazaki | The first pure form of Ostertag-type amyloidosis in Japan: a sporadic case of hereditary fibrinogen Aα-chain amyloidosis associated with a novel frameshift variant[END_REF] Therefore, three ex vivo biochemical analysis of amyloid deposits from AFib-patient's carrying three distinct frameshift variants of Aα-chain concordantly established that only the C-terminal fragments of Aαchain frameshift variants contribute to amyloid formation, and not the wild-type Aαchain. We then tested the hypothesis that these highly similar Aα-chain C-terminal mutant sequences, specific to amyloidogenic variants, might contain segments with a high propensity to self-aggregate into ß-sheets rendering mutant Aα-chains amyloidogenic. Our in silico analysis predicted that the C-terminal end of all mutant Aαchains contained a major amyloid hot spot, VLITL. This prediction was in good concordance with the fact that VLITL was found within renal amyloid deposits of Phe521Leufs-, Val522Alafs-and Ser523Argfs-AFib patients. [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF][START_REF] Yazaki | The first pure form of Ostertag-type amyloidosis in Japan: a sporadic case of hereditary fibrinogen Aα-chain amyloidosis associated with a novel frameshift variant[END_REF] To experimentally verify that VLITL is a major ß-sheet signal of Aα-chain frameshift variants, we evaluated the ability of synthetic Phe521Leufs-derived peptides containing the VLITL motif to polymerize into ß-sheet in vitro. We also compared their capacity for fibril formation with that of their VLITL-deleted counterparts. We provide in vitro evidence that VLITL is a fibril-forming motif, necessary for the β-sheet arrangement of the full-length Aα-chain peptide deposited as extracellular fibrils in Phe521Leufs-patient's kidneys, while its absence abrogates fibril formation of Phe521Leufs-derived peptides. Therefore, combined in vitro and in vivo experiments support that the amyloidogenic behavior of the Phe521Leufs variant depends on the amyloidogenic properties of VLITL. The location of VLITL at the extreme end of renal fibrils probably renders this motif easily accessible for intermolecular interactions in vivo. VLITL satisfies two major criteria that are recognized as essential for triggering amyloid formation: high β-sheet propensity and appropriate position within the mutant Aα-chains for nucleating fibril formation. [START_REF] Esteras-Chopo | The amyloid stretch hypothesis: recruiting proteins toward the dark side[END_REF][START_REF] Pastor | Hacking the code of amyloid formation: the amyloid stretch hypothesis[END_REF] It is important to note that Phe521Leufs-derived peptides form amyloid fibrils in "physiological" experimental conditions. On this basis, it was therefore particularly relevant to compare the structural characteristics of Phe521Leufs-derived fibrils formed in vitro with those formed in the Phe521fs-patient's kidneys. To this end, X-ray analysis of Aα-chain-fibrils from Phe521fs-patients was performed "in situ", directly on the pathological renal tissue without denaturating extraction procedures, to preserve the natural state of Aα-chain aggregates. [START_REF] Briki | Synchrotron x-ray microdiffraction reveals intrinsic structural features of amyloid deposits in situ[END_REF] This structural analysis revealed that ASSQIQRNPVLITLG-fibrils closely reproduced the ß-sheet structural organization of Aα-. chain-fibrils assembled in their natural cellular context. Therefore, ASSQIQRNPVLITLG, the mutant portion common to all amyloidogenic frameshifts, is a "minimalist" in vitro Aα-chain model suitable for all amyloidogenic Aα-chain frameshift variants. This in vitro Aα-chain model might be useful for testing anti-amyloid agents targeting the VLITL motif because we showed that deleting VLITL disrupts fibril aggregation propensity of synthetic Phe521Leufs-derived peptides. Also, this in vitro model can be useful to conduct high-resolution structure investigations to shed light on the precise atomistic structure of Aα-chain frameshift derived-fibrils.

The reasons why fragments of the mutant Aα-chain C-terminus accumulate and form amyloid in kidneys, and why the mutant Aα-chain could not be detected in the plasma of AFib-patients are not understood, [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] but it has been proposed that it can be the consequence of an accelerated metabolism of the mutant Aα-chain. [START_REF] Hamidi Asl | Renal amyloidosis with a frame shift mutation in fibrinogen aalpha-chain gene producing a novel amyloid protein[END_REF] In case of Aα-chain dysfibrinogenic variants, experiments carried on the His494fs and Ala499fs frameshift variants, each introducing in their mutant C-terminal part a novel unpaired cysteine residue, revealed that these mutant Aα-chains circulated as disulphide-linked complexes with albumin. More importantly, it has been shown that these abnormal Aα-chainalbumin complexes directly altered the fibrin clot structure, conferring to the patients a dysfibrinogenic phenotype, clinically apparent as recurrent episodes of thromboembolism. [START_REF] Homer | Novel Aalpha chain truncation (fibrinogen Perth) resulting in low expression and impaired fibrinogen polymerization[END_REF][START_REF] Margaglione | A frameshift mutation in the human fibrinogen Aalpha-chain gene (Aalpha(499)Ala frameshift stop) leading to dysfibrinogen San Giovanni Rotondo[END_REF][START_REF] Dempfle | Demonstration of heterodimeric fibrinogen molecules partially conjugated with albumin in a novel dysfibrinogen: fibrinogen Mannheim V[END_REF] Unlike Aα-chain dysfibrinogenic variants, the amino acid composition of the mutant C-terminus of amyloidogenic frameshift variants do not contain a novel cysteine residue, thus they are unlikely able to form abnormal disulphide conjugates with albumin. This could explain why, despite lacking Lys556, Lys580, and Lys601 in the αC-domain important for factor XIII cross-linking, AFibpatients do not show clinical and biological evidence of clotting disorders. Further, we can speculate that these "albumin-free" amyloidogenic Aα-chains might be more susceptible to undergo an aberrant proteolytic cleavage, yielding high concentrations of a catabolic intermediate containing the amyloid-prone VLITL motif serving as an amyloid core to initiate fibrillogenesis in the cellular environment of the kidney.

Consistent with data from the literature, it is unlikely a coincidence that no mutations involving a cysteine residue in the Aα-chain have been associated with AFib, while they explain a large number of congenital dysfibrinogenemias associated with circulating fibrinogen-albumin conjugates (http://site.geht.org/base-fibrinogene/). An instructive example is given by Fibrinogen Dusart, caused by the replacement of arginine 554 by cysteine (Arg554Cys) in the Aα-chain, which is associated with Aα-chains-554C-albumin complexes and recurrent episodes of thrombosis, [START_REF] Koopman | Molecular basis for fibrinogen Dusart (A alpha 554 Arg-->Cys) and its association with abnormal fibrin polymerization and thrombophilia[END_REF][START_REF] Mosesson | The relationship between the fibrinogen D domain self-association/cross-linking site (gammaXL) and the fibrinogen Dusart abnormality (Aalpha R554C-albumin): clues to thrombophilia in the "Dusart syndrome[END_REF] while replacement of Arg554 by leucine (Arg554Leu) causes renal AFib-amyloidosis. [START_REF] Benson | Hereditary renal amyloidosis associated with a mutant fibrinogen alpha-chain[END_REF] The six polypeptide chains of the normal fibrinogen molecule are covalently linked by numerous interchain disulphide bonds, with no free sulphydryl groups, [START_REF] Weisel | Mechanisms of fibrin polymerization and clinical implications[END_REF] supporting that an unpaired cysteine residue in the fibrinogen molecule might be critical on overall clot structure.

In summary, we provide compelling evidence that VLITL is part of Phe521Leufsfibrils formed in vivo, and is a major fibril-forming motif necessary for β-sheet arrangement of the full-length Aα-chain Phe521Leufs-peptide identified in AFibpatient's kidneys. This VLITL amyloid motif, exclusively present at the C-terminal end of amyloidogenic Aα-chain frameshift sequences, and also previously identified in amyloid deposits of Val522Alafs and Ser523Argfs AFib-patients support that VLITL is predictive of high risk of Aα-chain amyloid formation. This finding sheds light on the as yet unresolved issue of the mechanisms underlying Aα-chain amyloidogenesis, yielding an uncommon example among hereditary amyloidoses.

  4 A -D , AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG self-assembled into ThT-positive, β-sheet-enriched fibrillar aggregates exhibiting cross-β architecture that unambiguously define amyloid fibrils. The ThT profile forAFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G did not parallel that obtained for its corresponding amyloid VLITL-counterpart. Despite a mild fluorescence intensity, maximum emission was observed at 510 nm instead of 485 nm, indicating that these aggregates have distinct dye-binding characteristics from typical amyloid fibrils (Figure4A). Such a ThT profile has been associated with unstructured/amorphous aggregates. formation of fibrils (Figure5A). In contrast, AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG organized into fibrils with a diameter of 11.4±0.9 nm and twisted ribbon-like substructure (Figure4B). XRD of AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG-fibrils showed a typical "cross-β" molecular architecture with 4.72 Å sharp signal arising from the repeated β-strand spacing along the fibril axis and 11.5 Å signal corresponding to the stacking of β-sheets perpendicular to the fibril axis (Figures4C and 4D). In contrast, XRD pattern of AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G showed one diffuse reflection ring around 4.5 Å arising from the mean distance of randomly distributed peptide chains (Figure5B). Therefore, XRD provided definitive structural evidence that species formed by AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G lack ordered cross-β organization, the major diagnostic hallmark of amyloid. Experimental studies of ASSQIQRNPVLITLG demonstrated that this VLITL-containing peptide bound ThT with a characteristic amyloid maximum emission fluorescence intensity at 485 nm and formed fibrillar aggregates with a diameter of 13±0.9 nm and cross-β molecular architecture (Figures

  performed and analyzed the in vitro fibrillogenesis studies. F.B and J.D performed and analyzed the X-ray diffraction studies. N.R-L and L.M performed and analyzed the microscopy and immunohistochemical analysis. A.D, J.T, and J.A performed the LMD/MS analysis. C.B performed the molecular screening. F.B, M.D contributed to the discussion of the data. G.G contributed to the discussion, provided critical review of the manuscript, edited and approved the final version of the manuscript. B.N contributed to the preparation of the manuscript and prepared the figures. P.D, S.V analyzed in silico calculations and designed in vitro experiments. S.V supervised all aspects of this work, developed the whole idea, designed the experiments, collected and interpreted the data and wrote the manuscript. Conflict-of-interest disclosure: The authors declare no competing interests. Correspondence: Pr. Sophie Valleix, Laboratoire de Génétique Moléculaire, Hôpital Necker-Enfants Malades, 75015 Paris, Université Paris Descartes, Sorbonne Paris Cité, Faculté de Médecine Paris; AP-HP, Paris, France. E-mail : sophie.valleix@aphp.fr

Figure 1 .

 1 Figure 1. Novel amyloidogenic"private" Aα-chain frameshift variant in a French family. (A) shows the family pedigree of the AFib-kindred with familial segregation of the Phe521Leufs variant due to a single thymine deletion at Phe521. Squares denote male family members, circles female family members, and solid symbols affected family members. (B) shows partial sequence of FGA exon 5 from II.2, indicating heterozygosity for deletion of a single thymine leading to superimposed sequences after codon 521. (C) shows Congo red deposits in the glomeruli of renal specimens from II.2 (x400). (D) illustrates the amyloid fibrils found in the mesangium and under the glomerular basement membrane, appearing as straight unbranched fibrils with 10 nm diameter by EM (x1400). (E) shows positive staining with the specific Aα-chain antibody raised against the C-terminal Aα-chain mutant sequence (black arrow).

Figure 2 .

 2 Figure 2. The C-terminal mutant region predicted by Phe521Leufs is detected in renal amyloid deposits, but not its wild-type counterpart. (A) shows the results of LMD/MS-based proteomics analysis of amyloid plaques from seven cases of AFib. Cases 1-6 carry the Aα-chain Glu526Val (E526V) variant and case 7 the Phe521Leufs (F521fs) variant. The identified proteins are listed by relative probability score for identity, and the top 20 proteins of 103 proteins are shown. The columns show the protein name, the UnitProt identifier (protein accession number in the UniProt database, http://www.uniprot.org/), the molecular weight of the protein, and one microdissection from 7 patient specimens involved by AFib. The numbers indicate the number of total peptide spectra identified for each protein. Fibrinogen Aα-chain is the most abundant protein amyloidogenic in this sample set, consistent with AFib amyloidosis in each case. To show the presence of mutated proteins in the amyloid plaques, the raw mass spectrometry data files were searched using the human SwissProt database supplemented with Aα-chain variants Glu526Val and Phe521Leufs. Consistent with genetic analysis, cases 1-6 contain the tryptic peptide carrying the Glu526Val variant (Row 7, green rectangle), whereas this variant is not present in the case with the Phe521Leufs variant. In contrast, the novel tryptic peptides generated by the frameshift in Phe521Leufs variant are only present in case 7 (Row 17, red rectangle). (B) shows the Aα-chain protein coverage in seven cases of AFib amyloidosis. Cases 1-6 carry the Glu526Val variant and case 7 the Phe521Leufs variant. The top line represents the Cterminal sequence of native Aα-chain. The amino acid residues of Phe521Leufs (F521 in red) and Glu526Val (E526 in green) are indicated. The first line of rectangles (blue) labeled "WT" represents the coverage of the wild-type Aα-chain by the mass spectrometry-based proteomic method used. Two samples (S1 and S2) from four patients are shown. In cases 1-6 (Glu526Val variant), most of the coverage is identical to the wild-type Aα-chain except for the tryptic peptide carrying the point mutation (green rectangle) instead of the amino acid present in the wild-type peptide. In case 7 (Phe521Leufs), frameshift leads to a novel sequence indicated by the red rectangle and

Figure 3 .

 3 Figure 3. In silico studies of human Aα-chain amyloidogenic frameshift variants. (A) The TANGO aggregation scores of Phe521Leufs variant exhibited a very strong signal for β-sheet aggregation for VLITL at pH 2 (full line) and pH 8 (dotted line) at its Cterminus. (B) PASTA2 predicted that VLITL is likely to stabilize the cross-ß core of fibrillar aggregates and predicts parallel in-register intermolecular β-sheets for VLITL.

Figure 4 .

 4 Figure 4. In vitro fibrillogenesis and structural analysis of Aα-chain frameshiftderived polypeptides identified in amyloid deposits in vivo. (A) shows ThT fluorescence assays performed on AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG (red curve) and AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G (blue curve). Characteristic enhanced ThT fluorescence at 485 nm was only observed for AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG suggesting that this peptide formed amyloid β-sheet structures. In contrast, a spectral red shift at 510 nm was recorded for AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G, suggesting that it does not form typical amyloid β-sheet structures. (B) Transmission electron micrographs showed that AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG forms fibrillar aggregates and AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G spherical aggregates. (C) Fibrils formed by AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG exhibited a meridional peak at 4.72 Å, indicating the spacing between β-strands within fibrils associated with an equatorial reflection at 11.50 Å. This microdiffraction pattern confirms the presence of the characteristic amyloid cross-β architecture constituted by intermolecular β-sheets with β-strands oriented perpendicular to the fibril axis. (D) presents an extracted radial profile from the 2D pattern shown in (C). The noisy background is due to the small angle used for the profile extraction to avoid the intense peaks from salts in the sample. (E) shows data from ThT fluorescence assays performed on ASSQIQRNPVLITLG (red curve) and ASSQIQRNP_G (blue curve), revealing that only ASSQIQRNPVLITLG induces enhanced fluorescence at 485 nm and that only the peptide containing VLITL forms aggregates with β-sheet conformation. (F) Transmission electron micrographs showed that ASSQIQRNPVLITLG forms aggregates of fibrillar morphology. (G) shows XRD profiles of ASSQIQRNPVLITLG fibrils displaying the typical "cross-β" microdiffraction pattern of amyloid fibrils with a spacing of 4.75 Å along the meridional direction and a periodicity of 9.90 Å in the equatorial direction. (H) illustrates the in situ X-ray microdiffraction pattern from a cut of the pathological kidney specimen of patient II.2 with in vivo amyloid fibrils, showing meridional (4.71 Å) and equatorial (10.0 Å) reflections. (I) shows a ThT fluorescence assay of VLITL with increased fluorescence intensity at 485 nm, demonstrating that the dye bound to β-

Figure 5 .

 5 Figure 5. Structural characteristics of AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNP_G assemblies. (A) shows the morphological features of aggregates. Note that these aggregates are spherical and do not form fibrillar structures, in contrast to amyloid fibrils formed by AFFDTASTGKTFPGFFSPMLGELSVRLSLGAQNLASSQIQRNPVLITLG (Fig. 4B). (B) X-ray microdiffraction did not reveal a cross-β microdiffraction pattern, demonstrating that the aggregates are not amyloid.

Figure 5

 5 Figure 5

Table 1

 1

	Aα-chain frameshift variants associated	FGA nucleotide variations	Predicted C-termin al mutant Aα-chains	Renal Aα-chain fibril
	with renal amyloidosis		encoded by the respective shifted reading frames	composition
			with premature stop at codon 548
	Met517_Phe521delinsGlnSerfs*28 (p. Met536_Phe540delinsGlnSerfs*28	c.1606_1620 delATGTTAGGAGAGTTT	…QSVRLSLGAQNLASSQIQRNPVLITLG	No
	(Kang et al., Kidney Int 2005)	insCA
	Phe521Leufs*28 (p.Phe540Leufs*28)	c.1620delT
	(New variant reported here)		…LSVRLSLGAQNLASSQIQRNPVLITLG	Yes
	Phe521Serfs*27 (p.Phe540Ser*27)	c.1619_1622delTTGT		(This report)
	(The XVth ISA)		…SVRLSLGAQNLASSQIQRNPVLITLG	Yes
	Val522Alafs*27 (p.Val541Alafs*27) (Hamidi et al., Blood 1997)	c.1622delT	…AVRLSLGAQNLASSQIQRNPVLITLG	Yes
				(Our previous AFib-
	Ser523Argfs*26 (p.Ser543Argfs*26) (Yazaki et al., Amyloid 2015)	c.1624_1627del AGTG	…RLSLGAQNLASSQIQRNPVLITLG	kindred) Yes
	Glu524Glufs*25 (p.Glu543Glufs*25) (Uemichi et al., Blood 1996)	c.1629delG	…LSLGAQNLASSQIQRNPVLITLG	No
	Thr525Thrfs*24 (p.Thr544Thrfs*24) (Gillmore et al., J Am Soc Nephrol 2009)	c.1632delT	…SLGAQNLASSQIQRNPVLITLG	Yes
	Ser532Serfs*16 (p.Ser551Serfs*16) (The XIIIth ISA)	c.1653delT	…ASSQIQRNPVLITLG	No

Table 1 .

 1 Summary of FGA variants associated with renal amyloidosis. Irrespective of the nucleotide position of the FGA deletion/insertion anomalies, all frameshifts truncate at codon 548 and generate similar mutant C-terminal sequences. In the third column of the Table are shown the predicted C-terminal portions of frameshifts: in black are the portion which differs of four/five residues between frameshifts and in blue is the common 15 amino acid sequence, shared by all frameshifts: ASSQIQRNPVLITLG contains the VLITL motif (underligned). All amyloidogenic Aα-chain frameshift variants are listed according to the two nomenclatures. To convert the conventional mature protein amino acid numbering to the HGVS nomenclature, add 19 nucleotides for Aα-chain changes.

Acknowledgments

We thank all of the family members for their participation in this study, and l'Association Française contre l'Amylose. We thank Fabrice Senger and Marie-Paule Ramée for technical assistance with light microscopy and transmission electron microscopy, respectively. We thank Céline Leroux for her assistance with FGA sequencing, and J D Theis for his assistance in proteomics analysis at the Mayo Clinic. This work was supported in part by grants from l'Association Française contre l'Amylose.


Iovka Boneva

Jose Lozano

Sławek Staworko

Relational to RDF Data Exchange in Presence of a Shape Expression Schema

We study the relational to RDF data exchange problem, where the target constraints are specified using Shape Expression schema (ShEx). We investigate two fundamental problems: 1) consistency which is checking for a given data exchange setting whether there always exists a solution for any source instance, and 2) constructing a universal solution which is a solution that represents the space of all solutions. We propose to use typed IRI constructors in source-totarget tuple generating dependencies to create the IRIs of the RDF graph from the values in the relational instance, and we translate ShEx into a set of target dependencies. We also identify data exchange settings that are key covered, a property that is decidable and guarantees consistency. Furthermore, we show that this property is a sufficient and necessary condition for the existence of universal solutions for a practical subclass of weakly-recursive ShEx.

Introduction

Data exchange can be seen as a process of transforming an instance of one schema, called the source schema, to an instance of another schema, called the target schema, according to a set of rules, called source-to-target tuple generating dependencies (sttgds). But more generally, for a given source schema, any instance of the target schema that satisfies the dependencies is a solution to the data exchange problem. Naturally, there might be no solution, and then we say that the setting is inconsistent. Conversely, there might be a possibly infinite number of solutions, and a considerable amount of work has been focused on finding a universal solution, which is an instance (potentially with incomplete information) that represents the entire space of solutions. Another fundamental and well-studied problem is checking consistency of a data exchange setting i.e., given the source and target schemas and the st-tgds, does a solution exist for any source instance. For relational databases the consistency problem is in general known to be undecidable [START_REF] Beeri | The implication problem for data dependencies[END_REF][START_REF] Kolaitis | The complexity of data exchange[END_REF] but a number of decidable and even tractable cases has been identified, for instance when a set of weakly-acyclic dependencies is used [START_REF] Fagin | Data exchange: semantics and query answering[END_REF].

Resource Description Framework (RDF) [2] is a well-established format for publishing linked data on the Web, where triples of the form (subject, predicate, object) allow to represent an edge-labeled graph. While originally RDF was introduced schemafree to promote its adoption and wide-spread use, the use of RDF for storing and exchanging data among web applications has prompted the development of schema languages for RDF [START_REF]Shapes Constraint Language (SHACL)[END_REF][START_REF] Ryman | Oslc resource shape: A language for defining constraints on linked data[END_REF][START_REF] Sirin | Data Validation with OWL Integrity Constraints[END_REF]. One such schema language, under continuous development, is Shape Expressions Schemas (ShEx) [START_REF] Boneva | Semantics and Validation of Shapes Schemas for RDF[END_REF][START_REF] Staworko | Complexity and Expressiveness of ShEx for RDF[END_REF], which allows to define structural constraints on nodes and their immediate neighborhoods in a declarative fashion.

In the present paper, we study the problem of data exchange where the source is a relational database and the target is an RDF graph constrained with a ShEx schema. Although an RDF graph can be seen as a relational database with a single ternary relation Triple, RDF graphs require using Internationalized Resource Identifiers (IRIs) as global identifiers for entities. Consequently, the framework for data exchange for relational databases cannot be directly applied as is and we adapt it with the help of IRI constructors, functions that assign IRIs to identifiers from a relational database instance. Their precise implementation is out of the scope of this paper and belongs to the vast domain of entity matching [START_REF] Köpcke | Frameworks for Entity Matching: A Comparison[END_REF].

Example 1. Consider the relational database of bug reports in Figure 1, where the relation Bug stores a list of bugs with their description and ID of the user who reported the bug, the name of each user is stored in the relation User and her email in the relation Email. Additionally, the relation Rel identifies related bug reports for any bug report. Now, suppose that we wish to share the above data with a partner that has an already existing infrastructure for consuming bug reports in the form of RDF whose structure is described with the following ShEx schema (where : is some default prefix):

TBug → {:descr :: Lit 1 ,:rep :: TUser 1 ,:related :: TBug * } TUser → {:name :: Lit 1 ,:email :: Lit 1 ,:phone :: Lit ? }

The above schema defines two types of (non-literal) nodes: TBug for describing bugs and TUser for describing users. Every bug has a description, a user who reported it, and a number of related bugs. Every user has a name, an email, and an optional phone number. The reserved symbol Lit indicates that the corresponding value is a literal.

The mapping of the contents of the relational database to RDF is defined with the following logical rules (the free variables are implicitly universally quantified).

Bug(b, d, u) ⇒ Triple(bug2iri(b),:descr, d) ∧ TBug(bug2iri(b)) ∧ Triple(bug2iri(b),:rep, pers2iri(u)) Rel(b 1 , b 2 ) ⇒ Triple(bug2iri(b 1 ),:related, bug2iri(b 2 )) User(u, n) ⇒ Triple(pers2iri(u),:name, n) ∧ TUser(pers2iri(u)) User(u, n) ∧ Email(u, e) ⇒ Triple(pers2iri(u),:email, e) ∧ Lit(e)
On the left-hand-side of each rule we employ queries over the source relational database, while on the right-hand-side we make corresponding assertions about the triples in the target RDF graph and the types of the nodes connected by the triples. The atomic values used in relational tables need to be carefully converted to IRIs with the help of IRI constructors pers2iri and bug2iri. The constructors can be typed i.e., the IRI they introduce are assigned a unique type in the same st-tgd. We point out that in general, IRI constructors may use external data sources to properly assign to the identifiers from the relational database unique IRIs that identify the object in the RDF domain. For instance, the user Jose is our employee and is assigned the corresponding IRI emp:jose, the user Edith is not an employee but a registered user of our bug reporting tool and consequently is assigned the IRI user:edith, and finally, the user Steve89 is an anonymous user and is assigned a special IRI indicating it anon:3.

Figure 2 presents an RDF instance that is a solution to the problem at hand. We point out that the instance uses a (labeled) null literal ⊥ 1 for the email of Steve89 that is required by the ShEx schema but is missing in our database.

"Kabang!" "Boom!" "Bang!" "Kaboom!" bug:3 bug:1 bug:4 bug:2 emp:jose user:edith anon:3 "Jose" "j@ex.com" "Edith" "e@o. The presence of target schema raises the question of consistency. On the one hand, we can prove that for any instance of the relational database in Example 1 there exists a target solution that satisfies the schema and the set of source-to-target tuple generating dependencies. On the other hand, suppose we allow a user to have multiple email addresses, by changing the key of Email to both uid and email ). Then, the setting would not be consistent as one could construct an instance of the relational database, with multiple email addresses for a single user, for which there would be no solution.

Our investigation provides a preliminary analysis of the consistency problem for relational to RDF data exchange with target ShEx schema. Our contribution can be summarized as follows:

a formalization of relational to RDF data exchange with target ShEx schema and typed IRI constructors. a decidable characterization of a fully-typed key-covered data exchange setting that is a sufficient and necessary condition for consistency. an additional restriction of weak-recursion on ShEx schemas that ensures the existence of universal solution.

Related Work. Relational Data Exchange, Consistency. The theoretical foundations of data exchange for relational databases are laid in [START_REF] Arenas | Relational and XML Data Exchange[END_REF][START_REF] Fagin | Data exchange: semantics and query answering[END_REF]. Source-to-target dependencies with Skolem functions were introduced by nested dependencies [START_REF] Fuxman | Nested Mappings: Schema Mapping Reloaded[END_REF] in order to improve the quality of the data exchange solution. General existentially quantified functions are possible in second order tgds [START_REF] Arenas | The Language of Plain SO-tgds: Composition, Inversion and Structural Properties[END_REF]. Consistency in the case of relational data exchange is undecidable, and decidable classes usually rely on chase termination ensured by restrictions such as acyclicity, or guarded dependencies, or restrictions on the structure of source instances. The consistency criterion that we identify in this paper is orthogonal and is particular to the kind of target constraints imposed by ShEx schemas. In [START_REF] Marnette | Static Analysis of Schema-mappings Ensuring Oblivious Termination[END_REF], static analysis is used to test whether a target dependency is implied by a data exchange setting, these however rely on chase termination. Consistency is an important problem in XML data exchange [START_REF] Arenas | Relational and XML Data Exchange[END_REF] but the techniques developed for XML do not apply here.

Value Invention, Relational to RDF Data Exchange. Value invention is used in the purely relational setting for generating null values. Tools such as Clio [START_REF] Fagin | Clio: Schema Mapping Creation and Data Exchange[END_REF] and ++Spicy [START_REF] Marnette | ++Spicy: an Open-Source Tool for Second-Generation Schema Mapping and Data Exchange[END_REF] implement Skolem functions as concatenation of their arguments. IRI value invention is considered by R2RML [START_REF] R2rml | RDB to RDF Mapping Language[END_REF], a W3C standard for writing customizable relational to RDF mappings. The principle is similar to what we propose here. A R2RML mapping allows to specify logical tables (i.e. very similar to left-hand-sides of source-to-target dependencies), and then how each row of a logical table is used to produce one or several triples of the resulting RDF graph. Generating IRI values in the resulting graph is done using templates that specify how a fixed IRI part is to be concatenated with the values of some of the columns of the logical table. R2RML does not allow to specify structural constraints on the resulting graph, therefore the problem of consistency is irrelevant there. In [START_REF] Sequeda | On Directly Mapping Relational Databases to RDF and OWL[END_REF], a direct mapping that is a default automatic way for translating a relational database to RDF is presented. The main difference with our proposal and with R2RML is that the structure of the resulting RDF graph is not customizable. In [START_REF] Boneva | Graph Data Exchange with Target Constraints[END_REF] we studied relational to graph data exchange in which the target instance is an edge labelled graph and source-to-target and target dependencies are conjunctions of nested regular expressions. Such a framework raises a different kind of issues, among which is the materialization of a solution, as a universal solution is not necessarily a graph itself, but a graph pattern in which some edges carry regular expressions. On the other hand, IRI value invention is not relevant in such framework.

Organization. In Section 2 we present basic notions. In Section 3 we show how ShEx schemas can be encoded using target dependencies. In Section 4 we formalize relational to RDF data exchange. In Section 5 we study the problem of consistency. And finally, in Section 6 we investigate the existence of universal solutions. Conclusions and directions of future work are in Section 7. The missing proofs can be found in the full version [?].

Preliminaries

First-order logic. A relational signature R (resp. functional signature F) is a finite set of relational symbols (resp. functional symbols), each with fixed arity. A type symbol is a relational symbol with arity one. A signature is a set of functional and relational symbols. In the sequel we use R, resp. F, resp. T for sets of relational, resp. functional, resp. type symbols.

We fix an infinite and enumerable domain Dom partitioned into three infinite subsets Dom = Iri ∪ Lit ∪ Blank of IRIs, literals, and blank nodes respectively. Also, we assume an infinite subset NullLit ⊆ Lit of null literals. In general, by null values we understand both null literals and blank nodes and we denote them by Null = NullLit ∪ Blank.

Given a signature W = R ∪ F, a model (or a structure) of W is a mapping M that with any symbol S in W associates its interpretation S M s.t.:

-R M ⊆ Dom n for any relational symbol R ∈ R of arity n; f M : Dom n → Dom, which is a total function for any function symbol f ∈ F of arity n.

We fix a countable set V of variables and reserve the symbols x, y, z for variables, and the symbols x, y, z for vectors of variables. We assume that the reader is familiar with the syntax of first-order logic with equality and here only recall some basic notions. A term over F is either a variable in V , or a constant in Dom, or is of the form f (x) where f ∈ F and the length of x is equal to the arity of f ; we remark that we do not allow nesting of function symbols in terms. A dependency is a formula of the form ∀x.ϕ ⇒ ∃y.ψ and in the sequel, we often drop the universal quantifier, write simply ϕ ⇒ ∃y.ψ, and assume that implicitly all free variables are universally quantified.

The semantics of first-order logic formulas is captured with the entailment relation M, ν |= φ defined in the standard fashion for a model M , a first-order logic formula φ with free variables x and a valuation ν : x → Dom. The entailment relation is extended to sets of formulas in the canonical fashion:

M |= {ϕ 1 , . . . , ϕ n } iff M |= ϕ i for every i ∈ {1, . . . , k}.
Relational Databases. We model relational databases using relational structures in the standard fashion. For our purposes we are only concerned with functional dependencies, which include key constraints. Other types of constraints, such as inclusion dependencies and foreign key constraints, are omitted in our abstraction.

A relational schema is a pair R = (R, Σ fd ) where R is a relational signature and Σ fd is a set of functional dependencies (fds) of the form R : X → Y , where R ∈ R is a relational symbol of arity n, and X, Y ⊆ {1, . . . , k}. An fd R : X → Y is a short for the following formula ∀x, y. R(x) ∧ R(y) ∧ i∈X (x i = y i ) ⇒ j∈Y (x j = y j ). An instance of R is a model I of R and we say that I is valid if I |= Σ fd . The active domain dom(I) of the instance I is the set of values from Dom that appear in R I for some relational symbol R in R. Unless we state otherwise, in the sequel we consider only instances that use only constants from Lit \ NullLit.

RDF Graphs and Shape Expressions Schemas. Recall that an RDF graph, or graph for short, is a set of triples in (Iri ∪ Blank) × Iri × (Iri ∪ Blank ∪ Lit). The set of nodes of the graph G is the set of elements of Iri ∪ Blank ∪ Lit that appear on first or third position of a triple in G.

We next define the fragment of shape expression schemas that we consider, and that was called RBE 0 in []. Essentially, a ShEx is a collection of shape names, and each comes with a definition consisting of a set of triple constraints. A triple constraint indicates a label of an outgoing edge, the shape of the nodes reachable with this label, and a multiplicity indicating how many instances of this kind of edge are allowed. We remark that the constraints expressible with this fragment of ShEx, if non-recursive, can also be captured by a simple fragment of SHACL with AND operator only.

Formally, a multiplicity is an element of {1, ?, *, +} with the natural interpretation: 1 is exactly one occurrence, ? stands for none or one occurrence, * stands for an arbitrary number of occurrences, and + stands for a positive number of occurrences. A triple constraint over a finite set of shape names T is an element of Iri × (T ∪ {Lit}) × {1, ?, *, +}, where Lit is an additional symbol used to indicate that a node is to be a literal. Typically, we shall write a triple constraint (p, T, µ) as p :: T µ . Now, a shape expressions schema, or ShEx schema for short, is a couple S = (T , δ) where T is a finite set of shape names, and δ is shape definition function that maps every symbol T ∈ T to a finite set of triple constraints over T such that for every shape name T and for every IRI p, δ(T ) contains at most one triple constraint using p.

For a finite set T of shape names, a T -typed graph is a couple (G, typing) where G is a graph and typing is a mapping from the nodes of G into 2 T ∪{Lit} that with every node of G associates a (possibly empty) set of types. Let S = (T , δ) be a ShEx schema. The T -typed graph (G, typing) is correctly typed w.r.t. S if it satisfies the constraints defined by δ i.e., for any node n of G:

-if Lit ∈ typing(n), then n ∈ Lit; -if T ∈ typing(n) then n ∈ Iri
i.e., |K| = 1 if µ = 1, |K| ≤ 1 if µ = ?, and |K| ≥ 1 if µ = + (there is no constraint if µ = *).
For instance, a correct typing for the graph in Figure 2 assigns the type TBug to the nodes bug:1, bug:2, bug:3, and bug:4; the type TUser to the nodes emp:jose, user:edith, and anon:3; and Lit to every literal node.

ShEx Schemas as Sets of Dependencies

In this section we show how to express a ShEx schema S = (T , δ) using dependencies. First, we observe that any T -typed graph can be easily converted to a relational structure over the relational signature G T = {Triple} ∪ T ∪ {Lit}, where Triple is a ternary relation symbol for encoding triples, and T ∪ {Lit} are monadic relation symbols indicating node types (details in Appendix A). Consequently, in the sequel, we may view a T -typed graph as the corresponding relational structure (or even a relational database over the schema (G T , ∅)).

Next, we define auxiliary dependencies for any two T, S ∈ T and any p ∈ Iri We point out that in terms of the classical relational data exchange, tc and mult ≥1 are tuple generating dependencies (tgds), and mult ≤1 is an equality generating dependency (egd). We capture the ShEx schema S with the following set of dependencies:

Σ S =

Relational to RDF Data Exchange

In this section, we present the main definitions for data exchange.

Definition 1 (Data exchange setting). A relational to RDF data exchange setting is a tuple E = (R, S, Σ st , F, F int ) where R = (R, Σ fd ) is a source relational schema, S = (T , δ) is a target ShEx schema, F is a function signature, F int as an interpretation for F that with every function symbol f in F of arity n associates a function from Dom n to Iri, and Σ st is a set of source-to-target tuple generating dependencies, clauses of the form ∀x.ϕ ⇒ ψ, where ϕ is a conjunction of atomic formulas over the source signature R and ψ is a conjunction of atomic formulas over the target signature G T ∪F. Furthermore, we assume that all functions in F int have disjoint ranges i.e., for

f 1 , f 2 ∈ F int if f 1 = f 2 , then ran(f 1 ) ∩ ran(f 2 ) = ∅.
Definition 2 (Solution). Take a data exchange setting E = (R, S, Σ st , F, F int ), and let I be a valid instance of R. Then, a solution for I w.r.t. E is any T -typed graph J such that I ∪ J ∪ F int |= Σ st and J |= Σ S .

A homomorphism h : I 1 → I 2 between two relational structures I 1 , I 2 of the same relational signature R is a mapping from dom(I 1 ) to dom(I 2 ) that 1) preserves the values of non-null elements i.e., h(a) = a whenever a ∈ dom(I 1 ) \ Null, and 2) for every R ∈ R and every a ∈ R I1 we have h(a) ∈ R I2 , where h(a) = (h(a 1 ), . . . , h(a n )) and n is the arity of R.

Definition 3 (Universal Solution)

. Given a data exchange setting E and a valid source instance I, a solution J for I w.r.t. E is universal, if for any solution J for I w.r.t. E there exists a homomorphism h : J → J .

As usual, a solution is computed using the chase. We use a slight extension of the standard chase (explained in [?]) in order to handle function terms, which in our case is simple (compared to e.g. [START_REF] Arenas | The Language of Plain SO-tgds: Composition, Inversion and Structural Properties[END_REF]) as the interpretation of function symbols is given.

Consistency

Definition 4 (Consistency). A data exchange setting E is consistent if every valid source instance admits a solution.

We fix a relational to RDF data exchange setting E = (R, S, Σ st , F, F int ) and let S = (T , δ). We normalize source-to-target tuple generating dependencies so that their right-hand-sides use exactly one Triple atom and at most two type assertions on the subject and the object of the triple; such normalization is possible as our st-tgds do not use existential quantification. In this paper, we restrict our investigation to completely typed st-tgds having both type assertions, and therefore being of the following form

∀x. ϕ ⇒ Triple(s, p, o) ∧ T s (s) ∧ T o (o),
where s is the subject term, T s is the subject type, p ∈ Iri is the predicate, o is the object term, and T o is the object type. Because the subject of a triple cannot be a literal, we assume that s = f (y) for f ∈ F and for y ⊆ x, and T s ∈ T . As for the object, we have two cases: 1) the object is an IRI and then o = g(z) for g ∈ F and for z ⊆ x, and T o ∈ T , or 2) the object is literal o = z for z ∈ x and T o = Lit. Moreover, we assume consistency with the target ShEx schema S i.e., for any st-tgd in Σ st with source type T s , predicate p, and object type T o we have p :: T µ o ∈ δ(T s ) for some multiplicity µ. Finally, we assume that every IRI constructor in F is used with a unique type in T . When all these assumptions are satisfied, we say that the source-to-target tuple generating dependencies are fully-typed.

While the st-tgds in Example 1 are not fully-typed, an equivalent set of fully-typed dependencies can be easily produced if additionally appropriate foreign keys are given. For instance, assuming the foreign key constraint Bug[uid ] ⊆ User[uid ], the first rule with Bug on the left-hand-side is equivalent to Now, two st-tgds are contentious if both use the same IRI constructor f for their subjects and have the same predicate, hence the same subject type T s and object type T o , and p :: T µ o ∈ δ(T s ) with µ = 1 or µ = ?. We do not want two contentious sttgds to produce two triples with the same subject and different objects. Formally, take two contentious st-tgds σ 1 and σ 2 and assume they have the form (for i ∈ {1, 2}, and assuming x 1 , x 2 , y 1 , y 2 are pairwise disjoint)

σ i = ∀x i , y i . ϕ i (x i , y i ) ⇒ Triple(f (x i ), p, o i ) ∧ T s (f (x i )) ∧ T o (o i ).
The st-tgds σ 1 and σ 2 are functionally overlapping if for every valid instance I of R

I ∪ F int |= ∀x 1 , y 1 , x 2 , y 2 . ϕ 1 (x 1 , y 1 ) ∧ ϕ 2 (x 2 , y 2 ) ∧ x 1 = x 2 ⇒ o 1 = o 2 .
Finally, a data-exchange setting is key-covered if every pair of its contentious st-tgds is functionally overlapping. Note that any single st-tgd may be contentious with itself. Theorem 1. A fully-typed data exchange setting is consistent if and only if it is keycovered.

The sole reason for the non-existence of a solution for a source instance I is a violation of some egd in Σ S . The key-covered property ensures that such egd would never be applicable. Intuitively, two egd-conflicting objects o 1 and o 2 are necessarily generated by TBug TUser TEmp TTest Fig. 3: Dependency graph with dashed weak edges and plain strong edges two contentious st-tgds. The functional-overlapping criterion guarantees that the terms o 1 and o 2 are "guarded" by a primary key in the source schema, thus cannot be different.

Theorem 2. It is decidable whether a fully-typed data exchange setting is key-covered.

The proof uses a reduction to the problem of functional dependency propagation [START_REF] Klug | Determining View Dependencies Using Tableaux[END_REF].

Universal Solution

In this section, we identify conditions that guarantee the existence of a universal solution. Our results rely on the existence of a universal solution for sets of weakly-acyclic sets of dependencies for relational data exchange [START_REF] Fagin | Data exchange: semantics and query answering[END_REF]. As the tgds and egds that we generate are driven by the schema (cf. Section 3), we introduce a restriction on the ShEx schema that yields weakly-acyclic sets of dependencies, and consequently, guarantees the existence of universal solution.

The dependency graph of a ShEx schema S = (T , δ) is the directed graph whose set of nodes is T and has an edge (T, T ) if T appears in some triple constraint p :: T µ of δ(T ). There are two kinds of edges: strong edge, when the multiplicity µ ∈ {1, +}, and weak edge, when µ ∈ {*, ?}. The schema S is strongly-recursive if its dependency graph contains a cycle of strong edges only, and is weakly-recursive otherwise. Take for instance the following extension of the ShEx schema from The dependency graph of this schema, presented in Figure 3. contains two cycles but neither of them is strong. Consequently, the schema is weakly-recursive (and naturally so is the ShEx schema in Example 1).

As stated above, a weakly-recursive ShEx schema guarantees a weakly-acyclic set of dependencies and using results from [START_REF] Fagin | Data exchange: semantics and query answering[END_REF] we get Proposition 1. Let E = (R, S, Σ st , F, F int ) be a data exchange setting and I be a valid instance of R. If S is weakly recursive, then every chase sequence of I with Σ st ∪ Σ S is finite, and either every chase sequence of I with Σ st fails, or every such chase sequence computes a universal solution of I for E.

Conclusion and Future Work

We presented a preliminary study of the consistency problem for relational to RDF data exchange in which the target schema is ShEx. Consistency is achieved by fully-typed and key-covered syntactic restriction of st-tgds. An open problem that we plan to investigate is consistency when the fully-typed restriction is relaxed; we believe that it is achievable if we extend the definition of contentious st-tgds. Another direction of research is to consider a larger subset of ShEx. Finally, we plan to extend our framework to typed literals which are not expected to bring fundamental difficulties but are essential for practical applications.

A ShEx Schemas as Sets of Dependencies

Lemma 2. For any T -typed graph (G, typing), let rdf -to-inst(G, typing) be defined as below. For any I instance of (G T , ∅) satisfying Triple I ⊆ (Iri ∪ Blank) × Iri × (Iri ∪ Blank ∪ Lit) and Lit I ⊆ Lit and T I ⊆ Iri for all T ∈ T , let inst-to-rdf (I) be defined as below.

rdf -to-inst(G, typing) ={Triple(s, p, o) | (s, p, o) ∈ G} ∪ {T (n) | n node of G, T ∈ typing(n)} inst-to-rdf (I) =(G, typing) with G = {(s, p, o) | Triple(s, p, o) ∈ I} and typing(n) = {T ∈ T ∪ {Lit} | T (n) ∈ I} for any n node of G
Then for any T -typed graph (G, typing) and any instance I of (G T , ∅) in the domain of inst-to-rdf , the following hold:

1. rdf -to-inst(G, typing) is an instance of (G T , ∅); 2. inst-to-rdf (I) is a T -typed graph; 3. inst-to-rdf (rdf -to-inst(G, typing)
) is defined and is equal to (G, typing).

Proof. 1. Immediately follows from the definition rdf -to-inst(G, typing).

2. Immediately follows from the definition of inst-to-rdf (I).

Let

I = rdf -to-inst(G, typing). By definition, inst-to-rdf (I) is defined if (a) Triple I ⊆ (Iri ∪ Blank) × Iri × (Iri ∪ Blank ∪ Lit)
and (b) Lit I ⊆ Lit and (c) T I ⊆ Iri for all T ∈ T . Note that (a) follows from the definition of rdf -to-inst and the fact that G is an RDF graph. Also, (b) and (c) follow from the definition of rdf -to-inst and the fact that typing is a typing. Then it immediately follows from the definitions that inst-to-rdf (rdf -to-inst(G, typing)) = (G, typing).

A.1 Proof of Lemma 1

Take a typed graph (G, typing) and ShEx schema S = (T , δ). For the ⇒ direction, we will prove by contrapositive. Assume that (G, typing) |= Σ S . Our goal is to prove (G, typing) is not correctly typed w.r.t. S. By definition of entailment, there is one dependency σ ∈ Σ S that is not satisfied. The dependency σ can be of the following forms:

mult ≥1 (T s , p). By construction of Σ S , the dependency σ occurs when a triple constraint is of the form p :: T µ o where µ ∈ {1, +} and p some property. Since σ is not satisfied, T s ∈ typing(n) for some node n of G. Because the cardinalty of the set of triples with node n and propery p is 0, the definition of correctly typed in the typed graph (G, typing) w.r.t. S is violated.

mult ≤1 (T s , p). By construction of Σ S , the dependency σ occurs when a triple constraint is of the form p :: T µ o where µ ∈ {1, ?}. Since σ is not satisfied, we have that (s, p, o 1 ) ∈ G and (s, p, o 2 ) ∈ G and T s ∈ typing(s), which violates the definition of correctly typed in the typed graph (G, typing) w.r.t. S.

tc(T s , T o , p). By construction of Σ S , the dependency σ occurs when a triple constraint is of the form p :: T µ o where µ ∈ {1, ?, *, +}. Since σ is not satisfied, (s, p, o) ∈ G and T s ∈ typing(s). Because the node o ∈ G, it must hold T o ∈ typing(o). But this fact is not, then the typed graph (G, typing) w.r.t. S is not correctly typed.

For the ⇐ direction, assume that (G, typing) |= Σ S . Our goal is to prove (G, typing) is correctly typed w.r.t. S. We will prove by contradiction. Suppose that (G, typing) is not correctly typed w.r.t. S. Then we have two cases when there is a node n ∈ G:

B The chase

Let E = (R, S, Σ st , F, F int ) be a data exchange setting with R = (R, Σ fd ) and S = (T , δ), and let I be an instance of R ∪ G T . For a tgd or std σ = ∀x.φ → ψ and a homomorphism h : φ → I, we say that σ is applicable to I with h if (1) either ψ is without existential quantifier and I ∪ F int , h |= ψ, or (2) ψ = ∃y.ψ and for all h extension of h on y, I ∪ F int , h |= ψ . Then applying σ to I with h yields the instance I defined as follows. In the case (1), I = h Fint (ψ). In the case (2), I = h Fint (ψ ) where h is an extension of h and for y ∈ y, h (y) is a fresh null value that depends on S. If δ(T ) contains a triple constraint p :: Lit µ , then h (y) ∈ NullLit \ dom(I). If δ(T ) contains p :: T µ for some T ∈ T , then h (y) ∈ Blank \ dom(I). For an egd σ = ∀x.φ → x = x , if there exists a homomorphism h : φ → I s.t. h(x) = h(x ), we say that σ is applicable to I with h and the result is (1) the instance I obtained by replacing h(x) by h(x ) (resp. h(x ) by h(x)) in all facts of I if h(x) (resp. h(x )) is a null value, and (2) the failure denoted ⊥ if both h(x) and h(x ) are non nulls. We write

I σ,h
--→U if σ is applicable to I with h yielding U , where U is either another instance or ⊥, and I σ,h --→U is called a chase step. Let Σ be a set of dependencies and I be an instance. A chase sequence of I with Σ is a finite or infinite sequence of chase steps I i σi,hi ---→I i+1 for i = 0, 1, . . ., with I 0 = I and σ i a dependency in Σ. The well-known result from [START_REF] Fagin | Data exchange: semantics and query answering[END_REF] still holds in our setting: if there exists a finite chase sequence then it constructs a universal solution.

C Proofs of Theorems 1 and 2

Before proving the theorems, we define a mapping h F that will be used to define the notion of homomorphism from a formula into an instance. Let F be a function signature and F be an interpretation of F. For a term t over F and a mapping h : V → Dom, we define h F (t) as:

h F (t) =      h(x) if t = x ∈ V a if t = a ∈ Dom f (h F (t )) if t = f (t ) is a function term.
The mapping h F is extended on atoms and conjunctions of atoms as expected:

h F (R(t)) = R(h F (t)) and h F ( i∈1..k R i (t i )) = i∈1..k h F (R i (t i ))
. Note that if the argument of h F does not contain function terms, the interpretation F is irrelevant so we allow to omit the F superscript and write e.g. h(t) instead of h F (t).

A homomorphism h : φ → M between the conjunction of atoms φ over signature W = R ∪ F and the model M = I ∪ F of W is a mapping from fvars(φ) to Dom s.t. for every atom R(t) in φ it holds that R(h F (t)) is a fact in I, where I, resp. F , is the restriction of M to R, resp. to F.

Remark that if φ does not contain function terms, then F in the above definition is irrelevant and we write h : φ → I instead of h : φ → M and h(t) instead of h F (t).

C.1 Proof of Theorem 1

Take a data exchange setting E = (R, S, Σ st , F, F int ) with S = (T , δ). Assume first that E is consistent, and let I be a valid instance of R and J be a solution for I by E. That is, I ∪ J |= Σ st ∪ Σ S . Let T s , T o , p and µ ∈ {1, ?} be such that p ::

T µ o ∈ δ(T s ). Suppose by contradiction that, for i = 1, 2, σ i = ∀x.φ i (x i , y i ) ⇒ Triple(f (x i ), p, o i ) ∧ T s (f (x i )) ∧ T o (o i ) are two contentious stds in Σ st and they are not functionally overlapped that is I |= ∀x 1 , x 2 , y 1 , y 2 .φ 1 (x 1 , y 1 )∧φ 2 (x 2 , y 2 )∧x 1 = x 2 ⇒ o 1 = o 2 . That is, there is a homomorphism h : φ 1 ∧ φ 2 → I s.t. I, h |= φ 1 ∧ φ 2 but h Fint (o 1 ) = h Fint (o 2 ). Because J is a solution of E, we know that I ∪ J ∪ F int |= σ i for i = 1,
2 and deduce that J contains the facts (1) Triple(h Fint (f (x 1 )), p, h Fint (o 1 )), Triple(h Fint (f (x 1 )), p, h Fint (o 2 )) and T s (h Fint (f (x 1 ))). On the other hand, by definition mult ≤1 (T s , p) = ∀x, y, z. T s (x) ∧ Triple(x, p, y) ∧ Triple(x, p, z) ⇒ y = z is in Σ S and J |= mult ≤1 (T s , p). But mult ≤1 (T s , p) applies on the facts (1) with homomorphism h s.

t. h (x) = h Fint (f (x 1 )), h (y) = h Fint (o 1 ) and h (z) = h Fint (o 2 ), therefore h Fint (o 1 ) = h Fint (o 2 ). Contradiction.
Assume now that E is key-covered, and let I be a valid instance of R. We construct a solution for I by E. We first chase I with Σ st until no more rules are applicable, yielding an instance J. Because Σ st contains only stds (that is tgds on different source and target signatures), we know that J exists. We now show that no egd from Σ S is applicable to J. By contradiction, let mult ≤1 (T s , p) = ∀x, y 1 , y 2 . T s (x) ∧ Triple(x, p, y 1 ) ∧ Triple(x, p, y 2 ) ⇒ y 1 = y 2 be an egd that is applicable to J. That is, there is a homomorphism h : T s (x) ∧ Triple(x, p, y 1 ) ∧ Triple(x, p, y 2 ) → I s.t. Triple(h(x), p, h(y 1 )), Triple(h(x), p, h(y 2 )) and T s (h(x)) are facts in J and h(y 1 ) = h(y 2 ). By construction of J as the result of chasing I with Σ st and by the fact that Σ st is fully-typed, it follows that there are two (not necessarily distinct) stds σ i = ∀x, y i .φ i (x, y i ) ⇒ Triple(f (x), p, o i )∧T s (f (x))∧T o (o i ) and there exist h i : φ i → I homomorphisms satisfying the following: (2) f Fint (h i (x)) = h(x), and h i (z i ) = h(y i ) if o i = z i are variables, and g Fint (h i (z i )) = h(y i ) if o i = g(z i ) for some vectors of variables z i and function symbol g, for i = 1, 2. Then h 1 ∪ h 2 : φ 1 ∧ φ 2 → I is a homomorphism, and because E is key-covered we know that h 1 (o 1 ) = h 2 (o 2 ). This is a contradiction with h(y 1 ) = h(y 2 ) using (2) and the fact that the functions f Fint and g Fint are injective, and implies that no egd from Σ S is applicable to J.

Finally, we are going to add the facts J to J so that J ∪ J satisfies the tgds and the egd's in Σ S . Note that J does not satisfy Σ S because some of the mult ≥1 (T s , p) might not be satisfied. For any mult ≥1 (T s , p) in Σ S , let b Ts,p ∈ Blank be a blank node distinct from other such blank nodes, that is, b Ts,p = b To,p if T s = T o or p = p . Now, let J 1 and J 2 be the sets of facts defined by: J 1 = T 1 (b Ts,p ) | p :: T µ 1 ∈ δ(T s ) for µ ∈ {1, +} J 2 = Triple(b Ts,p , q, b T1,q ) | T 1 (b Ts,p ) ∈ J 1 and q :: T µ 2 ∈ δ(T 1 ) for µ ∈ {1, +} Intuitively, J 1 adds to the graph nodes b Ts,p whenever the property p is required by type T s in S. A property is required if it appears in a triple constraint with multiplicity 1 or +. Such node has type T 1 as required by the corresponding triple constraint p :: T µ 1 in δ(T s ). Then, J 2 adds to the graph triples for the properties q that are required by the nodes added by J 1 . Remark that J 1 ∪ J 2 is a correctly typed graph. We finally connect J 1 ∪ J 2 to J. Let Then G = J ∪ J 1 ∪ J 2 ∪ J 3 satisfies the tgds in Σ S . It remains to show that G also satisfies the egd's in Σ S . This is ensured by construction as J satisfies the egd's and J 2 and J 3 add a unique triple Triple(b, p, b ) only to unsatisfied typing requirements T s (b) for types T s , that is, for every Triple(b, p, b ) added by J 2 or J 3 there is no different Triple(b, p, b ) in J ∪ J 2 ∪ J 3 . This concludes the proof of Theorem 1.

C.2 Proof of Theorem 2

Let E = (R, S, Σ st , F, F int ) with S = (T , δ) and R = (R, Σ fd ) be a fully-typed data exchange setting.

Fig. 1 :

 1 Fig. 1: Relational database (source)

Fig. 2 :

 2 Fig. 2: Target RDF graph (solution)

  tc(T, S, p) := T (x) ∧ Triple(x, p, y) ⇒ S(y) mult ≥1 (T, p) := T (x) ⇒ ∃y.Triple(x, p, y) mult ≤1 (T, p) := T (x) ∧ Triple(x, p, y) ∧ Triple(x, p, z) ⇒ y = z

Lemma 1 .

 1 {tc(T, S, p) | T ∈ T , p :: S µ ∈ δ(T )} ∪ {mult ≥1 (T, p) | T ∈ T , p :: S µ ∈ δ(T ), µ ∈ {1, +}} ∪ {mult ≤1 (T, p) | T ∈ T , p :: S µ ∈ δ(T ), µ ∈ {1, ?}}. For every ShEx schema S = (T , δ) and every T -typed RDF graph (G, typing), (G, typing) is correctly typed w.r.t. S iff (G, typing) |= Σ S .

  Bug(b, d, u) ⇒ Triple(bug2iri(b),:descr, d) ∧ TBug(bug2iri(b)) ∧ Lit(d) Bug(b, d, u) ⇒ Triple(bug2iri(b),:rep, pers2iri(u)) ∧ TBug(bug2iri(b)) ∧ TUser(pers2iri(u))

Example 1 :

 1 TUser → {:name :: Lit 1 ,:email :: Lit 1 ,:phone :: Lit ? } TBug → {:rep :: TUser 1 ,:descr :: Lit 1 ,:related :: TBug * ,:repro :: TEmp ? } TEmp → {:name :: Lit 1 ,:prepare :: TTest + } TTest → {:covers :: TBug + }

-

  Lit ∈ typing(n) and n ∈ Lit. By definition of Lit, the node n is of type literal, means n ∈ Lit. Contradiction. -We have two sub-cases when T ∈ typing(n): • n ∈ Iri. By definition, all nodes of G are in the set Lit∪Iri∪Blank. Because T (n) is fact in (G, typing), then n ∈ Iri ∪ Blank. Because blank nodes are potentially IRIs, then n ∈ Iri. Contradiction. • There is a triple constraint p :: S µ ∈ δ(T ) such that * There is a triple (n, p, m) such that S ∈ typing(m). Since T (n) and Triple(n, p, m) are facts in (G, typing) and (G, typing) |= tc(T, S, p), then S(m) is fact in (G, typing). Thus, S ∈ typing(m). Contradiction. * Let K be the set of triples whose first element is n and second element is p. The cardinality of K is not bounded by µ. Thus, we have the following cases: • When µ = 1 and |K| = 1. It follows that mult ≤1 (T, S, p) ∈ Σ S and mult ≥1 (T, S, p) ∈ Σ S . Since (G, typing) |= Σ S , then |K| = 1. Contradiction. • When µ = ? and |K| > 1. It follows that mult ≤1 (T, S, p) ∈ Σ S . Since (G, typing) |= Σ S , then |K| ≤ 1. Contradiction. • When µ = + and |K| < 1. It follows that mult ≥1 (T, S, p) ∈ Σ S . Since (G, typing) |= Σ S , then |K| ≥ 1. Contradiction.

J 3 =

 3 Triple(a, p, b Ts,p ) | T s (a) ∈ J and ∃Triple(a, p, b ) in J and p :: T µ o ∈ δ(T s )

The proof goes by reduction to the problem of functional dependency propagation. We start by fixing some vocabulary and notions standard in databases. A view over a relational signature R is a set of queries over R. Recall that a n-ary query is a logical formula with n free variables. If V = {V 1 , . . . , V n } is a view, we see V as a relational signature, where the arity of the symbol V i is the same as the arity of the query V i , for 1 ≤ i ≤ n. Given a relational schema R = (R, Σ fd ), a view V, and an instance I of R, by V(I) we denote the result of applying the query V to I. The latter is an instance over the signature V.

Now, the problem of functional dependency propagation FDPROP(R, V, Σ V fd ) is defined as follows. Given a relational schema R = (R, Σ fd ), a view V over R, and a set of functional dependencies Σ V fd over V, R = (R, Σ fd ) holds iff for any I valid instance of R, V(I) |= Σ V fd . It is known by [START_REF] Klug | Determining View Dependencies Using Tableaux[END_REF] that the problem FDPROP(R, V, Σ V fd ) is decidable. We will construct a view V and a set Σ V fd of functional dependencies over V s.t. FDPROP(R, V, Σ V fd ) iff E is key-covered. Let σ 1 , σ 2 be two contentious stds from Σ st that are functionally overlapping as those in the premise of the key-coverdness condition. That is, for some T s , T o , p, f , for i = 1, 2, we have

Recall that o i and o i and either both variables, or are both functional terms with the same function symbol. Let z, resp. z be the vectors of variables is o 1 , resp. o 2 . That is, if e.g. o 1 is a variable then z is a vector of length one of this variable, and if o 1 = g(z 1 , . . . , z n ) for some function symbol g, then z = z 1 , . . . , z n . Remark that z ⊆ x∪y 1 , and similarly for z . Now, for any such couple σ 1 , σ 2 of two (not necessarily distinct) stds, we define the query V σ1,σ2 as the union of two queries, and the functional dependency fd σ1,σ2 , as follows.

where for any two vectors of variables y and z, y -z designates the set of variables y\z, and m is the length of x, and n is the length of z and z . Then

as in the premise of the condition for key-covered} (5)

as in the premise of the condition for key-covered

The sequel is the proof that FDPROP(R, V, Σ V fd ) iff E is key-covered, which by [START_REF] Klug | Determining View Dependencies Using Tableaux[END_REF] implies that key-coverdness is decidable.

For the ⇒ direction, suppose that FDPROP(R, V, Σ V fd ). Let I a valid instance of R and let J = V(I). We show that for any two contentious stds σ 1 , σ 2 ∈ Σ st that are functionally overlapping as in the premise of the condition for key-covered, it holds that

Let ν be a valuation of the variables x 1 ∪y 1 ∪y 2 s.t. I ∪F int , ν |= φ 1 ∧φ 2 . By definition of q σ1 and q σ2 and x 1 = x 2 it is easy to see that V σ1,σ2 (ν(x 1 ), ν(z)), and V σ1,σ2 (ν(x 2 ), ν(z )) are facts in J Because J satisfies fd σ1,σ2 , we deduce that ν(z) = ν(z ), therefore ν Fint (o 1 ) = ν Fint (o 2 ), which concludes the proof of the ⇒ direction.

For the ⇐ direction, suppose that E is key-covered. Let I a valid instance of R and let J = V(I).

, 2 be two stds in Σ st that satisfy the premise for key-covered. Let V σ1,σ2 (a, b) and V σ1,σ2 (a, b ) be two facts in J. That is, by definition and x 1 = x 2 there exist valuations ν of the variables y -z 1 and ν of the variables y -z 2 s.t. I, ν[x 1 /a, z/b] |= φ 1 (x 1 , y 1 ) and I, ν [x 2 /a, z /b ] |= φ 2 (x 2 , y 2 ). We now distinguish two cases, depending on whether the two facts were generated by the same query V σi (for some i ∈ 1..2), or one was generated by V σ1 and the other one by V σ2 .

- This concludes the proof of Theorem 2.