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

research-article

Open access

Datalog Unchained

Author:

Victor VianuAuthors Info & Claims

PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Pages 57 - 69

https://doi.org/10.1145/3452021.3458815

Published: 20 June 2021 Publication History

Abstract

This is the companion paper of a talk in the Gems of PODS series, that reviews the development, starting at PODS 1988, of a family of Datalog-like languages with procedural, forward chaining semantics, providing an alternative to the classical declarative, model-theoretic semantics. These languages also provide a unified formalism that can express important classes of queries including fixpoint, while, and all computable queries. They can also incorporate in a natural fashion updates and nondeterminism. Datalog variants with forward chaining semantics have been adopted in a variety of settings, including active databases, production systems, distributed data exchange, and data-driven reactive systems.

References

[1]

S. Abiteboul and G. Grahne. Update semantics for incomplete databases. In Proc. of Intl. Conf. on Very Large Data Bases, pages 1--12, 1985.

[2]

S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases. Addison Wesley, 1995.

Digital Library

[3]

S. Abiteboul, E. Simon, and V. Vianu. Non-deterministic languages to express deterministic transformations. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 218--229, 1990.

Digital Library

[4]

S. Abiteboul and V. Vianu. A transaction language complete for database update and specification. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 260--268, 1987.

Digital Library

[5]

S. Abiteboul and V. Vianu. Procedural and declarative database update languages. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 240--250, 1988.

Digital Library

[6]

S. Abiteboul and V. Vianu. Datalog extensions for database queries and updates. Journal of Computer and System Sciences, 43:62--124, 1991.

Digital Library

[7]

S. Abiteboul and V. Vianu. Generic computation and its complexity. In Proc. ACM SIGACT Symp. on the Theory of Computing, pages 209--219, 1991.

Digital Library

[8]

S. Abiteboul and V. Vianu. Non-determinism in logic-based languages. Annals of Math. and Artif. Int., 3:151--186, 1991.

[9]

Serge Abiteboul, Zoë Abrams, Stefan Haar, and Tova Milo. Diagnosis of asynchronous discrete event systems: datalog to the rescue! In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 358--367, 2005.

Digital Library

[10]

Serge Abiteboul, Omar Benjelloun, and Tova Milo. The Active XML project: an overview. VLDB J., 17(5):1019--1040, 2008.

Digital Library

[11]

Serge Abiteboul, Meghyn Bienvenu, Alban Galland, and É milien Antoine. A rule-based language for web data management. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 293--304, 2011.

Digital Library

[12]

Serge Abiteboul and Paris C. Kanellakis. Object identity as a query language primitive. J. ACM, 45(5):798--842, 1998.

Digital Library

[13]

Serge Abiteboul, Luc Segoufin, and Victor Vianu. Static analysis of active XML systems. ACM Trans. Database Syst., 34(4):23:1--23:44, 2009. Also in PODS 2008.

Digital Library

[14]

Serge Abiteboul and Victor Vianu. Fixpoint extensions of first-order logic and Datalog-like languages. In Proc. IEEE Symp. on Logic in Computer Science, pages 71--79, 1989.

[15]

Serge Abiteboul and Victor Vianu. Non-determinism in logic-based languages. Ann. Math. Artif. Intell., 3(2--4):151--186, 1991.

[16]

Serge Abiteboul and Victor Vianu. Collaborative data-driven workflows: think global, act local. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 91--102, 2013.

Digital Library

[17]

A. V. Aho and J. D. Ullman. Universality of data retrieval languages. In Proc. ACM Symp. on Principles of Programming Languages, pages 110--117, 1979.

Digital Library

[18]

Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and William R. Marczak. Consistency analysis in Bloom: a CALM and collected approach. In CIDR 2011, Fifth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 9--12, 2011, Online Proceedings, pages 249--260, 2011.bibitemAlvaroMCHMS10Peter Alvaro, William R. Marczak, Neil Conway, Joseph M. Hellerstein, David Maier, and Russell Sears. Dedalus: Datalog in time and space. In Datalog Reloaded - First International Workshop, Datalog 2010, Oxford, UK, March 16--19, 2010. Revised Selected Papers, volume 6702 of Lecture Notes in Computer Science, pages 262--281. Springer, 2010.

