Functional Dependencies for Graphs

Wenfei Fan, Yinghui Wu, Jingbo Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 languageEnglish
Title of host publicationSIGMOD '16 Proceedings of the 2016 International Conference on Management of Data
Place of PublicationSan Francisco, USA
Number of pages15
ISBN (Print)978-1-4503-3531-7
Publication statusPublished - 26 Jun 2016
Event2016 International Conference on Management of Data - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016


Conference2016 International Conference on Management of Data
Abbreviated titleSIGMOD/PODS'16
Country/TerritoryUnited States
CitySan Francisco
Internet address


Dive into the research topics of 'Functional Dependencies for Graphs'. Together they form a unique fingerprint.

Cite this