2026-07-24T00:18:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15888 2024-03-06T10:56:26Z ddc:004 open_access

Inference of Shape Graphs for Graph Databases Groz, Benoît Lemay, Aurélien Staworko, Sławek Wieczorek, Piotr RDF Schema Inference Learning Fitting Minimality Containment 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benoît Groz and Aurélien Lemay and Sławek Staworko and Piotr Wieczorek 2022 Is Part Of LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2022.14 urn:nbn:de:0030-drops-158889 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode