Discovering Graph Functional Dependencies
Citations Over TimeTop 10% of 2020 papers
Abstract
This article studies discovery of Graph Functional Dependencies (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 in general. 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 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.
Related Papers
- Problem Decomposition Method to Compute an Optimal Cover for a Set of Functional Dependencies(2011)
- → Data dependencies over rough relational expressions(2002)2 cited
- → Functional Dependencies in Relational Expressions Based on Or-Sets(2002)
- Letting keys and functional dependencies out of the bag(2013)
- RESEARCH ON THE SCALABILITY OF THE LARGE SCALE PARALLEL APPLICATION PROGRAMS(2000)