Projects per year
Abstract
We propose a class of functional dependencies for graphs, referred to as GFDs. GFDs capture both attribute-value dependencies and topological structures of entities, and subsume conditional functional dependencies (CFDs) as a special case.We show that the satisfiability and implication problems for GFDs are coNP-complete and NP-complete, respectively,no worse than their CFD counterparts. We also show that the validation problem for GFDs is coNP-complete. Despite the intractability, we develop parallel scalable algorithms for catching violations of GFDs in large-scale graphs. Using real life and synthetic data, we experimentally verify that GFDs provide an effective approach to detecting inconsistencies in knowledge and social graphs.
Original language | English |
---|---|
Title of host publication | SIGMOD '16 Proceedings of the 2016 International Conference on Management of Data |
Place of Publication | San Francisco, USA |
Publisher | ACM |
Pages | 1843-1857 |
Number of pages | 15 |
ISBN (Print) | 978-1-4503-3531-7 |
DOIs | |
Publication status | Published - 26 Jun 2016 |
Event | 2016 International Conference on Management of Data - San Francisco, United States Duration: 26 Jun 2016 → 1 Jul 2016 http://sigmod2016.org/ |
Conference
Conference | 2016 International Conference on Management of Data |
---|---|
Abbreviated title | SIGMOD/PODS'16 |
Country/Territory | United States |
City | San Francisco |
Period | 26/06/16 → 1/07/16 |
Internet address |
Fingerprint
Dive into the research topics of 'Functional Dependencies for Graphs'. 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
-
Querying Graph Structured Data: Principles and Techniques
Libkin, L. (Principal Investigator) & Fan, W. (Co-investigator)
1/11/13 → 31/10/16
Project: Research