Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14571
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | AMELOOT, Tom | - |
dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
dc.date.accessioned | 2013-02-06T07:58:36Z | - |
dc.date.available | 2013-02-06T07:58:36Z | - |
dc.date.issued | 2013 | - |
dc.identifier.uri | http://hdl.handle.net/1942/14571 | - |
dc.description.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 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.iso | en | - |
dc.subject.other | relational transducer; eventual consistency; decidability; complexity; expressivity | - |
dc.title | Deciding Eventual Consistency for a Simple Class of Relational Transducer Networks | - |
dc.type | Research Report | - |
local.format.pages | 72 | - |
local.bibliographicCitation.jcat | R2 | - |
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.refereed | Refereed | - |
local.type.specified | Research Report | - |
item.contributor | AMELOOT, Tom | - |
item.contributor | VAN DEN BUSSCHE, Jan | - |
item.fulltext | With Fulltext | - |
item.accessRights | Open Access | - |
item.fullcitation | AMELOOT, Tom & VAN DEN BUSSCHE, Jan (2013) Deciding Eventual Consistency for a Simple Class of Relational Transducer Networks. | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tocs_techreport.pdf | Peer-reviewed author version | 960.6 kB | Adobe PDF | View/Open |
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.