TY - GEN
T1 - Discovering graph functional dependencies
AU - Fan, Wenfei
AU - Hu, Chunming
AU - Liu, Xueli
AU - Lu, Ping
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/5/27
Y1 - 2018/5/27
N2 - 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.
AB - 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.
KW - Fixed-parameter tractability
KW - GFD discovery
KW - Parallel scalable
UR - https://www.scopus.com/pages/publications/85048744843
U2 - 10.1145/3183713.3196916
DO - 10.1145/3183713.3196916
M3 - 会议稿件
AN - SCOPUS:85048744843
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
SP - 427
EP - 439
BT - SIGMOD 2018 - Proceedings of the 2018 International Conference on Management of Data
A2 - Das, Gautam
A2 - Jermaine, Christopher
A2 - Eldawy, Ahmed
A2 - Bernstein, Philip
PB - Association for Computing Machinery
T2 - 44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018
Y2 - 10 June 2018 through 15 June 2018
ER -