Edinburgh Research Explorer

Functional Dependencies for Graphs

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=2915232
Original languageEnglish
Title of host publicationSIGMOD '16 Proceedings of the 2016 International Conference on Management of Data
Place of PublicationSan Francisco, USA
PublisherACM
Pages1843-1857
Number of pages15
ISBN (Print)978-1-4503-3531-7
DOIs
Publication statusPublished - 26 Jun 2016
Event2016 International Conference on Management of Data - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016
http://sigmod2016.org/

Conference

Conference2016 International Conference on Management of Data
Abbreviated titleSIGMOD/PODS'16
CountryUnited States
CitySan Francisco
Period26/06/161/07/16
Internet address

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.

Event

2016 International Conference on Management of Data

26/06/161/07/16

San Francisco, United States

Event: Conference

Download statistics

No data available

ID: 25032713