1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
|
<html>
<head>
<title>An Overview of Datalog</title>
<link href="../../static/favicon.png" rel="icon" />
<link href="../../static/favicon.png" rel="shortcut icon" />
<link media="all" type="text/css" href="../../static/clojure.css" rel="stylesheet" />
<link media="all" type="text/css" href="../../static/wiki.css" rel="stylesheet" />
<link media="all" type="text/css" href="../../static/internal.css" rel="stylesheet" />
<!-- TODO: are we using these (from clojure.org)? If so, add the files -->
<script src="file/view/code_highlighter.js" type="text/javascript"></script>
<script src="file/view/clojure.js" type="text/javascript"></script>
<style>.menuWrapper{height: 36px;}</style>
<!--[if lte IE 6]>
<link rel="stylesheet" href="http://www.wikispaces.com/_/2009051601/s/internal_ie.css" type="text/css" />
<![endif]-->
</head>
<!--
This document was auto-generated from the source by the clojure autodoc system.
To report errors or ask questions about the overall documentation structure, formatting,
etc., contact Tom Faulhaber (google mail name: tomfaulhaber).
For errors in the documentation of a particular namespace, contact the author of that
namespace.
-->
<body>
<div id="AllContentContainer">
<div id="Header">
<a id="Logo" href="index.html"><img alt="Clojure" height="100" width="100" src="../../static/clojure-icon.gif" /></a>
<h1><a title="page header title" id="page-header" href="index.html">Clojure-contrib API Reference</a></h1>
</div>
<div id="leftcolumn"><div style="text-align: center;"></div>
<div class="menu">
<div class="WikiCustomNav WikiElement wiki">
<span class="toc-header"><span id="project-name">clojure-contrib</span> <span id="version">next</span> API</span><br />
<ul>
<li><a class="wiki_link" href="../../index.html">Overview</a></li>
<li><a class="wiki_link" href="../../api-index.html">API Index</a></li>
</ul>
<span class="toc-header">Namespaces</span>
<ul id="left-sidebar-list">
</ul>
<div class="BranchTOC">
<span class="toc-header">Other Versions</span>
<ul id="left-sidebar-branch-list">
<li><a href="../../../index.html" class="wiki_link">v1.2 (beta 1)</a></li><li><a href="../../../branch-1.1.x/index.html" class="wiki_link">v1.1 (stable)</a></li>
</ul>
</div>
<a href="../../http://clojure.org" class="wiki_link">Clojure Home</a>
</div>
</div>
</div>
<div id="rightcolumn">
<div id="Content">
<div class="contentBox"><div class="innerContentBox">
<div id="content_view" class="wiki wikiPage">
<div id="right-sidebar"></div>
<div id="content-tag"><html><body><h1>An Overview of Datalog</h1>
<p>By Jeffrey Straszheim</p>
<p><em>What Datalog is, and what it can do for you.</em></p>
<p><em>Work in Progress</em></p>
<h2>Introduction</h2>
<p>Datalog is a logical query language. It exists somewhere between relational algebra (the formal theory behind SQL) and Prolog, but is closer in motivation to the former than the later. It was invented to apply some of the principles of logic programming to database theory. Its primary addition to the semantics of databases is <em>recursive</em> queries. Examples will be provided below.</p>
<p>The implementation of Datalog that is provided (in this library) departs a bit from the original model insofar as it supports <em>in memory</em> data structures only. It is intended to give developers tools to use relational modeling for their data. A good overview of why you would want to do this is Ben Mosely's <em>Functional Relational Programming</em> material, found here: <a href="http://web.mac.com/ben_moseley/frp/frp.html">http://web.mac.com/ben_moseley/frp/frp.html</a>.</p>
<h2>Details</h2>
<h3>The Database</h3>
<p>Clojure Datalog supports an in memory relational database format, implemented in clojure.contrib.datalog.database (<a href="http://github.com/richhickey/clojure-contrib/blob/master/src/clojure/contrib/datalog/database.clj">here</a>). It supports relations (tables) with named columns and simple hash based indexes. At the present time it does not support any integrity constraints (perhaps later).</p>
<p>Tables are built with <code>make-database</code>, like this:</p>
<pre><code>(make-database
(relation :employee [:id :name :position])
(index :employee :name)
(relation :boss [:employee-id :boss-id])
(index :boss :employee-id)
(relation :can-do-job [:position :job])
(index :can-do-job :position)
(relation :job-replacement [:job :can-be-done-by])
(relation :job-exceptions [:id :job]))
</code></pre>
<p>The schema can be modified by <code>add-relation</code> and <code>add-index</code>. Under the hood, it is standard Clojure map from relation name to relation, and can be directly modified if needed.</p>
<p>Data is added like this:</p>
<pre><code>(add-tuples db-base
[:employee :id 1 :name "Bob" :position :boss]
[:employee :id 2 :name "Mary" :position :chief-accountant]
[:employee :id 3 :name "John" :position :accountant]
[:employee :id 4 :name "Sameer" :position :chief-programmer]
[:employee :id 5 :name "Lilian" :position :programmer]
[:employee :id 6 :name "Li" :position :technician]
[:employee :id 7 :name "Fred" :position :sales]
[:employee :id 8 :name "Brenda" :position :sales]
[:employee :id 9 :name "Miki" :position :project-management]
[:employee :id 10 :name "Albert" :position :technician]
[:boss :employee-id 2 :boss-id 1]
[:boss :employee-id 3 :boss-id 2]
[:boss :employee-id 4 :boss-id 1]
[:boss :employee-id 5 :boss-id 4]
[:boss :employee-id 6 :boss-id 4]
[:boss :employee-id 7 :boss-id 1]
[:boss :employee-id 8 :boss-id 7]
[:boss :employee-id 9 :boss-id 1]
[:boss :employee-id 10 :boss-id 6]
[:can-do-job :position :boss :job :management]
[:can-do-job :position :accountant :job :accounting]
[:can-do-job :position :chief-accountant :job :accounting]
[:can-do-job :position :programmer :job :programming]
[:can-do-job :position :chief-programmer :job :programming]
[:can-do-job :position :technician :job :server-support]
[:can-do-job :position :sales :job :sales]
[:can-do-job :position :project-management :job :project-management]
[:job-replacement :job :pc-support :can-be-done-by :server-support]
[:job-replacement :job :pc-support :can-be-done-by :programming]
[:job-replacement :job :payroll :can-be-done-by :accounting]
[:job-exceptions :id 4 :job :pc-support])
</code></pre>
<p>The meaning is, I believe, obvious.</p>
<p>Functions that add/remove individual tuples are also provided. Use the source.</p>
<h3>Rules</h3>
<p>In addition to the database itself, Datalog lets you define a series of <em>inference rules</em> to apply to your data. Rules look like this:</p>
<pre><code>(<- (:works-for :employee ?x :boss ?y) (:boss :employee-id ?e-id :boss-id ?b-id)
(:employee :id ?e-id :name ?x)
(:employee :id ?b-id :name ?y))
</code></pre>
<p>The <code><-</code> operator represents implication. The first form is the head of the rule, the remainder the body. The meaning is that the head is true if each member of the body is true. We can read this above rule as:</p>
<ul>
<li>An employee (?x) works for a boss (?y) if: in the :boss relation there is an employee id (?e-id) matched to a boss id (?b-id) <em>and</em> in the :employee relation that (?e-id) matches the name (?x) <em>and also</em> in the :employee relation the id (?b-id) matches the name (?y).</li>
</ul>
<p>Notice two things: Logic variables are prefixed by a '?', and the meaning of those variables in a rule can join together entities.</p>
<p>That same rule might be expressed in SQL as:</p>
<pre><code>select e.name, b.name
from employee as e, employee as b, boss
where e.id = boss.employee-id and b.id = boss.boss-id
</code></pre>
<p>However, unlike SQL, Datalog rules can be recursive. Like this:</p>
<pre><code>(<- (:works-for :employee ?x :boss ?y) (:works-for :employee ?x :boss ?z)
(:works-for :employee ?z :boss ?y))
</code></pre>
<p>If you combine these two rules, this builds a <em>transitive closure</em> of the works-for relation. It will return not only ?x's direct boss, but the boss of his boss, and so on. This cannot be done in most forms of SQL.</p>
<h4>Negation and Conditionals</h4>
<p><em>Todo</em></p>
<h3>Queries</h3>
<p>A query is how you request information from a set of rules and a database. Queries look like this:</p>
<pre><code>(?- :works-for :employee ??name :boss ?y)
</code></pre>
<p>Notice the double '?'!</p>
<p>This asks for the name and boss columns from the works-for relation, which was defined by the two rules above. The double ?? allow you to parameterize your query.</p>
<h3>Work Plans</h3>
<p>A set of work rules and a query can form a work plan. It is done like this:</p>
<pre><code>(build-work-plan rules (?- :works-for :employee '??name :boss ?x))
</code></pre>
<p>This takes a set of rules and a query, and performs some basic filtering an optimization. it is a fairly expensive operation, so try to build the plans you need once in your program, or perhaps cache them somehow.</p>
<p>In SQL, a work plan is similar to a prepared statement.</p>
<h3>Running your Work Plan</h3>
<p>You run a work plan like this:</p>
<pre><code>(run-work-plan wp db {'??name "Albert"})
</code></pre>
<p>Where wp is the result of (build-work-plan ...) and db is a database. The last argument is a map of bindings. It provides the specific values for any ??X forms in your query. Given the rules and query defined above, it should return a sequence of tuples of all the people that "Albert" works for.</p>
<h3>Examples</h3>
<p>A completed example is provided at <a href="http://github.com/richhickey/clojure-contrib/blob/master/src/clojure/contrib/datalog/example.clj">http://github.com/richhickey/clojure-contrib/blob/master/src/clojure/contrib/datalog/example.clj</a>.</p>
</body></html></div>
</div>
</div>
</div>
</div>
<div id="foot">
<div style="text-align: center;" id="copyright">Copyright 2007-2010 by Rich Hickey and the various contributors</div>
</div>
</div>
<div id="DesignedBy">Logo & site design by <a title="Visit Tom Hickey's website." href="http://www.tomhickey.com">Tom Hickey</a>.<br />
Clojure auto-documentation system by Tom Faulhaber.</div>
</div>
<!-- /AllContentContainer -->
</body>
</html>
|
