Talk:Datalog

It would be nice if the examples were explained, such as "If X is a parent of Y, then we know that X is also an ancestor of Y".

---

in the rule:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- ancestor(X,Z),ancestor(Z,Y).

shouldn't it be:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- ancestor(X,Z),parent(Z,Y).

---

The two formulations are equivalent, as is the formulation:

ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y). 
Logperson (talk) 14:59, 30 April 2008 (UTC)

No, they are not equivalent. Using ancestor twice causes an infinite loop since the Z in the second rule will attempt to unify with Y at some point and thus we end up with ancestor(X,Y) again. I've changed it. Steve Checkoway (talk) 08:04, 21 June 2009 (UTC)

You seem to have some particular execution strategy in mind, say Prolog. However, Datalog without function symbols is decidable and can be implemented in many different, equivalent ways, including the use of forward reasoning, magic sets, or backward reasoning with tabling. Both model-theoretically and in all these correct and complete implementations, the two formulations are equivalent. Logperson (talk) 13:37, 22 June 2009 (UTC)

Magic Sets

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

The result of the discussion is to merge Magic Sets into Datalog. -- Carbo1200 (talk) 16:14, 9 July 2010 (UTC)

---

I don't see why an undescribed algorithm for Datalog processing shouldn't just be here. — Arthur Rubin (talk) 19:39, 21 June 2010 (UTC)

Yes, it makes sense to me. Carbo1200 (talk) 09:43, 22 June 2010 (UTC)

Agreed, magic sets should be in the Datalog article. SeparateWays (talk) 14:55, 2 July 2010 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

do all datalog programs terminate ?

Are we right to say : "These rules make the set of all possible proofs finite, with the consequence that all datalog programs terminate (unlike Prolog programs)" ?

This program never terminates, and thus contradicts the sentence:

loop(X) :- (X1=X+1), loop(X1).

Unless we say that this is not a Datalog program ? But then, why isn't it ? Carbo1200 (talk) 11:11, 12 April 2012 (UTC)

I have modified the article to say that queries on finite sets always terminate. Carbo1200 (talk) 16:01, 13 April 2012 (UTC)

That is not a Datalog program; see the Syntax section, which formally defines the syntax of Datalog programs. I've added a Complexity section, which gives results on the complexity (and hence, termination) of evaluating Datalog programs, and removed the statement about "finite sets" - the Herbrand base of a Datalog program is always finite. siddharthist (talk) 22:35, 2 March 2023 (UTC)

Expressiveness

The queries expressiveness should be made clear in the first paragraph. From what I understand it is more expressive than SQL. OriumX (talk) 23:00, 28 May 2012 (UTC)

Datalog is more expressive than SQL for recursive queries, for example, but is less so for ordering the result set, or calculating aggregates (unless these are provided by datalog language extensions) Carbo1200 (talk) 16:30, 17 June 2012 (UTC)

pyDatalog includes such language extensions to query any database via SQLAlchemy, a data access layer. Carbo1200 (talk) 10:22, 17 July 2012 (UTC)

Datomic

Should we include something about Datomic (http://www.datomic.com/), a commercial database that uses Datalog as its Query language? — Preceding unsigned comment added by 134.99.112.66 (talk) 13:58, 15 October 2012 (UTC)

Datomic is mentioned on the List of Datalog engines, which is linked from this page. siddharthist (talk) 22:36, 2 March 2023 (UTC)

Typo (usage) check

Should "a not negated clause" be "a non-negated clause" (and clause that is not negated)?

If not, clarify what "a not negated clause" means (whether it means something like "a 'not'-negated clause" (a clause that is negated and specifically negated with some "not" function/operator/etc.) or something else).

Jena is written in Java

Jena is definitely a Java-based project, but its query component is called ARQ. — Preceding unsigned comment added by 160.83.42.136 (talk) 12:11, 12 November 2012 (UTC)

The information about Jena has been moved to List of Datalog engines. siddharthist (talk) 22:37, 2 March 2023 (UTC)

Polynomial time

If I'm not mistaken Datalog program do not only always terminate, but they do so in a polynomial amount of time (i.e., you can't implement exponential-time algorithms in Datalog.) —Ruud 09:22, 27 November 2012 (UTC)

