Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Bidirectional Collaborative Frameworks for Decentralized Data Management

  • Conference paper
  • First Online:
Software Foundations for Data Interoperability (SFDI 2021)

Part of the book series: Communications in Computer and Information Science ((CCIS,volume 1457))

  • 375 Accesses

Abstract

Along with the continuous evolution of data management systems for the new market requirements, we are moving from centralized systems towards decentralized systems, where data are maintained in different sites with autonomous storage and computation capabilities. There are two fundamental issues with such decentralized systems: local privacy and global consistency. By local privacy, the data owner wishes to control what information should be exposed and how it should be used or updated by other peers. By global consistency, the systems wish to have a globally consistent and integrated view of all data. In this paper, we report the progress of our BISCUITS (Bidirectional Information Systems for Collaborative, Updatable, Interoperable, and Trusted Sharing) project that attempts to systematically solve these two issues in distributed systems. We present a new bidirectional transformation-based approach to control and share distributed data, propose several distributed architectures for data integration via bidirectional updatable views, and demonstrate the applications of these architectures in ride-sharing alliances and gig job sites.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 54.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The project URL is http://www.prg.nii.ac.jp/projects/biscuits/project.html.

  2. 2.

    We write r(a, b) to denote a tuple \(\langle a,b \rangle \) in r.

  3. 3.

    What is called Dejima table in Fig. 3 is expressed in Fig. 5 (Sect. 3.2) by two or more separate copies that belong to each peer.

  4. 4.

    Dejima was the name of a small, artificial island located in Nagasaki, Japan. All the trades between Japan and foreign countries were made through Dejima from the middle of the 17th to the middle of the 19th century. We use this name because the functionality is similar to Dejima.

  5. 5.

    Split composition is a kind of composition patterns named co-sourcial composition explained in Sect. 2.3.

