On the complexity of finding set repairs for data-graphs

• URL: http://arxiv.org/abs/2206.07504v1
• Date: Wed, 15 Jun 2022 13:01:26 GMT
• Title: On the complexity of finding set repairs for data-graphs
• Authors: Sergio Abriola, Santiago Cifuentes, Mar\'ia Vanina Mart\'inez, Nina Pardal, Edwin Pin
• Abstract summary: We study the problem of computing a subset and superset repairs for graph databases with data values. We show that for positive fragments of Reg-GX expressions these problems admit a subset-time algorithm, while the full expressive power of the language renders them intractable.
• Score: 2.519906683279153
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the deeply interconnected world we live in, pieces of information link domains all around us. As graph databases embrace effectively relationships among data and allow processing and querying these connections efficiently, they are rapidly becoming a popular platform for storage that supports a wide range of domains and applications. As in the relational case, it is expected that data preserves a set of integrity constraints that define the semantic structure of the world it represents. When a database does not satisfy its integrity constraints, a possible approach is to search for a 'similar' database that does satisfy the constraints, also known as a repair. In this work, we study the problem of computing subset and superset repairs for graph databases with data values using a notion of consistency based on a set of Reg-GXPath expressions as integrity constraints. We show that for positive fragments of Reg-GXPath these problems admit a polynomial-time algorithm, while the full expressive power of the language renders them intractable.

Related papers

• CHESS: Contextual Harnessing for Efficient SQL Synthesis [1.9506402593665235]
  We propose a new pipeline that retrieves relevant data and context, selects an efficient schema, and synthesizes correct and efficient queries. Our method achieves new state-of-the-art performance on the cross-domain challenging BIRD dataset.
  arXiv  Detail & Related papers  (2024-05-27T01:54:16Z)
• Federated Neural Graph Databases [53.03085605769093]
  We propose Federated Neural Graph Database (FedNGDB), a novel framework that enables reasoning over multi-source graph-based data while preserving privacy. Unlike existing methods, FedNGDB can handle complex graph structures and relationships, making it suitable for various downstream tasks.
  arXiv  Detail & Related papers  (2024-02-22T14:57:44Z)
• Computational Complexity of Preferred Subset Repairs on Data-Graphs [2.254434034390529]
  We study the problem of computing prioritized repairs over graph databases with data values. We present several preference criteria based on the standard subset repair semantics. We show that it is possible to maintain the same computational complexity as in the case where no preference criterion is available for exploitation.
  arXiv  Detail & Related papers  (2024-02-14T15:51:55Z)
• Relational Deep Learning: Graph Representation Learning on Relational Databases [69.7008152388055]
  We introduce an end-to-end representation approach to learn on data laid out across multiple tables. Message Passing Graph Neural Networks can then automatically learn across the graph to extract representations that leverage all data input.
  arXiv  Detail & Related papers  (2023-12-07T18:51:41Z)
• Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints [5.87010466783654]
  This paper revisits the problem of repairing and querying inconsistent databases equipped with universal constraints. We adopt symmetric difference repairs, in which both deletions and additions of facts can be used to restore consistency. We show how existing notions of optimal repairs, defined for simpler denial constraints and repairs solely based on fact deletion, can be suitably extended to our richer setting.
  arXiv  Detail & Related papers  (2023-06-06T09:17:56Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• LGPMA: Complicated Table Structure Recognition with Local and Global Pyramid Mask Alignment [54.768354427967296]
  Table structure recognition is a challenging task due to the various structures and complicated cell spanning relations. We propose the framework of Local and Global Pyramid Mask Alignment, which adopts the soft pyramid mask learning mechanism in both the local and global feature maps. A pyramid mask re-scoring module is then integrated to compromise the local and global information and refine the predicted boundaries.
  arXiv  Detail & Related papers  (2021-05-13T12:24:12Z)
• Topological Data Analysis of Database Representations for Information Retrieval [2.729524133721473]
  Persistent homology provides a rigorous characterization for the database topology. We show that some commonly used embeddings fail to preserve the connectivity. We introduce the dilation-invariant bottleneck distance to capture this effect.
  arXiv  Detail & Related papers  (2021-04-04T19:29:47Z)
• Dynamic Hybrid Relation Network for Cross-Domain Context-Dependent Semantic Parsing [52.24507547010127]
  Cross-domain context-dependent semantic parsing is a new focus of research. We present a dynamic graph framework that effectively modelling contextual utterances, tokens, database schemas, and their complicated interaction as the conversation proceeds. The proposed framework outperforms all existing models by large margins, achieving new state-of-the-art performance on two large-scale benchmarks.
  arXiv  Detail & Related papers  (2021-01-05T18:11:29Z)
• Partially-Aligned Data-to-Text Generation with Distant Supervision [69.15410325679635]
  We propose a new generation task called Partially-Aligned Data-to-Text Generation (PADTG) It is more practical since it utilizes automatically annotated data for training and thus considerably expands the application domains. Our framework outperforms all baseline models as well as verify the feasibility of utilizing partially-aligned data.
  arXiv  Detail & Related papers  (2020-10-03T03:18:52Z)
• On Embeddings in Relational Databases [11.52782249184251]
  We address the problem of learning a distributed representation of entities in a relational database using a low-dimensional embedding. Recent methods for learning embedding constitute of a naive approach to consider complete denormalization of the database by relationalizing the full join of all tables and representing as a knowledge graph. In this paper we demonstrate; a better methodology for learning representations by exploiting the underlying semantics of columns in a table while using the relation joins and the latent inter-row relationships.
  arXiv  Detail & Related papers  (2020-05-13T17:21:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.