Functional Dependencies for Graphs Article Swipe

PDF

Related Concepts

Functional dependency Scalability Computer science Satisfiability Theoretical computer science Class (philosophy) Dependency theory (database theory) Boolean satisfiability problem Data mining Artificial intelligence Relational database Database

Wenfei Fan , Yinghui Wu , Jingbo Xu ·

YOU? · · 2016 · Open Access · · DOI: https://doi.org/10.1145/2882903.2915232 · OA: W2425348221

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.