References

  1. Abadi, D., et al.: The Seattle report on database research. ACM SIGMOD Rec. 48(4), 44–53 (2020)

    Article  Google Scholar 

  2. Asano, Y., et al.: Dejima: decentralized transactional data integration with bidirectional update propagation. To be Submitted to an International Conference

    Google Scholar 

  3. Asano, Y., et al.: Flexible framework for data integration and update propagation: system aspect. In: 2019 IEEE International Conference on Big Data and Smart Computing (BigComp), pp. 1–5 (2019)

    Google Scholar 

  4. Bancilhon, F., Spyratos, N.: Update semantics of relational views. ACM Trans. Database Syst. 6(4), 557–575 (1981)

    Article  Google Scholar 

  5. Bárány, V., ten Cate, B., Otto, M.: Queries with guarded negation. PVLDB 5(11), 1328–1339 (2012)

    Google Scholar 

  6. Bohannon, A., Foster, J.N., Pierce, B.C., Pilkiewicz, A., Schmitt, A.: Boomerang: resourceful lenses for string data. In: POPL, pp. 407–419 (2008)

    Google Scholar 

  7. Bohannon, A., Pierce, B.C., Vaughan, J.A.: Relational lenses: a language for updatable views. In: PODS, pp. 338–347 (2006)

    Google Scholar 

  8. Cleve, A., Kindler, E., Stevens, P., Zaytsev, V.: Multidirectional transformations and synchronisations (Dagstuhl seminar 18491). Dagstuhl Rep. 8(12), 1–48 (2019)

    Google Scholar 

  9. Codd, E.F.: Recent investigations in a relational database system. Inf. Process. 74, 1017–1021 (1974)

    Google Scholar 

  10. Czarnecki, K., Foster, J.N., Hu, Z., Lämmel, R., Schürr, A., Terwilliger, J.F.: Bidirectional transformations: a cross-discipline perspective. In: Paige, R.F. (ed.) ICMT 2009. LNCS, vol. 5563, pp. 260–283. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02408-5_19

    Chapter  Google Scholar 

  11. Dampney, C.N.G., Johnson, M.: Half-duplex interoperations for cooperating information systems. In: Advances in Concurrent Engineering, pp. 565–571 (2001)

    Google Scholar 

  12. Dayal, U., Bernstein, P.: On the correct translation of update operations on relational views. ACM Trans. Database Syst. 7, 381–416 (1982)

    Article  MathSciNet  Google Scholar 

  13. Diskin, Z.: Algebraic models for bidirectional model synchronization. In: Czarnecki, K., Ober, I., Bruel, J.-M., Uhl, A., Völter, M. (eds.) MODELS 2008. LNCS, vol. 5301, pp. 21–36. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87875-9_2

    Chapter  Google Scholar 

  14. Diskin, Z.: Update propagation over a network: multi-ary delta lenses, tiles, and categories. Keynote Talk of the 3rd Workshop on Software Foundations for Data Interoperability (SFDI 2019+) (2019)

    Google Scholar 

  15. Diskin, Z., Hidaka, S.: Personal communications, October 2019

    Google Scholar 

  16. Diskin, Z., König, H., Lawford, M.: Multiple model synchronization with multiary delta lenses. In: Russo, A., Schürr, A. (eds.) FASE 2018. LNCS, vol. 10802, pp. 21–37. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89363-1_2

    Chapter  Google Scholar 

  17. Doan, A., Halevy, A.Y., Ives, Z.G.: Principles of Data Integration. Morgan Kaufmann, Waltham (2012)

    Google Scholar 

  18. Dong, G., Su, J.: Incremental maintenance of recursive views using relational calculus/SQL. SIGMOD Rec. 29(1), 44–51 (2000)

    Article  Google Scholar 

  19. Fernandez, E.B., Summers, R.C., Wood, C.: Database Security and Integrity. Addison-Wesley, Reading (1981)

    Google Scholar 

  20. Foster, J.N., Greenwald, M.B., Moore, J.T., Pierce, B.C., Schmitt, A.: Combinators for bidirectional tree transformations: a linguistic approach to the view-update problem. ACM Trans. Program. Lang. Syst. 29(3), 17 (2007)

    Article  Google Scholar 

  21. Foster, J.N., Pierce, B.C., Zdancewic, S.: Updatable security views. In: CSF, pp. 60–74 (2009)

    Google Scholar 

  22. Golshan, B., Halevy, A., Mihaila, G., Tan, W.-C.: Data integration: after the teenage years. In: PODS, pp. 101–106 (2017)

    Google Scholar 

  23. Gupta, A., Mumick, I.S., Subrahmanian, V.S.: Maintaining views incrementally. In: SIGMOD, pp. 157–166 (1993)

    Google Scholar 

  24. Habu, M., Hidaka, S.: Conflict resolution for data updates by multiple bidirectional transformations. In: Proceedings of the Fifth Workshop on Software Foundations for Data Interoperability (SFDI 2021), August 2021. (to appear)

    Google Scholar 

  25. Halevy, A.Y.: Answering queries using views: a survey. VLDB J. 10(4), 270–294 (2001). https://doi.org/10.1007/s007780100054

    Article  MATH  Google Scholar 

  26. Halevy, A.Y., Ives, Z.G., Madhavan, J., Mork, P., Suciu, D., Tatarinov, I.: The Piazza peer data management system. IEEE Trans. Knowl. Data Eng. 16(7), 787–798 (2004)

    Article  Google Scholar 

  27. Halevy, A.Y., Ives, Z.G., Mork, P., Tatarinov, I.: Piazza: data management infrastructure for Semantic Web applications. In: WWW, pp. 556–567 (2003)

    Google Scholar 

  28. Herrmann, K., Voigt, H., Behrend, A., Rausch, J., Lehner, W.: Living in parallel realities: co-existing schema versions with a bidirectional database evolution language. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1101–1116 (2017)

    Google Scholar 

  29. Herrmann, K., Voigt, H., Pedersen, T., Lehner, W.: Multi-schema-version data management: data independence in the twenty-first century. VLDB J. 27(4), 547–571 (2018). https://doi.org/10.1007/s00778-018-0508-7

    Article  Google Scholar 

  30. Hidaka, S., Hu, Z., Inaba, K., Kato, H., Matsuda, K., Nakano, K.: Bidirectionalizing graph transformations. In: ICFP, pp. 205–216 (2010)

    Google Scholar 

  31. Hofmann, M., Pierce, B.C., Wagner, D.: Symmetric lenses. In: POPL, pp. 371–384 (2011)

    Google Scholar 

  32. Hu, Z., Mu, S.-C., Takeichi, M.: A programmable editor for developing structured documents based on bidirectional transformations. Higher-Order Symb. Comput. 21(1–2), 89–118 (2008). https://doi.org/10.1007/s10990-008-9025-5

    Article  MATH  Google Scholar 

  33. Ishihara, Y., Kato, H., Nakano, K., Onizuka, M., Sasaki, Y.: Toward BX-based architecture for controlling and sharing distributed data. In: 2019 IEEE International Conference on Big Data and Smart Computing (BigComp), pp. 1–5 (2019)

    Google Scholar 

  34. Ives, Z., Khandelwal, N., Kapur, A., Cakir, M.: ORCHESTRA: rapid, collaborative sharing of dynamic data. In: CIDR, pp. 107–118 (2005)

    Google Scholar 

  35. Johnson, M., Rosebrugh, R.D.: Spans of lenses. In: Candan, K.S., Amer-Yahia, S., Schweikardt, N., Christophides, V., Leroy, V. (eds.) CEUR@EDBT/ICDT, pp. 112–118 (2014)

    Google Scholar 

  36. Johnson, M., Rosebrugh, R.D.: Cospans and symmetric lenses. In: Marr, S., Sartor, J.B. (eds.) Conference Companion of the 2nd International Conference on Art, Science, and Engineering of Programming, pp. 21–29 (2018)

    Google Scholar 

  37. Karvounarakis, G., Green, T.J., Ives, Z.G., Tannen, V.: Collaborative data sharing via update exchange and provenance. ACM Trans. Database Syst. 38(3), 19:1–19:42 (2013)

    Google Scholar 

  38. Keller, A.: Choosing a view update translator by dialog at view definition time. In: VLDB, pp. 467–474 (1986)

    Google Scholar 

  39. Kementsietsidis, A., Arenas, M., Miller, R.J.: Mapping data in peer-to-peer systems: semantics and algorithmic issues. In: SIGMOD, pp. 325–336 (2003)

    Google Scholar 

  40. Litt, G., van Hardenberg, P., Henry, O.: Cambria: schema evolution in distributed systems with edit lenses. In: Proceedings of the 8th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC 2021), pp. 1–9. ACM Digital Library (2021). Article no. 8

    Google Scholar 

  41. Meertens, L.: Designing constraint maintainers for user interaction (1998). http://www.kestrel.edu/home/people/meertens

  42. Nakano, K.: Involutory turing machines. In: Lanese, I., Rawski, M. (eds.) RC 2020. LNCS, vol. 12227, pp. 54–70. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-52482-1_3

    Chapter  Google Scholar 

  43. Nakano, K.: Idempotent turing machines. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, Volume 202 of LIPIcs, Tallinn, Estonia, 23–27 August 2021, pp. 79:1–79:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

    Google Scholar 

  44. Nakano, K.: A tangled web of 12 Lens laws. In: Yamashita, S., Yokoyama, T. (eds.) RC 2021. LNCS, vol. 12805, pp. 185–203. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79837-6_11

    Chapter  Google Scholar 

  45. Ng, W.S., Ooi, B.C., Tan, K.-L., Zhou, A.: PeerDB: a P2P-based system for distributed data sharing. In: ICDE, pp. 633–644 (2003)

    Google Scholar 

  46. Onizuka, M., Ishihara, Y., Takeichi, M.: Towards smart data sharing by updatable views. In: Qin, L., et al. (eds.) SFDI/LSGDA -2020. CCIS, vol. 1281, pp. 165–171. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-61133-0_13

    Chapter  Google Scholar 

  47. Pierce, B.C., Schmitt, A.: Lenses and view update translation. Working draft, University of Pennsylvania (2003)

    Google Scholar 

  48. Ramakrishnan, R., Gehrke, J.: Database Management Systems, 2nd edn. McGraw-Hill Inc., New York (1999)

    MATH  Google Scholar 

  49. Shapiro, M., Preguiça, N., Baquero, C., Zawirski, M.: Conflict-free replicated data types. In: Défago, X., Petit, F., Villain, V. (eds.) SSS 2011. LNCS, vol. 6976, pp. 386–400. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24550-3_29

    Chapter  MATH  Google Scholar 

  50. Sinchuk, S., Chuprikov, P., Solomatov, K.: Verified operational transformation for trees. In: Blanchette, J.C., Merz, S. (eds.) ITP 2016. LNCS, vol. 9807, pp. 358–373. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43144-4_22

    Chapter  Google Scholar 

  51. Song, H., et al.: Supporting runtime software architecture: a bidirectional-transformation-based approach. J. Syst. Softw. 84(5), 711–723 (2011)

    Article  Google Scholar 

  52. Stevens, P.: Bidirectional transformations in the large. In: MODELS, pp. 1–11 (2017)

    Google Scholar 

  53. Takeichi, M.: Configuring bidirectional programs with functions. In: Draft Proceedings of the 21st International Symposium on Implementation and Application of Functional Languages, pp. 224–239 (2009)

    Google Scholar 

  54. Takeichi, M.: BCDS agent: an architecture for bidirectional collaborative data sharing. In: Computer Software, vol. 38, no. 3, pp. 41–57. Japan Society for Software Science and Technology (2021). https://www.jstage.jst.go.jp/article/jssst/38/3/38_3_41/_pdf/-char/ja

  55. Tanaka, J., Tran, V.-D., Hu, Z.: Toward programmable strategy for co-existence of relational schemes. In: Qin, L., et al. (eds.) SFDI/LSGDA-2020. CCIS, vol. 1281, pp. 138–151. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-61133-0_11

    Chapter  Google Scholar 

  56. Tanaka, J., Tran, V.-D., Kato, H., Hu, Z.: Toward co-existing database schemas based on bidirectional transformation. In: Proceedings of the 3rd Workshop on Software Foundations for Data Interoperability (SFDI 2019+) (2019)

    Google Scholar 

  57. Tatarinov, I., Viglas, S., Beyer, K.S., Shanmugasundaram, J., Shekita, E.J., Zhang, C.: Storing and querying ordered XML using a relational database system. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, USA, 3–6 June 2002, pp. 204–215 (2002)

    Google Scholar 

  58. Tom, M.: A visual guide to the twisted web created by the Uber/Didi merger (2016). https://pitchbook.com/news/articles/a-visual-guide-to-the-twisted-web-created-by-the-uberdidi-merger

  59. Tran, V.-D., Kato, H., Hu, Z.: BIRDS: programming view update strategies in datalog. PVLDB 13(12), 2897–2900 (2020)

    Google Scholar 

  60. Tran, V.-D., Kato, H., Hu, Z.: A counterexample-guided debugger for non-recursive datalog. In: Oliveira, B.C.S. (ed.) APLAS 2020. LNCS, vol. 12470, pp. 323–342. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64437-6_17

    Chapter  Google Scholar 

  61. Tran, V.-D., Kato, H., Hu, Z.: Programmable view update strategies on relations. PVLDB 13(5), 726–739 (2020)

    Google Scholar 

  62. Tran, V.-D., Kato, H., Hu, Z.: Toward recursive view update strategies on relations. In: Ninth International Workshop on Bidirectional Transformations (BX 2021), June 2021

    Google Scholar 

  63. Ullman, J.D.: Information integration using logical views. In: Afrati, F., Kolaitis, P. (eds.) ICDT 1997. LNCS, vol. 1186, pp. 19–40. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62222-5_34

    Chapter  Google Scholar 

