Talk:Datalog

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

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[edit]

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 above discussion is closed. Please do not modify it. Subsequent comments should be made in a new section.

do all datalog programs terminate ?[edit]

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)

Expressiveness[edit]

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[edit]

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)

Typo (usage) check[edit]

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[edit]

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)

Polynomial time[edit]

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.pdfRuud 09:25, 27 November 2012 (UTC)

External links modified[edit]

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:

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

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • 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.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

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