Object Graph Programming
Authors: 
Aditya Thimmaiah, Leonidas Lampropoulos, Christopher Rossbach, Milos GligoricAuthors Info & Claims
Article No.: 20, Pages 1 - 13
Abstract
We introduce Object Graph Programming (OGO), which enables reading and modifying an object graph (i.e., the entire state of the object heap) via declarative queries. OGO models the objects and their relations in the heap as an object graph thereby treating the heap as a graph database: each node in the graph is an object (e.g., an instance of a class or an instance of a metadata class) and each edge is a relation between objects (e.g., a field of one object references another object). We leverage Cypher, the most popular query language for graph databases, as OGO's query language. Unlike LINQ, which uses collections (e.g., List) as a source of data, OGO views the entire object graph as a single "collection". OGO is ideal for querying collections (just like LINQ), introspecting the runtime system state (e.g., finding all instances of a given class or accessing fields via reflection), and writing assertions that have access to the entire program state. We prototyped OGO for Java in two ways: (a) by translating an object graph into a Neo4j database on which we run Cypher queries, and (b) by implementing our own in-memory graph query engine that directly queries the object heap. We used OGO to rewrite hundreds of statements in large open-source projects into OGO queries. We report our experience and performance of our prototypes.
References
[1]
Atul Adya, José A. Blakeley, Sergey Melnik, and S. Muralidhar. 2007. Anatomy of the ADO.NET Entity Framework. In SIGMOD. 877--888.
[2]
Bilal Alsallakh, Peter Bodesinsky, Alexander Gruber, and Silvia Miksch. 2012. Visual Tracing for the Eclipse Java Debugger. In CSMR. 545--548.
[3]
Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan Reutter, and Domagoj Vrgoč. 2017. Foundations of Modern Query Languages for Graph Databases. CSUR (2017).
[4]
Renzo Angles and Claudio Gutierrez. 2008. Survey of Graph Database Models. CSUR (2008).
[5]
ANTLR. 2022. ANTLR Product Website. Accessed November 10, 2022 from https://www.antlr.org.
[6]
François Banciihon. 1988. Object-Oriented Database Systems. In PODS. 152--162.
[7]
Earl T. Barr and Mark Marron. 2014. Tardis: Affordable Time-Travel Debugging in Managed Runtimes. In OOPSLA. 67--82.
[8]
Earl T. Barr, Mark Marron, Ed Maurer, Dan Moseley, and Gaurav Seth. 2016. Time-Travel Debugging for JavaScript/Node.js. In FSE. 1003--1007.
[9]
Edmon Begoli, Tyler Akidau, Fabian Hueske, Julian Hyde, Kathryn Knight, and Kenneth Knowles. 2019. One SQL to Rule Them All - an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables. In SIGMOD. 1757--1772.
[10]
Jonathan Bell and Gail Kaiser. 2014. Unit Test Virtualization with VMVM. In ICSE. 550--561.
[11]
José A. Blakeley, David Campbell, S. Muralidhar, and Anil Nori. 2006. The ADO.NET Entity Framework: Making the Conceptual Level Real. SIGMOD Rec. (2006), 32--39.
[12]
Mathias Braux and Jacques Noyé. 1999. Towards Partially Evaluating Reflection in Java. In PEPM. 2--11.
[13]
Martin Bravenboer and Yannis Smaragdakis. 2009. Strictly Declarative Specification of Sophisticated Points-to Analyses. In OOPSLA. 243--262.
[14]
Fabian Breg and Constantine D. Polychronopoulos. 2001. Java Virtual Machine Support for Object Serialization. In JGI. 173--180.
[15]
Marta Burzańska, Krzysztof Stencel, Patrycja Suchomska, Aneta Szumowska, and Piotr Wiśniewski. 2010. Recursive Queries Using Object Relational Mapping. In Future Generation Information Technology. 42--50.
[16]
Andrea Calì, Georg Gottlob, Thomas Lukasiewicz, Bruno Marnette, and Andreas Pieris. 2010. Datalog+/-: A Family of Logical Knowledge Representation and Query Languages for New Applications. In LICS. 228--242.
[17]
Michael J. Carey, David J. DeWitt, Chander Kant, and Jeffrey F. Naughton. 1994. A Status Report on the OO7 OODBMS Benchmarking Effort. In OOPSLA. 414--426.
[18]
Pablo Castro, Sergey Melnik, and Atul Adya. 2007. ADO.NET Entity Framework: Raising the Level of Abstraction in Data Programming. In SIGMOD. 1070--1072.
[19]
S. Ceri, G. Gottlob, and L. Tanca. 1989. What you always wanted to know about Datalog (and never dared to ask). Transactions on Knowledge and Data Engineering (1989), 146--166.
[20]
Surajit Chaudhuri, Vivek Narasayya, and Manoj Syamala. 2007. Bridging the Application and DBMS Profiling Divide for Database Application Developers. In VLDB. 1252--1262.
[21]
Yangjun Chen and Gagandeep Singh. 2021. Graph Indexing for Efficient Evaluation of Label-Constrained Reachability Queries. TODS (2021).
[22]
James Cheney, Sam Lindley, and Philip Wadler. 2013. A Practical Theory of Language-Integrated Query. In ICFP. 403--416.
[23]
Alvin Cheung, Armando Solar-Lezama, and Samuel Madden. 2013. Optimizing Database-Backed Applications with Query Synthesis. In PLDI. 3--14.
[24]
Mariano Consens and Alberto Mendelzon. 1993. Hy+: A Hygraph-Based Query and Visualization System. In SIGMOD. 511--516.
[25]
World Wide Web Consortium. 2013. SPARQL Protocol and RDF Query Language. https://www.w3.org/TR/sparql11-query/
[26]
William R. Cook and Ali H. Ibrahim. 2005. Integrating programming languages and databases: What is the problem. In Expert Article.
[27]
George Copeland and David Maier. 1984. Making Smalltalk a Database System. In SIGMOD. 316--325.
[28]
C. J. Date. 1984. A Critique of the SQL Database Language. SIGMOD Rec. (1984), 8--54.
[29]
Andrew Eisenberg and Jim Melton. 1998. SQLJ Part 0, Now Known as SQL/OLB (Object-Language Bindings). (1998), 94--100.
[30]
Andrew Eisenberg and Jim Melton. 1999. SQLJ Part 1: SQL Routines Using the Java Programming Language. (1999), 58--63.
[31]
Wenfei Fan, Jianzhong Li, Xin Wang, and Yinghui Wu. 2012. Query Preserving Graph Compression. In SIGMOD. 157--168.
[32]
Tomás Feder and Rajeev Motwani. 1991. Clique Partitions, Graph Compression and Speeding-up Algorithms. In STOC. 123--133.
[33]
The GraphQL Foundation. 2021. GraphQL Specification. https://spec.graphql.org/October2021/
[34]
Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Martin Schuster, Petra Selmer, and Andrés Taylor. 2018. Formal Semantics of the Language Cypher. arXiv e-prints (2018), arXiv:1802.09984.
[35]
Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An Evolving Query Language for Property Graphs. In SIGMOD. 1433--1445.
[36]
GNU. [n.d.]. DDD - DataDisplay Debugger. Accessed November 10, 2022 from https://www.gnu.org/software/ddd.
[37]
Alastair Green, Martin Junghanns, Max Kießling, Tobias Lindaaker, Stefan Plantikow, and Petra Selmer. 2018. openCypher: New Directions in Property Graph Querying. In EDBT. 520--523.
[38]
Zhongxian Gu, Drew Schleck, Earl T. Barr, and Zhendong Su. 2014. Capturing and Exploiting IDE Interactions. In International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software. 83--94.
[39]
Marc Gyssens, Jan Paredaens, and Dirk van Gucht. 1990. A Graph-Oriented Object Database Model. In PODS. 417--424.
[40]
Graham Hamilton, Rick Cattell, and Maydene Fisher. 1997. Jdbc Database Access with Java: A Tutorial and Annotated Reference (1st ed.). Addison-Wesley Longman Publishing Co., Inc.
[41]
Matthew Harren, Mukund Raghavachari, Oded Shmueli, Michael G. Burke, Rajesh Bordawekar, Igor Pechtchanski, and Vivek Sarkar. 2005. XJ: Facilitating XML Processing in Java. In WWW. 278--287.
[42]
Matthew Harren, Mukund Raghavachari, Oded Shmueli, Michael G. Burke, Vivek Sarkar, and Rajesh Bordawekar. 2004. XJ: Integration of XML Processing into Java. In WWW Alt. 340--341.
[43]
Jelle Hellings, George H.L. Fletcher, and Herman Haverkort. 2012. Efficient External-Memory Bisimulation on DAGs. In SIGMOD. 553--564.
[44]
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia D'amato, Gerard De Melo, Claudio Gutierrez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel-Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann. 2021. Knowledge Graphs. CSUR (2021).
[45]
Florian Holzschuher and René Peinl. 2013. Performance of Graph Query Languages: Comparison of Cypher, Gremlin and Native Access in Neo4j. In EDBT. 195--204.
[46]
Florian Holzschuher and René Peinl. 2016. Querying a graph database - language selection and performance considerations. J. Comput. System Sci. 82 (2016), 45--68.
[47]
Shiyou Huang, Jianmei Guo, Sanhong Li, Xiang Li, Yumin Qi, Kingsum Chow, and Jeff Huang. 2019. SafeCheck: Safety Enhancement of Java Unsafe API. In ICSE. 889--899.
[48]
Shan Shan Huang, Todd Jeffrey Green, and Boon Thau Loo. 2011. Datalog and Emerging Applications: An Interactive Tutorial. In SIGMOD. 1213--1216.
[49]
Atshushi Igarashi, Benjamin Pierce, and Philip Wadler. 1999. Featherweight Java: A Minimal Core Calculus for Java and GJ. In OOPSLA. 132--146.
[50]
Salim Jouili and Valentin Vansteenberghe. 2013. An Empirical Comparison of Graph Databases. In SocialCom. 708--715.
[51]
Arthur M. Keller. 1986. Unifying Database and Programming Language Concepts Using the Object Model. In OODS. 221--222.
[52]
Yit Phang Khoo, Jeffrey S. Foster, and Michael Hicks. 2013. Expositor: Scriptable Time-Travel Debugging with First-Class Traces. In ICSE. 352--361.
[53]
Michael Kifer and Yanhong Annie Liu (Eds.). 2018. Declarative Logic Programming: Theory, Systems, and Applications. Vol. 20. Association for Computing Machinery and Morgan & Claypool.
[54]
Oleg Kiselyov and Tatsuya Katsushima. 2017. Sound and Efficient Language-Integrated Query. In Programming Languages and Systems. 364--383.
[55]
Phokion G. Kolaitis and Moshe Y. Vardi. 1990. On the Expressive Power of Datalog: Tools and a Case Study. In PODS. 61--71.
[56]
Mikael Kopteff. 2008. The Usasge and Performance of Object Databases Compared with ORM Tools in a Java Environment. In ICOODB.
[57]
Tomasz Marek Kowalski and Radosław Adamus. 2017. Optimisation of language-integrated queries by query unnesting. Computer Languages, Systems and Structures (2017), 131--150.
[58]
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tompkins, and Eli Upfal. 2000. The Web as a Graph. In PODS. 1--10.
[59]
Ramon Lawrence, Erik Brandsberg, and Roland Lee. 2017. Next Generation JDBC Database Drivers for Performance, Transparent Caching, Load Balancing, and Scale-Out. In SAC. 915--918.
[60]
Patrick Connor Linskey and Marc Prud'hommeaux. 2007. An In-Depth Look at the Architecture of an Object/Relational Mapper. In SIGMOD. 889--894.
[61]
J. López-González and Juan M. Serrano. 2020. The optics of language-integrated query. Science of Computer Programming (2020).
[62]
David Maier. 1990. Representing Database Programs as Objects. 377--386.
[63]
David Maier, Jacob Stein, Allen Otis, and Alan Purdy. 1986. Development of an Object-Oriented DBMS. (1986), 472--482.
[64]
Sofia Maiolo, Lorena Etcheverry, and Adriana Marotta. 2020. Data Profiling in Property Graph Databases. JDIQ (2020).
[65]
Luis Mastrangelo, Luca Ponzanelli, Andrea Mocci, Michele Lanza, Matthias Hauswirth, and Nathaniel Nystrom. 2015. Use at Your Own Risk: The Java Unsafe API in the Wild. In OOPSLA. 695--710.
[66]
Evan K. Maxwell, Godmar Back, and Naren Ramakrishnan. 2010. Diagnosing Memory Leaks Using Graph Mining on Heap Dumps. In KDD. 115--124.
[67]
Gerrit Meier and Michael Simons. 2020. The Neo4j Cypher-DSL. https://neo4j-contrib.github.io/cypher-dsl/current/.
[68]
Erik Meijer, Brian Beckman, and Gavin Bierman. 2006. LINQ: Reconciling Object, Relations and XML in the .NET Framework. In SIGMOD. 706.
[69]
Jim Melton. 2006. Database Language SQL. Springser Berlin Heidelberg, 105--132.
[70]
Jan Michels, Keith Hare, Krishna Kulkarni, Calisto Zuzarte, Zhen Hua Liu, Beda Hammerschmidt, and Fred Zemke. 2018. The New and Improved SQL: 2016 Standard. SIGMOD Rec. (2018), 51--60.
[71]
Aleksandar Milicevic, Derek Rayside, Kuat Yessenov, and Daniel Jackson. 2011. Unifying Execution of Imperative and Declarative Code. In ICSE. 511--520.
[72]
Fabian Nagel, Gavin Bierman, and Stratis D. Viglas. 2014. Code Generation for Efficient Query Processing in Managed Runtimes. Proceedings of the VLDB Endowment (2014), 1095--1106.
[73]
Inc. 2022. Neo4j. 2022. Neo4j Product Website. Accessed November 10, 2022 from https://neo4j.com/.
[74]
Pengyu Nie, Marinela Parovic, Zhiqiang Zang, Sarfraz Khurshid, Aleksandar Milicevic, and Milos Gligoric. 2020. Unifying Execution of Imperative Generators and Declarative Specifications. (2020).
[75]
Anders Norås. 2011. Quaere. Accessed November 10, 2022 from https://github.com/anoras/Quaere.
[76]
Rainer Oechsle and Thomas Schmitt. 2002. JAVAVIS: Automatic Program Visualization with Object and Sequence Diagrams Using the Java Debug Interface (JDI). In Software Visualization. Springer Berlin Heidelberg, 176--190.
[77]
Atsushi Ohori and Katsuhiro Ueno. 2011. Making Standard ML a Practical Database Programming Language. In ICFP. 307--319.
[78]
Rui Okura and Yukiyoshi Kameyama. 2020. Reorganizing Queries with Grouping. In GPCE. 50--62.
[79]
Elizabeth J. O'Neil. 2008. Object/Relational Mapping 2008: Hibernate and the Entity Data Model (Edm). In SIGMOD. 1351--1356.
[80]
Oracle. 2022. Java Object Serialization Specification. Accessed November 10, 2022 from https://docs.oracle.com/en/java/javase/17/docs/specs/serialization/index.html.
[81]
Oracle. 2022. Java Virtual Machine Tool Interface (JVM TI). Accessed November 10, 2022 from https://docs.oracle.com/en/java/javase/11/docs/specs/jvmti.html.
[82]
Oracle. 2022. jdb - The Java Debugger. Accessed November 10, 2022 from https://docs.oracle.com/javase/7/docs/technotes/tools/windows/jdb.html.
[83]
Oracle. 2022. Method Detail: hashCode. Accessed November 10, 2022 from https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Object.html#hashCode().
[84]
Oracle. 2022. Method Detail: identityHashCode. Accessed November 10, 2022 from https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/System.html#identityHashCode(java.lang.Object).
[85]
Oracle. 2022. Package java.sql Description. Accessed November 10, 2022 from https://docs.oracle.com/javase/8/docs/api/java/sql/package-summary.html#package.description.
[86]
Oracle. 2022. Unsafe Class. Accessed November 10, 2022 from https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/sun/misc/Unsafe.java.
[87]
T. J. Parr and R. W. Quong. 1995. ANTLR: A predicated-LL(k) parser generator. Software: Practice and Experience (1995), 789--810.
[88]
Owain Parry, Gregory M. Kapfhammer, Michael Hilton, and Phil McMinn. 2021. A Survey of Flaky Tests. ACM Trans. Softw. Eng. Methodol. (2021).
[89]
Michael Philippsen and Bernhard Haumacher. 1999. More efficient object serialization. In Parallel and Distributed Processing. Springer Berlin Heidelberg, 718--732.
[90]
Michael Philippsen, Bernhard Haumacher, and Christian Nester. 2000. More efficient serialization and RMI for Java. Concurrency: Practice and Experience (2000), 495--518.
[91]
Jaroslav Pokorný. 2015. Graph Databases: Their Power and Limitations. In Computer Information Systems and Industrial Management. 58--69.
[92]
Jaroslav Pokorný. 2016. Conceptual and Database Modelling of Graph Databases. In IDEAS. 370--377.
[93]
Alex Potanin. 2002. A Tool for Ownership and Confinement Analysis of the Java Object Graph. In OOPSLA. 118--119.
[94]
Wilmer Ricciotti and James Cheney. 2021. Query Lifting. In Programming Languages and Systems. 579--606.
[95]
Marko A. Rodriguez. 2015. The Gremlin Graph Traversal Machine and Language (Invited Talk). In Symposium on Database Programming Languages. Association for Computing Machinery, New York, NY, USA, 1--10.
[96]
Guido Salvaneschi, Mirko Köhler, Daniel Sokolowski, Philipp Haller, Sebastian Erdweg, and Mira Mezini. 2019. Language-Integrated Privacy-Aware Distributed Queries. Proc. ACM Program. Lang. (2019).
[97]
Wolfgang Schuetzelhofer. [n. d.]. JCypher. Accessed September 19, 2023 from https://github.com/Wolfgang-Schuetzelhofer/jcypher.
[98]
Philipp Seifer, Johannes Härtel, Martin Leinberger, Ralf Lämmel, and Steffen Staab. 2019. Empirical Study on the Usage of Graph Query Languages in Open Source Java Projects. 152--166.
[99]
Yannis Smaragdakis and Martin Bravenboer. 2011. Using Datalog for Fast and Easy Program Analysis. In Datalog Reloaded. 245--251.
[100]
Disha Soni, Thanaa Ghanem, Basma Gomaa, and Jon Schommer. 2019. Leveraging Twitter and Neo4j to Study the Public Use of Opioids in the USA. In GRADES-NDA.
[101]
David D. Straube and M. Tamer Özsu. 1990. Queries and Query Processing in Object-Oriented Database Systems. ACM Transactions on Information Systems (1990), 387--430.
[102]
Kenichi Suzuki, Oleg Kiselyov, and Yukiyoshi Kameyama. 2016. Finally, Safely-Extensible and Efficient Language-Integrated Query. In PEPM. 37--48.
[103]
Alexandre Torres, Renata Galante, Marcelo S. Pimenta, and Alexandre Jonatan B. Martins. 2017. Twenty years of object-relational mapping: A survey on patterns, solutions, and their implications on application design. Information and Software Technology (2017), 1--18.
[104]
Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi. 2016. PGQL: A Property Graph Query Language. In International Workshop on Graph Data Management Experiences and Systems (GRADES '16). Association for Computing Machinery, New York, NY, USA, 6 pages.
[105]
Sebastiaan J. van Schaik and Oege de Moor. 2011. A Memory Efficient Reachability Data Structure through Bit Vector Compression. In SIGMOD. 913--924.
[106]
Jeffrey Scott Vitter. 2001. External Memory Algorithms and Data Structures: Dealing with Massive Data. CSUR (2001), 209--271.
[107]
Emil Wcislo, Piotr Habela, and Kazimierz Subieta. 2011. A Java-Integrated Object Oriented Query Language. In Informatics Engineering and Information Science. 589--603.
[108]
Anjiang Wei, Pu Yi, Tao Xie, Darko Marinov, and Wing Lam. 2021. Probabilistic and Systematic Coverage of Consecutive Test-Method Pairs for Detecting Order-Dependent Flaky Tests. TACAS (2021), 270--287.
[109]
Markus Weninger, Elias Gander, and Hanspeter Mössenböck. 2019. Analyzing Data Structure Growth Over Time to Facilitate Memory Leak Detection. In ICPE. 273--284.
[110]
Markus Weninger, Lukas Makor, Elias Gander, and Hanspeter Mössenböck. 2019. AntTracks TrendViz: Configurable Heap Memory Visualization Over Time. In ICPE. 29--32.
[111]
Mingxi Wu and Alin Deutsch. 2019. GSQL: An SQL-Inspired Graph Query Language. https://info.tigergraph.com/gsql
[112]
Xifeng Yan, Philip S. Yu, and Jiawei Han. 2005. Graph Indexing Based on Discriminative Frequent Structure Analysis. TODS (2005), 960--993.
Recommendations
Efficient algorithms for supergraph query processing on graph databases
We study the problem of processing supergraph queries on graph databases. A graph database D is a large set of graphs. A supergraph query q on D is to retrieve all the graphs in D such that q is a supergraph of them. The large ...
TED: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database
PACMMODWith an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (e.g., chemical compounds). Although subgraph ...
Improving Semantic Queries by Utilizing UNL Ontology and a Graph Database
ICSC '12: Proceedings of the 2012 IEEE Sixth International Conference on Semantic ComputingThis paper describes an approach for improving semantic queries by utilizing Universal Words (UWs) and a graph database. Concept Description Language (CDL) is used for representing the semantic data, and Neo4j graph database is used as the storage back-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2024
2942 pages
ISBN:9798400702174
DOI:10.1145/3597503
- Co-chairs:
- Ana Paiva,
- Rui Abreu,
- Program Co-chairs:
- Abhik Roychoudhury,
- Margaret Storey
Copyright © 2024 Owner/Author(s).
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
In-Cooperation
- Faculty of Engineering of University of Porto
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 06 February 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- US National Science Fund
Conference
ICSE '24
Sponsor:
ICSE '24: IEEE/ACM 46th International Conference on Software Engineering
April 14 - 20, 2024
Lisbon, Portugal
Acceptance Rates
Overall Acceptance Rate 276 of 1,856 submissions, 15%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 428Total Downloads
- Downloads (Last 12 months)428
- Downloads (Last 6 weeks)50
Reflects downloads up to 21 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in