[19]

Mario Alviano and Andreas Pieris, editors. Datalog 2.0 2019 - 3rd International Workshop on the Resurgence of Datalog in Academia and Industry co-located with the 15th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2019) at the Philadelphia Logic Week 2019, Philadelphia, PA (USA), June 4--5, 2019, volume 2368 of CEUR Workshop Proceedings. CEUR-WS.org, 2019.

[20]

Tom J. Ameloot. Declarative networking: Recent theoretical work on coordination, correctness, and declarative semantics. SIGMOD Rec., 43(2):5--16, 2014.

Digital Library

[21]

Tom J. Ameloot and Jan Van den Bussche. Deciding eventual consistency for a simple class of relational transducer networks. In Alin Deutsch, editor, Proc. of Intl. Conf. on Database Theory, pages 86--98, 2012.

[22]

Tom J. Ameloot, Jan Van den Bussche, William R. Marczak, Peter Alvaro, and Joseph M. Hellerstein. Putting logic-based distributed systems on stable grounds. Theory Pract. Log. Program., 16(4):378--417, 2016.

[23]

Tom J. Ameloot, Bas Ketsman, Frank Neven, and Daniel Zinn. Weaker forms of monotonicity for declarative networking: A more fine-grained answer to the calm-conjecture. ACM Trans. Database Syst., 40(4):21:1--21:45, 2016.

Digital Library

[24]

Tom J. Ameloot, Frank Neven, and Jan Van den Bussche. Relational transducers for declarative networking. J. ACM, 60(2):15:1--15:38, 2013. Also in PODS 2011.

Digital Library

[25]

J. Anderson, M. Gaare, J. Holgu´n, N. Bailey, and T. Pratley. The Datomic database, pages 169--215. In Professional Clojure, Wiley Online Library, 2016.

[26]

K. Apt and M. van Emden. Contributions to the theory of logic programming. J. ACM, 29(3):841--862, 1982.

Digital Library

[27]

K.R. Apt, H. Blair, and A. Walker. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89--148. Morgan Kaufmann, Los Altos, CA, 1988.

Digital Library

[28]

Molham Aref, Balder ten Cate, Todd J. Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn. Design and implementation of the LogicBlox system. In Proc. ACM SIGMOD Intl. Conf. on Management of Data, pages 1371--1382, 2015.

Digital Library

[29]

Marcelo Arenas, Georg Gottlob, and Andreas Pieris. Expressive languages for querying the semantic web. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 14--26, 2014.

Digital Library

[30]

Pablo Barceló and Reinhard Pichler, editors. Datalog in Academia and Industry - Second International Workshop, Datalog 2.0, Vienna, Austria, September 11--13, 2012. Proceedings, volume 7494 of Lecture Notes in Computer Science. Springer, 2012.

Digital Library

[31]

Robert Baumgartner, Sergio Flesca, and Georg Gottlob. Visual web information extraction with lixto. In Proc. of Intl. Conf. on Very Large Data Bases, pages 119--128, 2001.

[32]

Luigi Bellomarini, Georg Gottlob, Andreas Pieris, and Emanuel Sallinger. Swift logic for big data and knowledge graphs. In Proc. of the Intl. Joint Conference on Artificial Intelligence, IJCAI 2017, pages 2--10, 2017.

[33]

Luigi Bellomarini, Emanuel Sallinger, and Georg Gottlob. The Vadalog system: Datalog-based reasoning for knowledge graphs. Proc. VLDB Endow., 11(9):975--987, 2018.

Digital Library

[34]

Gerald Berger, Georg Gottlob, Andreas Pieris, and Emanuel Sallinger. The space-efficient core of Vadalog. In Proc. ACM SIGMOD-SIGACT-SIGAI Symp. on Principles of Database Systems, pages 270--284, 2019.

Digital Library

[35]

