Parallel Reasoning of Graph Functional Dependencies

Wenfei Fan; Xueli Liu; Yingjie Cao

doi:10.1109/ICDE.2018.00060

Parallel Reasoning of Graph Functional Dependencies

Wenfei Fan, Xueli Liu, Yingjie Cao

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	34th IEEE International Conference on Data Engineering 2018 (ICDE)
Place of Publication	Paris, France
Publisher	Institute of Electrical and Electronics Engineers
Pages	593-604
Number of pages	12
ISBN (Electronic)	978-1-5386-5520-7
ISBN (Print)	978-1-5386-5521-4
DOIs	https://doi.org/10.1109/ICDE.2018.00060
Publication status	Published - 25 Oct 2018
Event	34th IEEE International Conference on Data Engineering - Paris, France Duration: 16 Apr 2018 → 19 Apr 2018 https://icde2018.org/

Publication series

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

Conference

Conference	34th IEEE International Conference on Data Engineering
Abbreviated title	ICDE 2018
Country/Territory	France
City	Paris
Period	16/04/18 → 19/04/18
Internet address	https://icde2018.org/

Access to Document

10.1109/ICDE.2018.00060

parallel_reasoning_of_graph_functional_dependencies_2018Accepted author manuscript, 313 KB

https://ieeexplore.ieee.org/document/8509281

GRACE-Resource Bounded Graph Query Answering
Fan, W. (Principal Investigator)
EU government bodies
1/11/15 → 31/10/21
Project: Research
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L. (Principal Investigator), Buneman, P. (Co-investigator), Fan, W. (Co-investigator) & Pieris, A. (Co-investigator)
EPSRC
1/04/15 → 30/09/20
Project: Research

Cite this

@inproceedings{c0ca7a241cde4dbc80178f5747b75bdf,

title = "Parallel Reasoning of Graph Functional Dependencies",

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.",

author = "Wenfei Fan and Xueli Liu and Yingjie Cao",

year = "2018",

month = oct,

day = "25",

doi = "10.1109/ICDE.2018.00060",

language = "English",

isbn = "978-1-5386-5521-4",

publisher = "Institute of Electrical and Electronics Engineers",

pages = "593--604",

booktitle = "34th IEEE International Conference on Data Engineering 2018 (ICDE)",

address = "United States",

note = "34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

url = "https://icde2018.org/",

}

TY - GEN

T1 - Parallel Reasoning of Graph Functional Dependencies

AU - Fan, Wenfei

AU - Liu, Xueli

AU - Cao, Yingjie

PY - 2018/10/25

Y1 - 2018/10/25

N2 - 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.

AB - 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.

U2 - 10.1109/ICDE.2018.00060

DO - 10.1109/ICDE.2018.00060

M3 - Conference contribution

SN - 978-1-5386-5521-4

SP - 593

EP - 604

BT - 34th IEEE International Conference on Data Engineering 2018 (ICDE)

PB - Institute of Electrical and Electronics Engineers

CY - Paris, France

T2 - 34th IEEE International Conference on Data Engineering

Y2 - 16 April 2018 through 19 April 2018

ER -

Parallel Reasoning of Graph Functional Dependencies

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

GRACE-Resource Bounded Graph Query Answering

VADA: Value Added Data Systems: Principles and Architecture

Cite this