zbMATH — the first resource for mathematics

A branding strategy for business types. (English) Zbl 1343.68052
Lindley, Sam (ed.) et al., A list of successes that can change the world. Essays dedicated to Philip Wadler on the occasion of his 60th birthday. Cham: Springer (ISBN 978-3-319-30935-4/pbk; 978-3-319-30936-1/ebook). Lecture Notes in Computer Science 9600, 367-387 (2016).
Summary: In the course of building a compiler from business rules to a database run-time, we encounter the need for a type system that includes a class hierarchy and subtyping in the presence of complex record operations. Since our starting point is based on structural typing and targets a data-centric language, we develop an approach inspired by Wadler’s work on XML types [J. Siméon and P. Wadler, “The essence of XML”, in: Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL 2003. New York, NY: Association for Computing Machinery (ACM). 1–13 (2003; doi:10.1145/604131.604132)]. Our proposed type system has strong similarities with branded or tagged objects, combining nominal and structural typing, and is designed to support a rich set of operations on records commonly found in database languages. We show soundness of the type system and illustrate its use on two of the intermediate languages involved in our compiler for business rules: a calculus for pattern matching with aggregation (CAMP) that captures rules semantics, and the nested relational algebra (NRA) used for optimization and code generation. We show type soundness for both languages. The approach and correctness proofs are fully mechanized using the Coq proof-assistant.
For the entire collection see [Zbl 1333.68014].
68N20 Theory of compilers and interpreters
68P05 Data structures
68P15 Database theory
Full Text: DOI
[1] Alagic, S.: Type-checking OQL queries in the ODMG type systems. ACM Trans. Database Syst. 24(3), 319–360 (1999) · doi:10.1145/328939.328943
[2] Armbrust, M., Xin, R.S., Lian, C., Huai, Y., Liu, D., Bradley, J.K., Meng, X., Kaftan, T., Franklin, M.J., Ghodsi, A., et al.: Spark SQL: relational data processing in Spark. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1383–1394 (2015) · doi:10.1145/2723372.2742797
[3] Arnold, M., Grove, D., Herta, B., Hind, M., Hirzel, M., Iyengar, A., Mandel, L., Saraswat, V.A., Shinnar, A., Siméon, J., Takeuchi, M., Tardieu, O., Zhang, W.: META: middleware for events, transactions, and analytics. IBM J. Res. Devel. (IBMRD). (2016, to appear) · doi:10.1147/JRD.2016.2527419
[4] Bali, M.: Drools JBoss Rules 5.0 Developer’s Guide. Packt Publishing, Birmingham (2009)
[5] Beeri, C., Kornatzky, Y.: Algebraic optimization of object-oriented query languages. Theor. Comput. Sci. 116(1&2), 59–94 (1993) · Zbl 0785.68020 · doi:10.1016/0304-3975(93)90220-N
[6] Berler, M., Cattell, R.G.G., Barry, D.K.: The Object Data Standard: ODMG 3.0. Morgan Kaufmann, San Francisco (2000)
[7] Boyer, J., Mili, H.: IBM websphere ILOG JRules. In: Boyer, J., Mili, H. (eds.) Agile Business Rule Development, pp. 215–242. Springer, Heidelberg (2011) · doi:10.1007/978-3-642-19041-4_8
[8] Cheney, J., Lindley, S., Wadler, P.: A practical theory of language-integrated query. In: International Conference on Functional Programming (ICFP), pp. 403–416 (2013) · Zbl 1323.68102 · doi:10.1145/2500365.2500586
[9] Claußen, J., Kemper, A., Moerkotte, G., Peithner, K.: Optimizing queries with universal quantification in object-oriented and object-relational databases. In: Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB), pp. 286–295 (1997)
[10] Cluet, S., Moerkotte, G.: Nested queries in object bases. In: Workshop on Database Programming Languages (DBPL), pp. 226–242 (1993)
[11] Cooper, E., Lindley, S., Yallop, J.: Links: web programming without tiers. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, W.-P. (eds.) FMCO 2006. LNCS, vol. 4709, pp. 266–296. Springer, Heidelberg (2007) · Zbl 05344440 · doi:10.1007/978-3-540-74792-5_12
[12] Fegaras, L., Maier, D.: Optimizing object queries using an effective calculus. ACM Trans. Database Syst. (TODS) 25(4), 457–516 (2000) · Zbl 1136.68380 · doi:10.1145/377674.377676
[13] Forgy, C.L.: OPS5 user’s manual. Technical report. 2397, CMU (1981)
[14] Green, T.J., Aref, M., Karvounarakis, G.: LogicBlox, platform and language: a tutorial. In: Barceló, P., Pichler, R. (eds.) Datalog 2.0 2012. LNCS, vol. 7494, pp. 1–8. Springer, Heidelberg (2012) · Zbl 06106012 · doi:10.1007/978-3-642-32925-8_1
[15] Grust, T., Mayr, M., Rittinger, J., Schreiber, T.: Ferry: Database-supported program execution. In: International Conference on Management of Data (SIGMOD), pp. 1063–1066 (2009) · doi:10.1145/1559845.1559982
[16] Jones, T., Homer, M., Noble, J.: Brand objects for nominal typing. In: 29th European Conference on Object-Oriented Programming, ECOOP 2015, 5–10 July 2015, Prague, Czech Republic, pp. 198–221 (2015)
[17] Lee, J., Aldrich, J., Shaw, T., Potanin, A.: A theory of tagged objects. In: 29th European Conference on Object-Oriented Programming, ECOOP 2015, 5–10 July 2015, Prague, Czech Republic (2015)
[18] May, N., Helmer, S., Moerkotte, G.: Strategies for query unnesting in XML databases. Trans. Database Syst. (TODS) 31(3), 968–1013 (2006) · doi:10.1145/1166074.1166081
[19] Meijer, E., Beckman, B., Bierman, G.: Linq: reconciling object, relations and XML in the.NET framework. In: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, pp. 706–706 (2006) · doi:10.1145/1142473.1142552
[20] Shinnar, A., Siméon, J., Hirzel, M.: A pattern calculus for rule languages: expressiveness, compilation, and mechanization. In: 29th European Conference on Object-Oriented Programming, ECOOP 2015, 5–10 July 2015, Prague, Czech Republic, pp. 542–567 (2015)
[21] Siméon, J., Wadler, P.: The essence of XML. In: The 30th SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisisana, USA, 15–17 January 2003, pp. 1–13 (2003) · Zbl 06481279 · doi:10.1145/604131.604132
[22] Tannen, V., Buneman, P., Wong, L.: Naturally embedded query languages. In: Hull, R., Biskup, J. (eds.) ICDT 1992. LNCS, vol. 646, pp. 140–154. Springer, Heidelberg (1992) · doi:10.1007/3-540-56039-4_38
[23] Trigoni, A., Bierman, G.: Inferring the principal type and the schema requirements of an OQL query. In: Read, B. (ed.) BNCOD 2001. LNCS, vol. 2097, pp. 185–201. Springer, Heidelberg (2001) · Zbl 0980.68711 · doi:10.1007/3-540-45754-2_12
[24] Trinder, P., Wadler, P.: List comprehensions and the relational calculus. In: Proceedings of 1988 Glasgow Workshop on Functional Programming, Rothesay, Scotland, pp. 115–123, August 1988
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.