N. Bidoit and C. Froidevaux. Minimalism subsumes default logic and circumscription. In Proc. IEEE Symp. on Logic in Computer Science, pages 89--97, 1987.

[36]

N. Bidoit and C. Froidevaux. General logic databases and programs: Default logic semantics and stratification. J. Information and Computation, 91(1):15--54, 1991.

Digital Library

[37]

L. Brownston, R. Farrel, E. Kant, and N. Martin. Programming Expert Systems in OPS5 . Addison Wesley, 1985.

Digital Library

[38]

Lee Brownston, Robert Farrell, Elaine Kant, and Nancy Martin. Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming. Addison-Wesley Longman Publishing Co., Inc., USA, 1985.

Digital Library

[39]

Andrea Cal`i, Georg Gottlob, and Thomas Lukasiewicz. Datalog(^mbox(pm) ): a unified approach to ontologies and integrity constraints. In Ronald Fagin, editor, Proc. of Intl. Conf. on Database Theory, volume 361, pages 14--30, 2009.

Digital Library

[40]

Andrea Cal`i, Georg Gottlob, and Thomas Lukasiewicz. Datalog(^mbox(pm) ): a unified approach to ontologies and integrity constraints. In Proc. of Intl. Conf. on Database Theory, volume 361, pages 14--30, 2009.

Digital Library

[41]

Andrea Cal`i, Georg Gottlob, Thomas Lukasiewicz, Bruno Marnette, and Andreas Pieris. Datalog

[42]

/-: A family of logical knowledge representation and query languages for new applications. In Proc. IEEE Symp. on Logic in Computer Science, pages 228--242, 2010.

[43]

Andrea Cal`i and Michael Kifer. Containment of conjunctive object meta-queries. In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12--15, 2006, pages 942--952, 2006.

[44]

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Dl-lite: Tractable description logics for ontologies. In Proceedings, The Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, July 9--13, 2005, Pittsburgh, Pennsylvania, USA, pages 602--607, 2005.

[45]

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reason., 39(3):385--429, 2007.

Digital Library

[46]

Diego Calvanese, Giuseppe De Giacomo, and Marco Montali. Foundations of data-aware process analysis: a database theory perspective. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 1--12, 2013.

Digital Library

[47]

A. K. Chandra. Programming primitives for database languages. In Proc. ACM Symp. on Principles of Programming Languages, pages 50--62, 1981.

Digital Library

[48]

A.K. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156--178, 1980.

[49]

A.K. Chandra and D. Harel. Structure and complexity of relational queries. Journal of Computer and System Sciences, 25(1):99--128, 1982.

[50]

A.K. Chandra and D. Harel. Horn clause queries and generalizations. J. Logic Programming, 2(1):1--15, 1985.

[51]

E. F. Codd. A relational model of data for large shared data banks. Comm. of the ACM, 13(6):377--387, 1970.

Digital Library

[52]

L. Corciulo, F. Giannotti, and D. Pedreschi. Datalog with non-deterministic choice computes NDB-PTIME. In Proc. of Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), 93.

[53]

E. Dalhaus. Skolem normal forms concerning the least fixpoint. In E. Börger, editor, Computation Theory and Logic, volume 270, pages 101--106. Springer Verlag, Lecture Notes in Computer Science, Berlin/New York, 1987.

[54]

Evgeny Dantsin, Thomas Eiter, Georg Gottlob, and Andrei Voronkov. Complexity and expressive power of logic programming. ACM Comput. Surv., 33(3):374--425, 2001.

Digital Library

[55]

Oege de Moor, Georg Gottlob, Tim Furche, and Andrew Jon Sellers, editors. Datalog Reloaded - First International Workshop, Datalog 2010, Oxford, UK, March 16--19, 2010. Revised Selected Papers, volume 6702 of Lecture Notes in Computer Science. Springer, 2011.

[56]

Alin Deutsch, Richard Hull, and Victor Vianu. Automatic verification of database-centric systems. SIGMOD Rec., 43(3):5--17, 2014.

Digital Library

[57]

