Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/20633
Title: Deciding Confluence for a Simple Class of Relational Transducer Networks
Authors: AMELOOT, Tom 
VAN DEN BUSSCHE, Jan 
Issue Date: 2015
Publisher: SPRINGER
Source: THEORY OF COMPUTING SYSTEMS, 57 (4), p. 1038-1111
Abstract: Networks of relational transducers can serve as a formal model for declarative networking, focusing on distributed database querying applications. In declarative networking, a crucial property is eventual consistency, meaning that the final output does not depend on the message delays and reorderings caused by the network. Here, we formalize eventual consistency as a confluence notion, meaning that finite executions of the system can always be extended to yield the desired output. We show that confluence is decidable when the transducers satisfy some syntactic restrictions, some of which have also been considered in earlier work on automated verification of relational transducers. This simple class of transducer networks computes exactly all distributed queries expressible by unions of conjunctive queries with negation.
Notes: [Ameloot, Tom J.; Van den Bussche, Jan] Hasselt Univ, Hasselt, Belgium. [Ameloot, Tom J.; Van den Bussche, Jan] Transnat Univ Limburg, Hasselt, Belgium.
Keywords: Relational transducer; Eventual consistency; Confluence; Decidability; Conjunctive query;relational transducer; eventual consistency; confluence; decidability; conjunctive query
Document URI: http://hdl.handle.net/1942/20633
ISSN: 1432-4350
e-ISSN: 1433-0490
DOI: 10.1007/s00224-015-9624-6
ISI #: 000365792200008
Rights: © Springer Science+Business Media New York 2015
Category: A1
Type: Journal Contribution
Validations: ecoom 2016
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
art%3A10.1007%2Fs00224-015-9624-6.pdf
  Restricted Access
published version940.37 kBAdobe PDFView/Open    Request a copy
icdt12journal.pdfauthor version960.89 kBAdobe PDFView/Open
Show full item record

Page view(s)

52
checked on May 28, 2022

Download(s)

170
checked on May 28, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.