Possible references: http://dl.acm.org/citation.cfm?id=113413.113415, http://www.sciencedirect.com/science/article/pii/S0022000085710604, http://www.cl.cam.ac.uk/~ad260/papers/icalp08.pdf, http://homepages.inf.ed.ac.uk/s0932806/icdt09.pdf —Ruud 09:25, 27 November 2012 (UTC)

I've added a section on the complexity of Datalog evaluation which answers this question. siddharthist (talk) 22:37, 2 March 2023 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Datalog. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20120308104055/http://ssdi.di.fct.unl.pt/krr/docs/magicsets.pdf to http://ssdi.di.fct.unl.pt/krr/docs/magicsets.pdf
• Added {{dead link}} tag to https://socialite.stanford.edu/
• Added {{dead link}} tag to ftp://tcl.tk/pub/incoming/p14/Tcl-21st-2014-Portland/KevinKenny/kenny-bdd.pdf
• Added {{dead link}} tag to http://foundationdb.com/documentation/latest/datalog.html
• Added archive https://web.archive.org/web/20070223213744/http://research.microsoft.com:80/projects/SecPAL/ to http://research.microsoft.com/projects/secpal

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 08:26, 7 December 2016 (UTC)

Systems implementing Datalog

Why are the different Datalog implementations grouped by implementation language? Would it not be better to sort them by other Datalog related metrics? e.g. whether they support semi-naive evaluation, stratified negation, locally stratified negation, arithmetic, magic sets, etc. etc. Choice of implementation language seems to be the least important.

Agreed. I plan to make this a stand-alone list, make programming language a column, and make the list consist only of notable entries (as it's gotten quite long).siddharthist (talk) 23:16, 1 March 2023 (UTC)

See List of Datalog engines. siddharthist (talk) 22:38, 2 March 2023 (UTC)

@Siddharthist: The list of Datalog engines has been removed from the Datalog article and has not been submitted as a separate article. Either the draft should be submitted or the section should be restored. Robert Kowalski (talk) 06:10, 28 October 2023 (UTC)

Origins of Datalog

As stated in the book Foundations of Databases (reference [4]), "it is difficult to attribute datalog to particular researchers". Moreover, the name "datalog" certainly does not come from "database dialog".Logperson (talk) 07:28, 21 May 2021 (UTC)

@Logperson: Hi again, this Infobox is required for making structured data for next generation of web i.e., semantic web. See I will omit designer names from it, but the existence of the remaining Infobox knowledge is necessary for performing semantic queries in semantic web. Is that OK? But if you or others can improve this Infobbox, please apply it. Hooman Mallahzadeh (talk) 12:20, 21 May 2021 (UTC)

OK.Logperson (talk) 08:18, 22 May 2021 (UTC)

Free software vs open source

I don't think it makes sense to mix open source with free software in the main list of implementations. It should be a list of open source software with the other proprietary solutions listed separately. List as it currently stands is confusing - what is 'free software'?

Everythingisnail (talk) 18:16, 8 June 2021 (UTC)

The list has been moved to List of Datalog engines, where the license is a column of a table and no mention is made of "free"ness. siddharthist (talk) 22:39, 2 March 2023 (UTC)

The draft List of Datalog engines was never submitted, and has been deleted by an administrator. I restored the deleted version. It is not perfect, but it is better than nothing. Robert Kowalski (talk) 13:44, 7 March 2024 (UTC)

Thanks bkil (talk) 13:59, 7 March 2024 (UTC)

Significance of linear, guarded, frontier-guarded Datalog

What is the significance of these fragments? In particular, "Is this something the topic is widely known for? What is its connection to the topic's notability?" (from WP:TOOMUCH). If we can get such information on the page, great. If not, I propose we remove the "fragments" subsection. siddharthist (talk) 22:51, 3 March 2023 (UTC)

I've removed this section for now, feel free to re-add it with a citation explaining its significance. siddharthist (talk) 04:16, 7 March 2023 (UTC)