Jö rg Flum, Max Kubierschky, and Bertram Lud"a scher. Total and partial well-founded Datalog coincide. In Proc. of Intl. Conf. on Database Theory, pages 113--124, 1997.

[58]

Jö rg Flum, Max Kubierschky, and Bertram Lud"a scher. Games and total Datalog(not) queries. Theor. Comput. Sci., 239(2):257--276, 2000.

Digital Library

[59]

C. L. Forgy. OPS5 user's manual. Technical Report Carnegie Mellon University-CS-81--135, Carnegie Mellon University, 1981.

[60]

Tim Furche, Georg Gottlob, Giovanni Grasso, Xiaonan Guo, Giorgio Orsi, Christian Schallhart, and Cheng Wang. DIADEM: thousands of websites to a single database. Proc. VLDB Endow., 7(14):1845--1856, 2014.

Digital Library

[61]

A. Van Gelder. Negation as failure using tight derivations for general logic programs. In IEEE Symp. on Logic Programming, pages 127--139, 1986.

[62]

A. Van Gelder. The alternating fixpoint of logic programs with negation. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 1--11, 1989.

Digital Library

[63]

A. Van Gelder, K.A. Ross, and J.S. Schlipf. The well-founded semantics for general logic programs. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 221--230, 1988.

Digital Library

[64]

A. Van Gelder, K.A. Ross, and J.S. Schlipf. The well-founded semantics for general logic programs. J. ACM, 38:620--650, 1991.

Digital Library

[65]

M. Gelfond and V. Lifschitz. The stable model semantics for logic programs. In Intl. Conf. on Logic Programming, pages 1070--1080, 1988.

[66]

F. Giannotti, D. Pedreschi, D. Saccà, and C. Zaniolo. Nondeterminism in deductive databases. In Proc. of Intl. Conf. on Deductive and Object-Oriented Databases (DOOD), pages 129--146, Los Altos, CA, 1991. Springer Verlag, Lecture Notes in Computer Science 566.

[67]

Georg Gottlob and Christoph Koch. Monadic queries over tree-structured data. In Proc. IEEE Symp. on Logic in Computer Science, pages 189--202, 2002.

[68]

Georg Gottlob and Christoph Koch. Monadic datalog and the expressive power of languages for web information extraction. J. ACM, 51(1):74--113, 2004. Also in PODS 2002.

Digital Library

[69]

Georg Gottlob, Christoph Koch, Robert Baumgartner, Marcus Herzog, and Sergio Flesca. The lixto data extraction project - back and forth between theory and practice. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 1--12, 2004.

[70]

Georg Gottlob, Reinhard Pichler, and Emanuel Sallinger. Function symbols in tuple-generating dependencies: Expressive power and computability. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 65--77, 2015.

Digital Library

[71]

Georg Gottlob, Reinhard Pichler, and Fang Wei. Bounded treewidth as a key to tractability of knowledge representation and reasoning. In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16--20, 2006, Boston, Massachusetts, USA, pages 250--256, 2006.

[72]

Georg Gottlob, Reinhard Pichler, and Fang Wei. Tractable database design through bounded treewidth. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 124--133, 2006.

Digital Library

[73]

Georg Gottlob, Reinhard Pichler, and Fang Wei. Abduction with bounded treewidth: From theoretical tractability to practically efficient computation. In Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, Illinois, USA, July 13--17, 2008, pages 1541--1546, 2008.

[74]

Georg Gottlob, Reinhard Pichler, and Fang Wei. Monadic datalog over finite structures of bounded treewidth. ACM Trans. Comput. Log., 12(1):3:1--3:48, 2010. Also in PODS 2007.

Digital Library

[75]

Georg Gottlob and Andreas Pieris. Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25--31, 2015, pages 2999--3007, 2015.

[76]

Sergio Greco, Domenico Saccà, and Carlo Zaniolo. Extending stratified datalog to capture complexity classes ranging from P to QH. Acta Informatica, 37(10):699--725, 2001.

Digital Library

[77]

Todd J. Green, Shan Shan Huang, Boon Thau Loo, and Wenchao Zhou. Datalog and recursive query processing. Found. Trends Databases, 5(2):105--195, 2013.

Digital Library

[78]

Todd J. Green, Gregory Karvounarakis, Nicholas E. Taylor, Olivier Biton, Zachary G. Ives, and Val Tannen. ORCHESTRA: facilitating collaborative data sharing. In Proc. ACM SIGMOD Intl. Conf. on Management of Data, pages 1131--1133, 2007.

[79]

Martin Grohe. The quest for a logic capturing PTIME. In Proc. IEEE Symp. on Logic in Computer Science, pages 267--271, 2008.

Digital Library

[80]

Joseph M. Hellerstein. Datalog redux: experience and conjecture. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 1--2. ACM, 2010.

Digital Library

[81]

Joseph M. Hellerstein. The declarative imperative: experiences and conjectures in distributed logic. SIGMOD Rec., 39(1):5--19, 2010.

Digital Library

[82]

T. Imielinski and W. Lipski. The relational model of data and cylindric algebras. Journal of Computer and System Sciences, 28(1):80--102, 1984.

[83]

N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86--104, 1986.

Digital Library

[84]

Zachary G. Ives, Todd J. Green, Grigoris Karvounarakis, Nicholas E. Taylor, Val Tannen, Partha Pratim Talukdar, Marie Jacob, and Fernando C. N. Pereira. The ORCHESTRA collaborative data sharing system. SIGMOD Rec., 37(3):26--32, 2008.

Digital Library

[85]

Michael Kifer, Georg Lausen, and James Wu. Logical foundations of object-oriented and frame-based languages. J. ACM, 42(4):741--843, 1995.

Digital Library

[86]

P. G. Kolaitis. The expressive power of stratified logic programs. Information and Computation, 90(1):50--66, 1991.

Digital Library

[87]

P. G. Kolaitis and C.H. Papadimitriou. Why not negation by fixpoint? In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 231--239, 1988.

Digital Library

[88]

S. Konolige. On the relation between default and autoepistemic logic. Artificial Intelligence, 35(3):343--382, 1988.

Digital Library

[89]

Nikolaos Konstantinou, Martin Koehler, Edward Abel, Cristina Civili, Bernd Neumayr, Emanuel Sallinger, Alvaro A. A. Fernandes, Georg Gottlob, John A. Keane, Leonid Libkin, and Norman W. Paton. The VADA architecture for cost-effective data wrangling. In Proc. ACM SIGMOD Intl. Conf. on Management of Data, pages 1599--1602, 2017.

Digital Library

[90]

R. Krishnamurthy and S.A. Naqvi. Nondeterministic choice in datalog. In 5th Int'l. Conf. on Data and Knowledge Bases, pages 416--424, Los Altos, CA, 1988. Morgan Kaufmann.

[91]

Georg Lausen, Bertram Lud"a scher, and Wolfgang May. On active deductive databases: The Statelog approach. In Transactions and Change in Logic Databases, International Seminar on Logic Databases and the Meaning of Change, Schloss Dagstuhl, Germany, September 23--27, 1996 and ILPS '97 Post-Conference Workshop on (Trans)Actions and Change in Logic Programming and Deductive Databases, (DYNAMICS'97) Port Jefferson, NY, USA, October 17, 1997, Invited Surveys and Selected Papers, volume 1472 of Lecture Notes in Computer Science, pages 69--106. Springer, 1998.

Digital Library

[92]

V. Lifschitz. On the declarative semantics of logic programs with negation. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 177--192. Morgan Kaufmann, Los Altos, CA, 1988.

Digital Library

[93]

Boon Thau Loo, Tyson Condie, Minos N. Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, and Ion Stoica. Declarative networking. Commun. ACM, 52(11):87--95, 2009.

Digital Library

[94]