Download references

Acknowledgments

This work was partly supported by JSPS KAKENHI Grant Numbers 17H06099, 18H04093, 19H04088. We also thank Dr. Zinovy Diskin (McMaster University) for discussing bipartite graph representation and expressiveness of the Dejima architecture.

Author information

Authors and Affiliations

  1. Toyo University, Tokyo, Japan

    Yasuhito Asano

  2. Kyoto University, Kyoto, Japan

    Yang Cao & Masatoshi Yoshikawa

  3. Hosei University, Tokyo, Japan

    Soichiro Hidaka

  4. Peking University, Beijing, China

    Zhenjiang Hu

  5. Nanzan University, Nagoya, Japan

    Yasunori Ishihara

  6. National Institute of Informatics, Tokyo, Japan

    Zhenjiang Hu & Hiroyuki Kato

  7. Tohoku University, Sendai, Japan

    Keisuke Nakano

  8. Osaka University, Suita, Japan

    Makoto Onizuka, Yuya Sasaki & Chuan Xiao

  9. Kyushu University, Fukuoka, Japan

    Toshiyuki Shimizu

  10. University of Tokyo, Tokyo, Japan

    Masato Takeichi

Authors
  1. Yasuhito Asano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yang Cao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Soichiro Hidaka
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhenjiang Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yasunori Ishihara
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Hiroyuki Kato
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Keisuke Nakano
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Makoto Onizuka
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Yuya Sasaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  10. Toshiyuki Shimizu
    View author publications

    You can also search for this author in PubMed Google Scholar

  11. Masato Takeichi
    View author publications

    You can also search for this author in PubMed Google Scholar

  12. Chuan Xiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  13. Masatoshi Yoshikawa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yang Cao .

Editor information

Editors and Affiliations

  1. Eindhoven University of Technology, Eindhoven, The Netherlands

    George Fletcher

  2. Tohoku University, Sendai, Japan

    Keisuke Nakano

  3. Osaka University, Osaka, Japan

    Yuya Sasaki

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Asano, Y. et al. (2022). Bidirectional Collaborative Frameworks for Decentralized Data Management. In: Fletcher, G., Nakano, K., Sasaki, Y. (eds) Software Foundations for Data Interoperability. SFDI 2021. Communications in Computer and Information Science, vol 1457. Springer, Cham. https://doi.org/10.1007/978-3-030-93849-9_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-93849-9_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-93848-2

  • Online ISBN: 978-3-030-93849-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation