This is on the Web at http://pobox.com/~kragen/sw/dhtml-sniki.html. I wrote it in May but for some reason, as far as I can tell, I never got around to telling anyone about it, perhaps because I was too ashamed of the lameness of the implementation. Like everything else posted to this mailing list without notices to the contrary, this is in the public domain. <html> <head> <title>Sniki-like DHTML</title> <!-- Darius Bacon wrote this amazingly cool hack called SnikiSniki, a Wiki that contained typed links --- rather like RDF triples. I wanted to play with this same idea in DHTML (probably with Ajax persistence eventually). This implementation is really lame in several ways: - My implementation of depth-first search on the "knowledge base" is awfully clumsy; I anticipate that in time I will learn to express this concept more clearly in code. - Despite living in the browser, the user interface is the traditional "type text strings into a small box and hit enter" that we've all come to know and love over the last few decades. - There's no way to get the first few results before chewing up large amounts of browser time. --> <script src="http://pobox.com/~kragen/sw/jstest-v1.js"></script> <script> // -*- c -*- // simple (yet over-complex) triple-store library; originally in a // separate file, included here for email function makebits() { var stack = [[]] var results = [] while (stack.length) { var next = stack.pop() if (next.length == 3) results.push(next) else { var choices = [1, 0] for (var choice in choices) { stack.push(next.concat([choices[choice]])) } } } return results } function split_triple(triple) { return triple.split(/\s+/) } function is_var(atomname) { return atomname.match(/^[A-Z]/) } function freevars(triples) { var rv = [] var seen = {} for (var ii in triples) { var items = triples[ii] for (var jj in items) { if (is_var(items[jj]) && !seen[items[jj]]) { rv.push(items[jj]) seen[items[jj]] = 1 } } } return rv } function make_object(names, values) { var rv = {} for (var ii in names) rv[names[ii]] = values[ii] return rv } function map(cb, list) { var rv = [] for (var ii = 0; ii < list.length; ii++) rv.push(cb(list[ii])) return rv } function instantiate(triples, instantiations) { return map(function(triple) { return map(function(atom) {return instantiations[atom] || atom}, triple) }, triples) } function queryfunction(query_triples) { var split_query_triples = map(split_triple, query_triples) var variables = freevars(split_query_triples) var stack = [[]] var rv = [] while (stack.length) { var assignments = stack.pop() var state = make_object(variables, assignments) var instantiated_triples = instantiate(split_query_triples, state) if (this.may_contain(instantiated_triples)) { if (assignments.length == variables.length) { rv.push(state) } else { var current_variable = variables[assignments.length] var possible_values = this.get_candidate_values(instantiated_triples, current_variable) for (var ii in possible_values) { stack.push(assignments.concat([possible_values[ii]])) } } } } return rv } function triple_match(pattern, triple) { var rv = {} for (var jj in pattern) if (!is_var(pattern[jj]) && pattern[jj] != triple[jj]) return null else rv[pattern[jj]] = triple[jj] // XXX note that this will be overly optimistic for multiple occurrences of the variable! return rv } function contains(array, item) { for (var ii = 0; ii < array.length; ii++) if (array[ii] == item) return true return false } function triplestore() { this.triples = [] this.add = function(triples) { for (var x in triples) this.triples.push(split_triple(triples[x])) } this.query = queryfunction this.may_contain = function(triples) { for (var ii in triples) if (!this.may_contain_triple(triples[ii])) return false return true } this.may_contain_triple = function(triple) { for (var ii in this.triples) { if (triple_match(triple, this.triples[ii])) return true; } return false } this.get_candidate_values = function(triples, variable) { // XXX highly duplicative of may_contain! var rv = [] var seen = {} for (var ii in triples) if (contains(triples[ii], variable)) for (var jj in this.triples) { var match = triple_match(triples[ii], this.triples[jj]) if (match && !seen[match[variable]]) { rv.unshift(match[variable]) seen[match[variable]] = 1 } } return rv } } tests = { bits: function() { assert_equal(makebits(), [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]) }, is_var: function() { assert(is_var("A"), "A") assert(!is_var("a"), "a") assert(is_var("Ax"), "Ax") assert(!is_var("xA"), "xA") assert(is_var("Z"), "Z") }, freevars: function() { assert_equal(freevars([]), []) assert_equal(freevars([['a', 'b', 'c']]), []) assert_equal(freevars([['a', 'b', 'C']]), ['C']) assert_equal(freevars([['A', 'B', 'C']]), ['A', 'B', 'C']) assert_equal(freevars([['A', 'A', 'A']]), ['A']) }, make_object: function() { assert_equal(make_object(['beatrice', 'kragen', 'mikel'], ['murch', 'sitaker', 'jay']), {beatrice: 'murch', kragen: 'sitaker', mikel: 'jay'}) }, triplestore: function() { var ts = new triplestore() ts.add(['a b c']) var yes = [{}] var no = [] assert_equal(ts.query([]), yes) assert_equal(ts.query(['a b c']), yes) assert_equal(ts.query(['a b d']), no) assert_equal(ts.query(['a b c', 'a b c']), yes) assert_equal(ts.query(['a b c', 'a b d']), no) assert_equal(ts.query(['a b d', 'a b d']), no) assert_equal(ts.query(['a b d', 'a b c']), no) assert_equal(ts.query(['a b X']), [{X: 'c'}]) assert_equal(ts.query(['a X c']), [{X: 'b'}]) assert_equal(ts.query(['X b c']), [{X: 'a'}]) assert_equal(ts.query(['a X d']), no) assert_equal(ts.query(['a X Y']), [{X: 'b', Y: 'c'}]) assert_equal(ts.query(['a X X']), no) assert_equal(ts.query(['A B C']), [{A: 'a', B: 'b', C: 'c'}]) ts.add(['same c c', 'a b e']) assert_equal(ts.query(['a b c']), yes) assert_equal(ts.query(['a b c', 'a b e']), yes) assert_equal(ts.query(['a b e', 'a b c']), yes) assert_equal(ts.query(['a b d', 'a b c']), no) assert_equal(ts.query(['A B C']), [ {A: 'a', B: 'b', C: 'c'}, {A: 'a', B: 'b', C: 'e'}, {A: 'same', B: 'c', C: 'c'}, ]) assert_equal(ts.query(['A B C', 'A b c']), [ {A: 'a', B: 'b', C: 'c'}, {A: 'a', B: 'b', C: 'e'}]) assert_equal(ts.query(['a b X']), [{X: 'c'}, {X: 'e'}]) assert_equal(ts.query(['X Y Y']), [{X: 'same', Y: 'c'}]) assert_equal(ts.query(['A B C', 'X C Y']), [ {A: 'a', B: 'b', C: 'c', X: 'same', Y: 'c'}, {A:"same", B:"c", C:"c", X:"same", Y:"c"}]) }, triplestore_bits: function() { var ts = new triplestore() ts.add(['bit bit 0', 'bit bit 1']) assert_equal(ts.query(['bit bit B0', 'bit bit B1', 'bit bit B2']), [{B0:"0", B1:"0", B2:"0"}, {B0:"0", B1:"0", B2:"1"}, {B0:"0", B1:"1", B2:"0"}, {B0:"0", B1:"1", B2:"1"}, {B0:"1", B1:"0", B2:"0"}, {B0:"1", B1:"0", B2:"1"}, {B0:"1", B1:"1", B2:"0"}, {B0:"1", B1:"1", B2:"1"}]) }, }; </script> <script> // DHTML bits for this sample page function tablerow(contents, type) { if (!type) type = 'td' var el = document.createElement('tr') for (var ii = 0; ii < contents.length; ii++) { var td = document.createElement(type) td.appendChild(document.createTextNode(contents[ii])) el.appendChild(td) } return el } function clear_node(nod) { nod.innerHTML = '' // Mozilla erroneously caches some layout... fix it var old_display = nod.style.display nod.style.display = 'none' nod.style.display = old_display } function perform_query(qel, ts, triples) { clear_node(qel) var headers = freevars(map(split_triple, triples)) qel.appendChild(tablerow(headers, 'th')) var data = ts.query(triples) for (var ii in data) qel.appendChild(tablerow(map(function(propname){return data[ii][propname]}, headers))) } var ts = new triplestore() function handle_input(somestuff) { var triples = somestuff.split(/,\s*/) var free = freevars(map(split_triple, triples)) if (free.length) { perform_query(document.getElementById('querytable'), ts, triples) } else { // add to triple store var tb = document.getElementById('stufftable') for (var ii in triples) tb.appendChild(tablerow(split_triple(triples[ii]))) ts.add(triples) } return false } function set_up_test_stuff() { handle_input('beatrice parent aggie, beatrice spouse kragen, kragen spouse beatrice, beatrice parent walter, kragen parent greg') handle_input('aggie spouse walter, greg spouse paula') var query = 'Person spouse Spouse, Spouse parent In-law, In-law spouse In-law-2' var field = document.getElementById('theform').stuff field.value = query handle_input(query) field.focus() } </script> </head> <body onload="barebones_run_tests();set_up_test_stuff()"><h1>Toy triple store in DHTML</h1> <p> Inspired by Sniki.</p> <table id="stufftable"> <tr><th>object</th><th>property</th><th>value</th></tr> </table> <table id="querytable"> </table> <form id="theform" onsubmit="return handle_input(this.stuff.value)"> <input size="80" name="stuff" /> </form> </body> </html>