Boon Thau Loo, Harjot Gill, Changbin Liu, Yun Mao, William R. Marczak, Micah Sherr, Anduo Wang, and Wenchao Zhou. Recent advances in declarative networking. In Claudio V. Russo and Neng-Fa Zhou, editors, Practical Aspects of Declarative Languages - 14th International Symposium, PADL 2012, Philadelphia, PA, USA, January 23--24, 2012. Proceedings, volume 7149 of Lecture Notes in Computer Science, pages 1--16. Springer, 2012.

Digital Library

[95]

D. Maier and D. S. Warren. Computing with Logic: Logic Programming with Prolog. Benjamin Cummings, Menlo Park, CA, 1988.

Digital Library

[96]

David Maier, K. Tuncay Tekle, Michael Kifer, and David Scott Warren. Datalog: concepts, history, and outlook. In Michael Kifer and Yanhong Annie Liu, editors, Declarative Logic Programming: Theory, Systems, and Applications, pages 3--100. ACM / Morgan & Claypool, 2018.

Digital Library

[97]

R.C. Moore. Semantics considerations on non-monotonic logic. Artificial Intelligence, 25:75--94, 1985.

Digital Library

[98]

Y.N. Moschovakis. Elementary Induction on Abstract Structures. North Holland, 1974.

Digital Library

[99]

S. Naqvi and S. Tsur. A language for data and knowledge bases. Computer Science Press, Rockville, Maryland, 1989.

Digital Library

[100]

Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms: [extended abstract]. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 37--48. ACM, 2012.

Digital Library

[101]

C.P. Papadimitriou. A note on the expressive power of prolog. Bulletin of the EATCS, 26:21--23, 1985.

[102]

The Laguna Beach Participants. Future directions in DBMS research. SIGMOD Rec., 18(1):17--26, 1989.

Digital Library

[103]

Juan Antonio Navarro Pé rez and Andrey Rybalchenko. Operational semantics for declarative networking. In Practical Aspects of Declarative Languages, 11th International Symposium, PADL 2009, Savannah, GA, USA, January 19--20, 2009. Proceedings, volume 5418 of Lecture Notes in Computer Science, pages 76--90. Springer, 2009.

[104]

Philippe Picouet and Victor Vianu. Semantics and expressiveness issues in active databases. J. Comput. Syst. Sci., 57(3):325--355, 1998. Also in ICDT 1997.

Digital Library

[105]

T. Przymusinski. Every logic program has a natural stratification and an iterated least fixpoint model. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 11--21, 1989.

[106]

T. Przymusinski. Well-founded semantics coincides with three-valued stable semantics. Fundamenta Informaticae, XIII:445--463, 1990.

[107]

R. Ramakrishnan and J.D. Ullman. A survey of deductive database systems. J. Logic Programming, 23(2):125--149, 1995.

[108]

R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1):80--132, 1980.

[109]

D. Saccà and C. Zaniolo. Stable models and non-determinism in logic programs with negation. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems, pages 205--217, 1990.

Digital Library

[110]

Alexander Shkapsky, Mohan Yang, Matteo Interlandi, Hsuan Chiu, Tyson Condie, and Carlo Zaniolo. Big data analytics with datalog queries on spark. In Proc. ACM SIGMOD Intl. Conf. on Management of Data, pages 1135--1149, 2016.

Digital Library

[111]

Michael Stonebraker and Joseph M. Hellerstein, editors. Readings in Database Systems, Third Edition. Morgan Kaufmann, 1998.

[112]

VADA project website. http://vada.org.uk, 2021. Accessed: 2021-03-04.

[113]

M. H. van Emden and R. A. Kowalski. The semantics of predicate logic as a programming language. J. ACM, 23(4):733--742, 1976.

Digital Library

[114]

M. Y. Vardi. The complexity of relational query languages. In Proc. ACM SIGACT Symp. on the Theory of Computing, pages 137--146, 1982.

[115]

Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. of Intl. Conf. on Database Theory, pages 96--106, 2014.

[116]

Victor Vianu. Rule-based languages. Ann. Math. Artif. Intell., 19(1--2):215--259, 1997.

[117]

J. Widom and S. Ceri. Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan-Kaufmann, 1995.

[118]

