More Web Proxy on the site http://driver.im/

research-article

Type inference for datalog and its application to query optimisation

Authors:

Pavel Avgustinov,

Mathieu VerbaereAuthors Info & Claims

PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 291 - 300

https://doi.org/10.1145/1376916.1376957

Published: 09 June 2008 Publication History

Abstract

Certain variants of object-oriented Datalog can be compiled to Datalog with negation. We seek to apply optimisations akin to virtual method resolution (a well-known technique in compiling Java and other OO languages) to improve efficiency of the resulting Datalog programs. The effectiveness of such optimisations strongly depends on the precision of the underlying type inference algorithm. Previous work on type inference for Datalog has focussed on Cartesian abstractions, where the type of each field is computed separately. Such Cartesian type inference is inherently imprecise in the presence of field equalities. We propose a type system where equalities are tracked, and present a type inference algorithm. The algorithm is proved sound. We also prove that it is optimal for Datalog without negation, in the sense that the inferred type is as tight as possible. Extensive experiments with our type-based optimisations, in a commercial implementation of object-oriented Datalog, confirm the benefits of this non-Cartesian type inference algorithm.

References

[1]

Serge Abiteboul and Cassio Souza dos Santos. IQL(2): A model with ubiquitous objects. In Paolo Atzeni and Val Tannen, editors, Database Programming Languages (DBPL-5), Electronic Workshops in Computing. Springer, 1995.

Digital Library

[2]

Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.

Digital Library

[3]

Serge Abiteboul, Georg Lausen, Heinz Uphoff, and Emmanuel Waller. Methods and rules. In ACM SIGMOD International Conference on Management of Data, pages 32--41. ACM Press, 1993.

Digital Library

[4]

Roland Backhouse. Fixed point calculus. In Algebraic and Coalgebraic Methods in Mathematics of Program Construction, volume 2297 of LNCS, pages 89--148. Springer, 2002.

Digital Library

[5]

François Bancilhon, David Maier, Yehoshua Sagiv, and Jeffrey D. Ullman. Magic sets and other strange ways to implement logic programs. In Principles of Database Systems (PODS), pages 1--16. ACM Press, 1986.

Digital Library

[6]

Sacha Berger, Emmanuel Coquery, Wlodzimierz Drabent, and Artur Wilk. Descriptive typing rules for Xcerpt and their soundness. In François Fages and Sylvain Soliman, editors, Principles and Practice of Semantic Web Reasoning, volume 3703 of LNCS, pages 85--100. Springer, 2005.

Digital Library

[7]

Piero A. Bonatti. On the decidability of containment of recursive Datalog queries - preliminary report. In Principles of Database Systems (PODS), pages 297--306, 2004.

Digital Library

[8]

