Projects per year
Abstract
This paper develops techniques for reasoning about graph functional dependencies (GFDs). We study the satisfiability problem, to decide whether a given set of GFDs has a model, and the implication problem, to decide whether a set of GFDs entails another GFD. While these fundamental problems are important in practice, they are coNP-complete and NP-complete, respectively. We establish a small model property for satisfiability, showing that if a set Σ of GFDs is satisfiable, then it has a model of a size bounded by the size |Σ| of Σ; similarly we prove a small model property for implication. Based on the properties, we develop algorithms for checking the satisfiability and implication of GFDs. Moreover, we provide parallel algorithms that guarantee to reduce running time when more processors are used, despite the intractability of the problems. We experimentally verify the efficiency and scalability of the algorithms.
Original language | English |
---|---|
Title of host publication | 34th IEEE International Conference on Data Engineering 2018 (ICDE) |
Place of Publication | Paris, France |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 593-604 |
Number of pages | 12 |
ISBN (Electronic) | 978-1-5386-5520-7 |
ISBN (Print) | 978-1-5386-5521-4 |
DOIs | |
Publication status | Published - 25 Oct 2018 |
Event | 34th IEEE International Conference on Data Engineering - Paris, France Duration: 16 Apr 2018 → 19 Apr 2018 https://icde2018.org/ |
Publication series
Name | |
---|---|
Publisher | IEEE |
ISSN (Print) | 1063-6382 |
ISSN (Electronic) | 2375-026X |
Conference
Conference | 34th IEEE International Conference on Data Engineering |
---|---|
Abbreviated title | ICDE 2018 |
Country/Territory | France |
City | Paris |
Period | 16/04/18 → 19/04/18 |
Internet address |
Fingerprint
Dive into the research topics of 'Parallel Reasoning of Graph Functional Dependencies'. Together they form a unique fingerprint.Projects
- 2 Finished
-
GRACE-Resource Bounded Graph Query Answering
Fan, W. (Principal Investigator)
1/11/15 → 31/10/21
Project: Research
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L. (Principal Investigator), Buneman, P. (Co-investigator), Fan, W. (Co-investigator) & Pieris, A. (Co-investigator)
1/04/15 → 30/09/20
Project: Research