Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14571
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAMELOOT, Tom-
dc.contributor.authorVAN DEN BUSSCHE, Jan-
dc.date.accessioned2013-02-06T07:58:36Z-
dc.date.available2013-02-06T07:58:36Z-
dc.date.issued2013-
dc.identifier.urihttp://hdl.handle.net/1942/14571-
dc.description.abstractNetworks 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 show that eventual consistency 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.-
dc.language.isoen-
dc.subject.otherrelational transducer; eventual consistency; decidability; complexity; expressivity-
dc.titleDeciding Eventual Consistency for a Simple Class of Relational Transducer Networks-
dc.typeResearch Report-
local.format.pages72-
local.bibliographicCitation.jcatR2-
dc.relation.references[1] S. Abiteboul, M. Bienvenu, A. Galland, et al. A rule-based language for Web data management. In Proceedings 30th ACM Symposium on Principles of Database Systems, pages 293–304. ACM Press, 2011. [2] S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison- Wesley, 1995. [3] S. Abiteboul, V. Vianu, et al. Relational transducers for electronic com- merce. Journal of Computer and System Sciences, 61(2):236–269, 2000. [4] P. Alvaro, N. Conway, J. Hellerstein, and W.R. Marczak. Consistency analysis in Bloom: A CALM and collected approach. In Proceedings 5th Biennial Conference on Innovative Data Systems Research, pages 249–260. www.cidrdb.org, 2011. [5] P. Alvaro, W. Marczak, et al. Dedalus: Datalog in time and space. Tech- nical Report EECS-2009-173, University of California, Berkeley, 2009. [6] T.J. Ameloot, F. Neven, and J. Van den Bussche. Relational transducers for declarative networking. In Proceedings 30th ACM Symposium on Principles of Database Systems, pages 283–292. ACM Press, 2011. [7] T.J. Ameloot and J. Van den Bussche. Deciding eventual consistency for a simple class of relational transducer networks. In Proceedings of the 15th International Conference on Database Theory, pages 86–98. ACM Press, 2012. [8] A.K. Chandra and M.Y. Vardi. The implication problem for functional and inclusion dependencies is undecidable. SIAM Journal on Computing, 14(3):671–677, 1985. [9] A. Deutsch. Personal communication. 2011. [10] A. Deutsch, R. Hull, F. Patrizi, and V. Vianu. Automatic verification of data-centric business processes. In Proceedings 12th International Confer- ence on Database Theory, 2009. [11] A. Deutsch, L. Sui, and V. Vianu. Specification and verification of data- driven Web applications. Journal of Computer and System Sciences, 73(3):442–474, 2007. [12] A. Deutsch, L. Sui, V. Vianu, and D. Zhou. Verification of communicat- ing data-driven Web services. In Proceedings 25th ACM Symposium on Principles of Database Systems, pages 90–99. ACM Press, 2006. [13] S. Grumbach and F. Wang. Netlog, a rule-based language for distributed programming. In M. Carro and R. Peña, editors, Proceedings 12th Interna- tional Symposium on Practical Aspects of Declarative Languages, volume 5937 of Lecture Notes in Computer Science, pages 88–103, 2010. [14] J.M. Hellerstein. Datalog redux: experience and conjecture. Video avail- able (under the title “The Declarative Imperative”) from http://db.cs. berkeley.edu/jmh/, 2010. PODS 2010 keynote. [15] J.M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Record, 39(1):5–19, 2010. [16] B.T. Loo et al. Declarative networking. Communications of the ACM, 52(11):87–95, 2009. [17] W.R. Marczak, P. Alvaro, N. Conway, J.M. Hellerstein, and D. Maier. Confluence analysis for distributed programs: A model-theoretic approach. In P. Barceló and R. Pichler, editors, Datalog, volume 7494 of Lecture Notes in Computer Science, pages 135–147. Springer, 2012. [18] J.A. Navarro and A. Rybalchenko. Operational semantics for declarative networking. In A. Gill and T. Swift, editors, Proceedings 11th International Symposium on Practical Aspects of Declarative Languages, volume 5419 of Lecture Notes in Computer Science, pages 76–90, 2009. [19] E.L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264–268, 1946. [20] M. Sipser. Introduction to the Theory of Computation, Second Edition, In- ternational Edition. Thomson Course Technology, Boston, Massachusetss, USA, 2006. [21] M. Spielmann. Verification of relational transducers for electronic com- merce. Journal of Computer and System Sciences, 66(1):40–65, 2003. [22] W. Vogels. Eventual consistency. Communications of the ACM, 52(1):40– 44, 2009. [23] D. Zinn, T.J. Green, and B. Ludaescher. Win-move is coordination-free. In Proceedings of the 15th International Conference on Database Theory, pages 99–113. ACM Press, 2012.-
local.type.refereedRefereed-
local.type.specifiedResearch Report-
item.accessRightsOpen Access-
item.fulltextWith Fulltext-
item.fullcitationAMELOOT, Tom & VAN DEN BUSSCHE, Jan (2013) Deciding Eventual Consistency for a Simple Class of Relational Transducer Networks.-
item.contributorAMELOOT, Tom-
item.contributorVAN DEN BUSSCHE, Jan-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
tocs_techreport.pdfPeer-reviewed author version960.6 kBAdobe PDFView/Open
Show simple item record

Page view(s)

56
checked on Sep 6, 2022

Download(s)

134
checked on Sep 6, 2022

Google ScholarTM

Check


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