Functional Dependencies for Graphs

Wenfei Fan; Yinghui Wu; Jingbo Xu

doi:10.1145/2882903.2915232

Functional Dependencies for Graphs

Wenfei Fan, Yinghui Wu, Jingbo Xu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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	https://doi.org/10.1145/2882903.2915232
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	United States
City	San Francisco
Period	26/06/16 → 1/07/16
Internet address	http://sigmod2016.org/

Access to Document

10.1145/2882903.2915232

sigmod16-GFDAccepted author manuscript, 544 KB

http://dl.acm.org/citation.cfm?id=2915232

1 Finished
1 Active

GRACE-Resource Bounded Graph Query Answering
Fan, W.
EU government bodies
1/11/15 → 31/10/21
Project: Research
Querying Graph Structured Data: Principles and Techniques
Libkin, L. & Fan, W.
EPSRC
1/11/13 → 31/10/16
Project: Research

Cite this

@inproceedings{88cc9c7f0f154b8384e3bfc0106af107,

title = "Functional Dependencies for Graphs",

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.",

author = "Wenfei Fan and Yinghui Wu and Jingbo Xu",

year = "2016",

month = jun,

day = "26",

doi = "10.1145/2882903.2915232",

language = "English",

isbn = "978-1-4503-3531-7",

pages = "1843--1857 ",

booktitle = "SIGMOD '16 Proceedings of the 2016 International Conference on Management of Data",

publisher = "ACM",

note = "2016 International Conference on Management of Data, SIGMOD/PODS'16 ; Conference date: 26-06-2016 Through 01-07-2016",

url = "http://sigmod2016.org/",

}

TY - GEN

T1 - Functional Dependencies for Graphs

AU - Fan, Wenfei

AU - Wu, Yinghui

AU - Xu, Jingbo

PY - 2016/6/26

Y1 - 2016/6/26

N2 - 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.

AB - 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.

U2 - 10.1145/2882903.2915232

DO - 10.1145/2882903.2915232

M3 - Conference contribution

SN - 978-1-4503-3531-7

SP - 1843

EP - 1857

BT - SIGMOD '16 Proceedings of the 2016 International Conference on Management of Data

PB - ACM

CY - San Francisco, USA

T2 - 2016 International Conference on Management of Data

Y2 - 26 June 2016 through 1 July 2016

ER -

Functional Dependencies for Graphs

Abstract

Conference

Access to Document

GRACE-Resource Bounded Graph Query Answering

Querying Graph Structured Data: Principles and Techniques

Cite this