Edinburgh Research Explorer

Discovering Graph Functional Dependencies

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://dl.acm.org/citation.cfm?doid=3183713.3196916
Original languageEnglish
Title of host publicationProceedings of the 2018 International Conference on Management of Data (SIGMOD'18)
Place of PublicationTexas, USA
PublisherACM
Pages427-439
Number of pages13
ISBN (Electronic)978-1-4503-4703-7
DOIs
Publication statusPublished - 27 May 2018
Event2018 ACM SIGMOD/PODS International Conference on Management of Data - Houston, United States
Duration: 10 Jun 201815 Jun 2018
https://sigmod2018.org/

Conference

Conference2018 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD'18
CountryUnited States
CityHouston
Period10/06/1815/06/18
Internet address

Abstract

This paper studies discovery of GFDs, a class of functional dependencies defined on graphs. We investigate the fixed-parameter tractability of three fundamental problems related to GFD discovery. We show that the implication and satisfiability problems are fixed-parameter tractable, but the validation problem is co-W[1]-hard. We introduce notions of reduced GFDs and their topological support, and formalize the discovery problem for GFDs. We develop algorithms for discovering GFDs and computing their covers. Moreover, we show that GFD discovery is feasible over large-scale graphs, by providing parallel scalable algorithms for discovering GFDs that guarantee to reduce running time when more processors are used. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms.

    Research areas

  • GFD discovery, parallel scalable, fixed-parameter tractability

Event

2018 ACM SIGMOD/PODS International Conference on Management of Data

10/06/1815/06/18

Houston, United States

Event: Conference

Download statistics

No data available

ID: 64280118