Maurice Bruynooghe, John P. Gallagher, and Wouter van Humbeeck. Inference of well-typings for logic programs with application to termination analysis. In Chris Hankin and Igor Siveroni, editors, Static Analysis Symposium (SAS '05), volume 3672 of Lecture Notes in Computer Science, pages 35--51. Springer, 2005.

Digital Library

[9]

Diego Calvanese, Giuseppe De Giacomo, and Moshe Y. Vardi. Decidable containment of recursive queries. In International Conference on Database Theory (ICDT '03), pages 330--345, 2003.

Digital Library

[10]

Edward P. F. Chan. Containment and minimization of positive conjunctive queries in OODB's. In Principles of Database Systems (PODS), pages 202--211, 1992.

Digital Library

[11]

Surajit Chaudhuri. Finding nonrecursive envelopes for Datalog predicates. In Principles of Database Systems (PODS), pages 135--146, 1993.

Digital Library

[12]

Surajit Chaudhuri and Phokion G. Kolaitis. Can Datalog be approximated? In Principles of Database Systems (PODS), pages 86--96, 1994.

Digital Library

[13]

Horatiu Cirstea and Claude Kirchner. Types for web rule languages: a preliminary study. Technical Report IST5067779/Nancy/I3-D2/D/PU/a1, Rewerse: reasoning on the web, 2004.

[14]

Stavros Cosmadakis, Haim Gaifman, Paris Kanellakis, and Moshe Vardi. Decidable optimization problems for database logic programs. In Proceedings of the 20th annual ACM Symposium on Computing, pages 477--490, 1988.

Digital Library

[15]

Patrick Cousot. Types as abstract interpretations. In Symposium on Principles of Programming Languages (POPL), pages 316--331. ACM Press, 1997.

Digital Library

[16]

Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Symposium on Principles of Programming Languages (POPL), pages 238--252. ACM Press, 1977.

Digital Library

[17]

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. In IEEE Conference on Computational Complexity (CC '97), pages 82--101, 1997.

Digital Library

[18]

Anuj Dawar. Types and indiscernibles in finite models. In J. A. Makowsky, editor, Logic Colloquium '95, Lecture Notes in Logic, pages 51--65. Springer, 1995.

[19]

Oege de Moor, Damien Sereni, Mathieu Verbaere, Elnar Hajiyev, Pavel Avgustinov, Torbjörn Ekman, Neil Ongkingco, and Julian Tibble. .QL: Object-oriented queries made easy. In Ralf Lämmel, João Saraiva, and Joost Visser, editors, Generative and Transformational Techniques in Software Engineering, LNCS. Springer, 2007.

[20]

Oege de Moor, Mathieu Verbaere, Elnar Hajiyev, Pavel Avgustinov, Torbjörn Ekman, Neil Ongkingco, Damien Sereni, and Julian Tibble. .QL for source code analysis. In Source Code Analysis and Manipulation (SCAM '07), pages 3--16. IEEE, 2007.

Digital Library

[21]

Andrew Dinn, Norman W. Paton, M. Howard Williams, Alvaro A. A. Fernandez, and Maria L. Barja. The implementation of a deductive query language over an OODB. In 4th Conference on Deductive and Object-Oriented Databases, volume 1013 of LNCS, pages 143--160. Springer, 1995.

Digital Library

[22]

Thom W. Frühwirth, Ehud Y. Shapiro, Moshe Y. Vardi, and Eyal Yardeni. Logic programs as types for logic programs. In Logic in Computer Science (LICS), pages 300--309. IEEE Computer Society, 1991.

[23]

John P. Gallagher and Kim S. Henriksen. Type analysis and transformation tool. http://wagner.ruc.dk/Tattoo/, 2007.

[24]

John P. Gallagher, Kim S. Henriksen, and Gourinath Banda. Techniques for scaling up analyses based on pre-interpretations. In M. Gabbrielli and G. Gupta, editors, International Conference on Logic Programming (ICLP '05), volume 3668 of LNCS, pages 280--296. Springer, 2005.

Digital Library

[25]

John P. Gallagher and Germán Puebla. Abstract interpretation over non-deterministic finite tree automata for set-based analysis of logic programs. In Practical Aspects of Declarative Languages (PADL), volume 2257 of LNCS, pages 243--261. Springer, 2002.

Digital Library

[26]

Nevin C. Heintze and Joxan Jaffar. A finite presentation theorem for approximating logic programs. In Symposium on Principles of Programming Languages (POPL), pages 197--209, 1990.

Digital Library

[27]

Jakob Henriksson and Jan Maluszyński. Static type-checking of datalog with ontologies. In Hans Jürgen Ohlbach and Sebastian Schaffert, editors, Principles and Practice of Web Reasoning, volume 3208 of LNCS, pages 76--89. Springer, 2004.

[28]

John Hughes. Type specialisation for the lambda-calculus; or, a new paradigm for partial evaluation based on type inference. In Olivier Danvy, Robert Glück, and Peter Thiemann, editors, Dagstuhl Seminar on Partial Evaluation, volume 1110 of LNCS, pages 183--215. Springer, 1996.

Digital Library

[29]

Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, 1993.

Digital Library

[30]

Benjamin S. Lerner, Matthew Flower, Dan Grossman, and Craig Chambers. Searching for type-error messages. In Programming Language Design and Implementation (PLDI), pages 425--434, 2007.

Digital Library

[31]

Alon Y. Levy and Dan Suciu. Deciding containment for queries with complex objects. In Principles of Database Systems (PODS), pages 20--31, 1997.

Digital Library

[32]

Witold Litwin and Tore Risch. Main memory oriented optimization of OO queries using typed datalog with foreign predicates. IEEE Transactions on Knowledge and Data Engineering, 4(6):517--528, 1992.

Digital Library

[33]

Mengchi Liu, Gillian Dobbie, and Tok Wang Ling. A logical foundation for deductive object-oriented databases. ACM Transactions on Database Systems, 27(1):117--151, 2002.

Digital Library

[34]

Kim Marriott, Harald Søndergaard, and Neil D. Jones. Denotational abstract interpretation of logic programs. ACM Transactions on Programming Languages and Systems, 16(3):607--648, 1994.

Digital Library

[35]

Atsushi Ohori, Peter Buneman, and Val Breazu-Tannen. Database programming in Machiavelli - a polymorphic language with static type inference. In Principles of Database Systems, pages 46--57, 1989.

Digital Library

[36]

Benjamin Pierce. Types and Programming Languages. MIT Press, 2002.

Digital Library

[37]

Semmle Ltd. Company website with free downloads, documentation, and discussion forums. http://semmle.com, 2007.

[38]

Oded Shmueli. Equivalence of datalog queries is undecidable. Journal of Logic Programming, 15(3):231--241, 1993.

Digital Library

[39]

Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Etienne Gagnon, and Charles Godin. Practical virtual method call resolution for Java. ACM SIGPLAN Notices, 35(10):264--280, 2000.

Digital Library

[40]

Jeffrey D. Ullman. A comparison between deductive and object-oriented database systems. In 2nd International Conference on Deductive and Object-Oriented Databases, LNCS, pages 263--277, 1991.

[41]

Moshe Y. Vardi. Automata theory for database theoreticians. In Principles of Database Systems (PODS), pages 83--92. ACM Press, 1989.

Digital Library

Cited By

Klopp DErdweg SPacak A(2024)A Typed Multi-level Datalog IR and Its Compiler FrameworkProceedings of the ACM on Programming Languages10.1145/36897678:OOPSLA2(1586-1614)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689767
Meier MSchmidt MWei FLausen G(2013)Semantic query optimization in the presence of typesJournal of Computer and System Sciences10.1016/j.jcss.2013.01.01079:6(937-957)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1016/j.jcss.2013.01.010
De Schutter K(2012)Automated architectural reviews with SemmleProceedings of the 2012 IEEE International Conference on Software Maintenance (ICSM)10.1109/ICSM.2012.6405320(557-565)Online publication date: 23-Sep-2012
https://dl.acm.org/doi/10.1109/ICSM.2012.6405320
Show More Cited By

Index Terms

Type inference for datalog and its application to query optimisation
1. Information systems
  1. Data management systems
    1. Query languages

Recommendations

Type inference for datalog with complex type hierarchies
POPL '10

Type inference for Datalog can be understood as the problem of mapping programs to a sublanguage for which containment is decidable. To wit, given a program in Datalog, a schema describing the types of extensional relations, and a user-supplied set of ...
Type inference for datalog with complex type hierarchies
POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Type inference for Datalog can be understood as the problem of mapping programs to a sublanguage for which containment is decidable. To wit, given a program in Datalog, a schema describing the types of extensional relations, and a user-supplied set of ...
Type checking and inference for polymorphic and existential types
CATS '09: Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory - Volume 94

This paper proves undecidability of type checking and type inference problems in some variants of typed lambda calculi with polymorphic and existential types. First, type inference in the domain-free polymorphic lambda calculus is proved to be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '08: Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2008

330 pages

ISBN:9781605581521

DOI:10.1145/1376916

General Chair:
Phokion Kolaitis
IBM Almaden Research Center, USA
,
Program Chair:
Maurizio Lenzerini
SAPIENZA University of Rome, Italy

Copyright © 2008 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '08

Sponsor:

SIGMOD/PODS '08: SIGMOD/PODS '08 - International Conference on Management of Data

June 9 - 12, 2008

Vancouver, Canada

Acceptance Rates

PODS '08 Paper Acceptance Rate 28 of 159 submissions, 18%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
665
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Klopp DErdweg SPacak A(2024)A Typed Multi-level Datalog IR and Its Compiler FrameworkProceedings of the ACM on Programming Languages10.1145/36897678:OOPSLA2(1586-1614)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689767
Meier MSchmidt MWei FLausen G(2013)Semantic query optimization in the presence of typesJournal of Computer and System Sciences10.1016/j.jcss.2013.01.01079:6(937-957)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1016/j.jcss.2013.01.010
De Schutter K(2012)Automated architectural reviews with SemmleProceedings of the 2012 IEEE International Conference on Software Maintenance (ICSM)10.1109/ICSM.2012.6405320(557-565)Online publication date: 23-Sep-2012
https://dl.acm.org/doi/10.1109/ICSM.2012.6405320
Huang SGreen TLoo BSellis TMiller RKementsietsidis AVelegrakis Y(2011)Datalog and emerging applicationsProceedings of the 2011 ACM SIGMOD International Conference on Management of data10.1145/1989323.1989456(1213-1216)Online publication date: 12-Jun-2011
https://dl.acm.org/doi/10.1145/1989323.1989456
Tekle KLiu YKutsia TSchreiner WFernández M(2010)Precise complexity analysis for efficient datalog queriesProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836094(35-44)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836094
Meier MSchmidt MWei FLausen GParedaens JVan Gucht D(2010)Semantic query optimization in the presence of typesProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807102(111-122)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807102
Schäfer Mde Moor O(2010)Type inference for datalog with complex type hierarchiesACM SIGPLAN Notices10.1145/1707801.170631745:1(145-156)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1707801.1706317
Schäfer Mde Moor OHermenegildo MPalsberg J(2010)Type inference for datalog with complex type hierarchiesProceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1706299.1706317(145-156)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1706299.1706317
Greenshpan OMilo TPolyzotis N(2009)Autocompletion for mashupsProceedings of the VLDB Endowment10.14778/1687627.16876892:1(538-549)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.14778/1687627.1687689
Abiteboul SGreenshpan OMilo TChan CPolyzotis N(2008)Modeling the mashup spaceProceedings of the 10th ACM workshop on Web information and data management10.1145/1458502.1458517(87-94)Online publication date: 30-Oct-2008
https://dl.acm.org/doi/10.1145/1458502.1458517
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents