Abstract / Description of output
This paper proposes a class of dependencies for graphs, referred to as graph entity dependencies (GEDs). A GED is a combination of a graph pattern and an attribute dependency. In a uniform format, GEDs express graph functional dependencies with constant literals to catch inconsistencies, and keys carrying id literals to identify entities in a graph.
We revise the chase for GEDs and prove its Church-Rosser property. We characterize GED satisfiability and implication, and establish the complexity of these problems and the validation problem for GEDs, in the presence and absence of constant literals and id literals. We also develop a sound and complete axiom system for finite implication of GEDs. In addition, we extend GEDs with built-in predicates or disjunctions, to strike a balance between the expressive power and complexity. We settle the complexity of the satisfiability, implication and validation problems for the extensions.
We revise the chase for GEDs and prove its Church-Rosser property. We characterize GED satisfiability and implication, and establish the complexity of these problems and the validation problem for GEDs, in the presence and absence of constant literals and id literals. We also develop a sound and complete axiom system for finite implication of GEDs. In addition, we extend GEDs with built-in predicates or disjunctions, to strike a balance between the expressive power and complexity. We settle the complexity of the satisfiability, implication and validation problems for the extensions.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
| Place of Publication | New York, NY, USA |
| Publisher | ACM |
| Pages | 403-416 |
| Number of pages | 14 |
| ISBN (Print) | 978-1-4503-4198-1 |
| DOIs | |
| Publication status | Published - 9 May 2017 |
| Event | 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - New York, United States Duration: 14 May 2017 → 19 May 2017 |
Publication series
| Name | PODS '17 |
|---|---|
| Publisher | ACM |
Conference
| Conference | 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
|---|---|
| Country/Territory | United States |
| City | New York |
| Period | 14/05/17 → 19/05/17 |
Fingerprint
Dive into the research topics of 'Dependencies for Graphs'. Together they form a unique fingerprint.Profiles
-
Wenfei Fan
- School of Informatics - Personal Chair in Web Data Management
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active