Carlo Zaniolo, Mohan Yang, Ariyam Das, Alexander Shkapsky, Tyson Condie, and Matteo Interlandi. Fixpoint semantics and optimization of recursive datalog programs with aggregates. Theory Pract. Log. Program., 17(5--6):1048--1065, 2017.

Cited By

Bellomarini LBenedetto DBrandetti MSallinger EVlad A(2025)The Vadalog Parallel System: Distributed Reasoning with Datalog+/-Proceedings of the VLDB Endowment10.14778/3704965.370497017:13(4614-4626)Online publication date: 18-Feb-2025
https://doi.org/10.14778/3704965.3704970
Fejza AGenevès PLayaïda N(2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681986
Abo Khamis MNgo HPichler RSuciu DWang Y(2024)Convergence of datalog over (Pre-) SemiringsJournal of the ACM10.1145/364302771:2(1-55)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3643027
Show More Cited By

Index Terms

Datalog Unchained
1. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)
      2. Logic and databases

Recommendations

Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues

Datalog is one of the best-known rule-based languages, and extensions of it are used in a wide context of applications. An important Datalog extension is Disjunctive Datalog , which significantly increases the expressivity of the basic language. ...
Semi-Inflationary DATALOG: A declarative database language with procedural features

This paper presents a rule-based database language which extends stratified DATALOG by adding a controlled form of inflationary fixpoint, immersed in a context of classical stratified negation with least fixpoint. The proposed language, called Semi-...
On the complexity of single-rule datalog queries
Special issue: ICC '99

Datalog programs containing a unique rule and possibly some facts are known as single rule programs, or sirups. We study the complexity of evaluating sirups over variable and fixed databases, respectively, as well as the descriptive complexity of sirups,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

June 2021

440 pages

ISBN:9781450383813

DOI:10.1145/3452021

General Chair:
Leonid Libkin
University of Edinburgh, UK and ENS-Paris, France
,
Program Chairs:
Reinhard Pichler
TU Wien, Austria
,
Paolo Guagliardo
University of Edinburgh, UK

Copyright © 2021 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2021

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation
ANR Headwork

Conference

SIGMOD/PODS '21

Sponsor:

SIGMOD

SIGMOD/PODS '21: International Conference on Management of Data

June 20 - 25, 2021

Virtual Event, China

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
718
Total Downloads

Downloads (Last 12 months)236
Downloads (Last 6 weeks)22

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bellomarini LBenedetto DBrandetti MSallinger EVlad A(2025)The Vadalog Parallel System: Distributed Reasoning with Datalog+/-Proceedings of the VLDB Endowment10.14778/3704965.370497017:13(4614-4626)Online publication date: 18-Feb-2025
https://doi.org/10.14778/3704965.3704970
Fejza AGenevès PLayaïda N(2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681986
Abo Khamis MNgo HPichler RSuciu DWang Y(2024)Convergence of datalog over (Pre-) SemiringsJournal of the ACM10.1145/364302771:2(1-55)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3643027
Angles RGottlob GPavlović APichler RSallinger E(2023)SparqLog: A System for Efficient Evaluation of SPARQL 1.1 Queries via DatalogProceedings of the VLDB Endowment10.14778/3625054.362506116:13(4240-4253)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.14778/3625054.3625061
Bellomarini LBenedetto DBrandetti MSallinger E(2022)Exploiting the Power of Equality-Generating Dependencies in Ontological ReasoningProceedings of the VLDB Endowment10.14778/3565838.356585015:13(3976-3988)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.14778/3565838.3565850
Khamis MNgo HPichler RSuciu DRemy Wang Y(2022)Datalog in WonderlandACM SIGMOD Record10.1145/3552490.355249251:2(6-17)Online publication date: 29-Jul-2022
https://dl.acm.org/doi/10.1145/3552490.3552492
Wang YAbo Khamis MNgo HPichler RSuciu DIves ZBonifati AEl Abbadi A(2022)Optimizing Recursive Queries with Progam SynthesisProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517827(79-93)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517827

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten