skip to main content
research-article

Static and dynamic semantics of NoSQL languages

Published: 23 January 2013 Publication History

Abstract

We present a calculus for processing semistructured data that spans differences of application area among several novel query languages, broadly categorized as "NoSQL". This calculus lets users define their own operators, capturing a wider range of data processing capabilities, whilst providing a typing precision so far typical only of primitive hard-coded operators. The type inference algorithm is based on semantic type checking, resulting in type information that is both precise, and flexible enough to handle structured and semistructured data. We illustrate the use of this calculus by encoding a large fragment of Jaql, including operations and iterators over JSON, embedded SQL expressions, and co-grouping, and show how the encoding directly yields a typing discipline for Jaql as it is, namely without the addition of any type definition or type annotation in the code.

Supplementary Material

JPG File (r1d1_talk9.jpg)
MP4 File (r1d1_talk9.mp4)

References

[1]
A. Albano, G. Ghelli, and R. Orsini. Fibonacci: A programming language for object databases. The VLDB Journal, 4:403--444, 1995.
[2]
N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. XML with data values: typechecking revisited. In PODS\,'01. ACM, 2001.
[3]
N. Alon, T. Milo, F. Neven, D. Suciu, and V. Vianu. Typechecking XML views of relational databases. ACM Trans. Comput. Logic, 4:315--354, July 2003.
[4]
A. Behm phet al. Asterix: towards a scalable, semistructured data platform for evolving-world models. DAPD, 29(3):185--216, 2011.
[5]
V. Benzaken, G. Castagna, and A. Frisch. CDuce: an XML-friendly general purpose language. In ICFP\,'03. ACM, 2003.
[6]
K. Beyer phet al. Jaql: A scripting language for large scale semistructured data analysis. PVLDB, 4(12):1272--1283, 2011.
[7]
S. Boag, D. Chamberlain, M. F. Fernández, D. Florescu, J. Robie, and J. Siméon. XQuery 1.0: An XML query language, W3C rec., 2007.
[8]
P. Buneman, L. Libkin, D. Suciu, V. Tannen, and L. Wong. Comprehension syntax. SIGMOD Record, 23(1):87--96, 1994.
[9]
P. Buneman, R. Nikhil, and R. Frankel. A Practical Functional Programming System for Databases. In Proc. Conference on Functional Programming and Architecture. ACM, 1981.
[10]
G. Castagna and K. Nguyen. Typed iterators for XML. In ICFP'08. ACM, 2008.
[11]
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, C. Löding, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. http://www.grappa.univ-lille3.fr/tata, 2007.
[12]
G. Copeland and D. Maier. Making Smalltalk a database system. In ACM SIGMOD Conf., 1984.
[13]
J. Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory, 10(1):289--303, Dec. 1976.
[14]
A. Frisch. Théorie, conception et réalisation d'un langage de programmation adapté à XML. PhD thesis, Université Paris 7 Denis Diderot, 2004.
[15]
A. Frisch, G. Castagna, and V. Benzaken. Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types. Journal of the ACM, 55(4):1--64, 2008.
[16]
Jaql.texttthttp://code.google.com/p/jaql.
[17]
JavaScript Object Notation (JSON).texttthttp://json.org/.
[18]
W. Martens and F. Neven. Typechecking top-down uniform unranked tree transducers. In ICDT\,'03. Springer, 2002.
[19]
E. Meijer. The world according to LINQ. ACM Queue, 9(8):60, 2011.
[20]
E. Meijer and G. Bierman. A co-relational model of data for large shared data banks. Communications of the ACM, 54(4):49--58, 2011.
[21]
K. Nguyen. Language of Combinators for XML: Conception, Typing, Implementation. PhD thesis, Université Paris-Sud 11, 2008.
[22]
Odata.texttthttp://www.odata.org/.
[23]
A. Ohori and P. Buneman. Type Inference in a Database Programming Language. In LISP and Functional Programming, 1988.
[24]
A. Ohori, P. Buneman, and V. Tannen. Database Programming in Machiavelli --a Polymorphic Language with Static Type Inference. In ACM SIGMOD Conf., 1989.
[25]
A. Ohori and K. Ueno. Making standard ML a practical database programming language. In ICFP\,'11, 2011.
[26]
C. Olston, B. Reed, U. Srivastava, R. Kumar, and A. Tomkins. Pig latin: a not-so-foreign language for data processing. In ACM SIGMOD Conf., 2008.
[27]
F. Özcan phet al. Emerging trends in the enterprise data analytics: connecting Hadoop and DB2 warehouse. In ACM SIGMOD Conf., 2011.
[28]
J. Robie (editor). JSONiq. http://jsoniq.org.
[29]
J. Schmidt and M. Mall. Pascal/R Report. Technical Report 66, Fachbereich Informatik, université de Hamburg, 1980.
[30]
Squeryl: A Scala ORM and DSL for talking with Databases with minimum verbosity and maximum type safety.texttthttp://squeryl.org/.
[31]
V. Tannen, P. Buneman, and L. Wong. Naturally embedded query languages. In ICDT, pages 140--154, 1992.
[32]
P. Trinder and P. Wadler. Improving list comprehension database queries. In 4th IEEE Region 10 Conference (TENCON), 1989.
[33]
Unql.texttthttp://www.unqlspec.org/.

Cited By

View all
  • (2023)Making a Type Difference: Subtraction on Intersection Types as Generalized Record OperationsProceedings of the ACM on Programming Languages10.1145/35712247:POPL(893-920)Online publication date: 11-Jan-2023
  • (2021)Verification of Program Transformations with Inductive Refinement TypesACM Transactions on Software Engineering and Methodology10.1145/340980530:1(1-33)Online publication date: 20-Jan-2021
  • (2018)NoSQL Languages and SystemsNoSQL Data Models10.1002/9781119528227.ch1(1-20)Online publication date: 6-Aug-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices
ACM SIGPLAN Notices  Volume 48, Issue 1
POPL '13
January 2013
561 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2480359
Issue’s Table of Contents
  • cover image ACM Conferences
    POPL '13: Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages
    January 2013
    586 pages
    ISBN:9781450318327
    DOI:10.1145/2429069
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 January 2013
Published in SIGPLAN Volume 48, Issue 1

Check for updates

Author Tags

  1. NoSQL
  2. bigdata analytics
  3. cloud computing
  4. jaql
  5. type inference

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Making a Type Difference: Subtraction on Intersection Types as Generalized Record OperationsProceedings of the ACM on Programming Languages10.1145/35712247:POPL(893-920)Online publication date: 11-Jan-2023
  • (2021)Verification of Program Transformations with Inductive Refinement TypesACM Transactions on Software Engineering and Methodology10.1145/340980530:1(1-33)Online publication date: 20-Jan-2021
  • (2018)NoSQL Languages and SystemsNoSQL Data Models10.1002/9781119528227.ch1(1-20)Online publication date: 6-Aug-2018
  • (2016)Cross-system NoSQL data transformations with NotaQLProceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond10.1145/2926534.2926535(1-10)Online publication date: 26-Jun-2016
  • (2016)An Adaptive Load-Balanced Partitioning Module in Cassandra Using Rendezvous HashingProceedings of the International Conference on Advanced Intelligent Systems and Informatics 201610.1007/978-3-319-48308-5_56(587-597)Online publication date: 18-Oct-2016
  • (2015)Logics for Unordered Trees with Data Constraints on SiblingsLanguage and Automata Theory and Applications10.1007/978-3-319-15579-1_13(175-187)Online publication date: 24-Feb-2015
  • (2013)On bridging relational and document-centric data storesProceedings of the 29th British National conference on Big Data10.1007/978-3-642-39467-6_14(135-148)Online publication date: 8-Jul-2013
  • (2020)Verification of high-level transformations with inductive refinement typesACM SIGPLAN Notices10.1145/3393934.327812553:9(147-160)Online publication date: 7-Apr-2020
  • (2019)Logics for unordered trees with data constraintsJournal of Computer and System Sciences10.1016/j.jcss.2018.11.004104:C(149-164)Online publication date: 1-Sep-2019
  • (2018)NoSQL approach for sensor data storage and retrieval2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO)10.23919/MIPRO.2018.8400257(1427-1432)Online publication date: May-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media