Edinburgh Research Explorer

Dependencies for Graphs

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=3056114
Original languageEnglish
Title of host publicationProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationNew York, NY, USA
PublisherACM
Pages403-416
Number of pages14
ISBN (Print)978-1-4503-4198-1
DOIs
Publication statusPublished - 9 May 2017
Event36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - New York, United States
Duration: 14 May 201719 May 2017

Publication series

NamePODS '17
PublisherACM

Conference

Conference36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
CountryUnited States
CityNew York
Period14/05/1719/05/17

Abstract

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.

Event

36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

14/05/1719/05/17

New York, United States

Event: Conference

Download statistics

No data available

ID: 39094158