Loading...
Please wait, while we are loading the content...
Similar Documents
Explorer Functional Dependencies for Graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fan, Wenfei Wu, Yinghui Xu, Jingbo |
| Copyright Year | 2016 |
| 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 reallife and synthetic data, we experimentally verify that GFDs provide an effective approach to detecting inconsistencies in knowledge and social graphs. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.research.ed.ac.uk/portal/files/25032715/sigmod16_GFD.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
