Parallel Reasoning of Graph Functional Dependencies

Wenfei Fan, Xueli Liu, Yingjie Cao

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

Abstract

This paper develops techniques for reasoning about graph functional dependencies (GFDs). We study the satisfiability problem, to decide whether a given set of GFDs has a model, and the implication problem, to decide whether a set of GFDs entails another GFD. While these fundamental problems are important in practice, they are coNP-complete and NP-complete, respectively. We establish a small model property for satisfiability, showing that if a set Σ of GFDs is satisfiable, then it has a model of a size bounded by the size |Σ| of Σ; similarly we prove a small model property for implication. Based on the properties, we develop algorithms for checking the satisfiability and implication of GFDs. Moreover, we provide parallel algorithms that guarantee to reduce running time when more processors are used, despite the intractability of the problems. We experimentally verify the efficiency and scalability of the algorithms.
Original languageEnglish
Title of host publication34th IEEE International Conference on Data Engineering 2018 (ICDE)
Place of PublicationParis, France
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages593-604
Number of pages12
ISBN (Electronic)978-1-5386-5520-7
ISBN (Print)978-1-5386-5521-4
DOIs
Publication statusPublished - 25 Oct 2018
Event34th IEEE International Conference on Data Engineering - Paris, France
Duration: 16 Apr 201819 Apr 2018
https://icde2018.org/

Publication series

Name
PublisherIEEE
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X

Conference

Conference34th IEEE International Conference on Data Engineering
Abbreviated titleICDE 2018
CountryFrance
CityParis
Period16/04/1819/04/18
Internet address

Fingerprint Dive into the research topics of 'Parallel Reasoning of Graph Functional Dependencies'. Together they form a unique fingerprint.

Cite this