FastGFDs: Efficient Graph Functional Dependency Validation with Desbordante

This paper introduces FastGFDs, a sequential algorithm for validating graph functional dependencies (GFDs) on consumer-class, single-node machines. It targets the dominant bottleneck in GFD validation: locating suitable subgraphs, which accounts for about 99% of total runtime according to the abstract. FastGFDs combines Core-First Decomposition with a Compact Path Index (CPI) and operates over the entire graph. On a real-life graph, the authors report up to 3x speedup over the prior parallel scheme, with an average improvement of 2.6x, while reducing memory consumption fivefold. An open-source implementation is included in Desbordante.