From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id C1EC17EEAF for ; Mon, 28 Jan 2013 19:19:42 +0100 (CET) Received-SPF: Neutral (mail2-smtp-roc.national.inria.fr: domain of simon.cruanes.2007@m4x.org does not assert whether or not 129.104.30.34 is permitted sender) identity=pra; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=ZXYy=LV=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="simon.cruanes.2007@m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of SRS0=ZXYy=LV=m4x.org=simon.cruanes.2007@bounces.m4x.org designates 129.104.30.34 as permitted sender) identity=mailfrom; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=ZXYy=LV=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="SRS0=ZXYy=LV=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of postmaster@mx1.polytechnique.org designates 129.104.30.34 as permitted sender) identity=helo; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=ZXYy=LV=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="postmaster@mx1.polytechnique.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtwAAA/ABlGBaB4imWdsb2JhbABEq3ySWRYOAQEBAQEICwsHFCeCHgEBBW4EFwsYCQQSDwkDAgECATMSEwYCAQEOh20DDwy2KAOJX5ElA5cpkiQ X-IPAS-Result: AtwAAA/ABlGBaB4imWdsb2JhbABEq3ySWRYOAQEBAQEICwsHFCeCHgEBBW4EFwsYCQQSDwkDAgECATMSEwYCAQEOh20DDwy2KAOJX5ElA5cpkiQ X-IronPort-AV: E=Sophos;i="4.84,553,1355094000"; d="scan'208";a="343634" Received: from mx1.polytechnique.org ([129.104.30.34]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 28 Jan 2013 19:19:42 +0100 Received: from emmental.inria.fr (emmental.inria.fr [128.93.0.14]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ssl.polytechnique.org (Postfix) with ESMTPSA id CBA02140C558C for ; Mon, 28 Jan 2013 19:19:41 +0100 (CET) Message-ID: <5106C131.4030700@m4x.org> Date: Mon, 28 Jan 2013 19:19:29 +0100 From: Simon Cruanes User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-Version: 1.0 To: caml-list@inria.fr References: <51065CFC.8010508@m4x.org> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-AV-Checked: ClamAV using ClamSMTP at svoboda.polytechnique.org (Mon Jan 28 19:19:41 2013 +0100 (CET)) X-Spam-Flag: No, tests=bogofilter, spamicity=0.000888, queueID=E4706140C5590 X-Org-Mail: simon.cruanes.2007@polytechnique.org Subject: Re: [Caml-list] [ANN] Datalog-0.1 Hi, I did not compare its performance with other engines. First, I don't know where to find problem files for benchmarking. Then, the algorithm used here is different from the usual two techniques that are bottom-up (semi)-naive fixpoint computation (with magic sets, etc.), and top-down SLD resolution (akin to prolog). The goal of my library is to enable incremental computation of the fixpoint (for instance, by attaching callbacks to symbols, you can detect new consequences of a fact just after adding this fact). Also, Datalog was originally designed as a database language (it's basically like simple relational algebra, but with recursive queries), but here everything is in memory. However, it would be interesting to compare it with some in-memory engines (there is a simple one in Lua, top-down, if I remember correctly). Regards, -- Simon Cruanes On 01/28/2013 07:06 PM, yoann padioleau wrote: > Hi, > > How does it compare in terms of performance with other datalog engines? > > On Mon, Jan 28, 2013 at 3:11 AM, Simon Cruanes > wrote: >> Hello, >> >> I'm pleased to announce the first (alpha) release of Datalog, a small >> fixpoint engine for the Datalog fragment of logic >> (http://en.wikipedia.org/wiki/Datalog) written in OCaml. The library is >> designed to be used to compute fixpoints of rules, incrementally. It is >> available under the BSD license at https://github.com/c-cube/datalog . >> >> Both a command-line fixpoint computation tool and a functorial library >> are provided. Input files have a prolog-like syntax, but without >> function symbols. The command line tool works like this (the example >> computes the transitive closure of a graph, and then cliques within this >> transitive closure): >> >> $ cat tests/clique10.pl >> reachable(X,Y) :- edge(X,Y). >> reachable(X,Y) :- edge(X,Z), reachable(Z,Y). >> same_clique(X,Y) :- reachable(X,Y), reachable(Y,X). >> edge(0, 1). % edge from 0 to 1 >> edge(1, 2). >> edge(2, 3). >> edge(3, 4). >> edge(4, 5). >> edge(5, 0). >> edge(5, 6). >> edge(6, 7). >> edge(7, 8). >> edge(8, 9). >> edge(9, 10). >> edge(10, 7). >> >> $ ./datalog_cli.native tests/clique10.pl -pattern 'same_clique(1,X)' >> % start datalog >> % parse file tests/clique10.pl >> % process 15 rules >> % computing fixpoint... >> % done. >> % facts matching pattern same_clique(1, X1): >> same_clique(1, 0). >> same_clique(1, 1). >> same_clique(1, 3). >> same_clique(1, 2). >> same_clique(1, 5). >> same_clique(1, 4). >> % max_heap_size: 126976; minor_collections: 0; major collections: 0 >> >> The library provides a functor that allows one to create rules (Datalog >> clauses), and add them to a structure that computes their fixpoint >> incrementally (i.e., the fixpoint is updated after each rule is >> inserted). Callbacks can be associated to symbols, to be called whenever >> a fact is derived. >> >> Feedback, comments, or bug reports are very welcome! >> >> Cheers, >> >> -- >> Simon Cruanes >> >> >> -- >> Caml-list mailing list. Subscription management and archives: >> https://sympa.inria.fr/sympa/arc/caml-list >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs >