As an experiment, this exercise page interweaves the introduction of some basic concepts, with exercises.


These exercises use a number of different code and data files. They are all collected in one folder on the course web site.

Semantic Networks

For a potted description of semantic networks, you can start with this entry on Wikipedia. (For what "potted" means in this context, see this page.) This figure is from Wikipedia. For a much deeper discussion of semantic network graphs, see this article by John Sowa.

Semantic networks are one of the earliest methods used in AI to represent knowledge. They were popular in the 1960's, but many research groups moved on to other approaches, such as deductive frameworks, for logical power, or frame hierarchies, for efficiency.

Semantic networks have seen a resurgence with the rise of the Semantic Web and its desire to represent very large amounts of symbolic knowledge at web scale, meaning millions of "facts", from thousands of independent sources.

Why are semantic networks web-scalable? Because they can be completely described with triples of the form "subject relation object". For examples, see this introduction from AllegroGraph.

Semantic networks and triples

Triples are kind of like the binary numbers of semantic networks. In the simplest case of an edge connect two concepts, you just need one triple, e.g., (cat has fur).

Some facts relate more than two object, e.g., e.g., between relationships, as in the age of some ancient artifact is between 5000 and 7000 years old. The trick to doing relationships like this is to create an object name that represents the relationship, and then give the parts, like this:

(age-range-12 isa age-range)
(age-range-12 subject goblet-55)
(age-range-12 lower-bound 5000)
(age-range-12 upper-bound 10000)

There are many ways to represent facts, depending on what vocabulary, or ontolgy, you choose to use for the relations and objects.

Semantic Graph Queries

A common tool to query triple stores is SPARQL (SPARQL Protocol and RDF Query Language). This is a query language for RDF triple stores with a syntax inspired by SQL (Structured Query Language) for databases. Here's an example SPARQL query from the Allegro tutorial:

SELECT ?name WHERE {   
  ?x  ?y .   
  ?y   ?name .   

While using an SQL-like syntax may help database programmers get started with semantic networks, it's obscures what is essentially a very simple concept: querying by subgraph.

A graph is just a set of triples. The two triples in the WHERE clause of the query above are a graph. The query is finding all matching subgraphs in the entire triple store. The SELECT is just saying which pattern variables to return afterwards.

simple-triples.lisp defines the function (query query-list triple-store) to take a list of query triples. A query triple may contain pattern variables in any position.

query returns a list of binding lists. There is a binding list for every subset of triples in the global variable *triples* that can match the list of query triples for some set of match bindings.

Time for some exercises!

Exercise: Filtering Queries

Prequisite exercises:
Before doing these exercises, you need to know how to do pattern matching. Do the exercises (not challenges) in the pattern match bundle.

Fix the code query in simple-triples.lisp so that it can do SPARQL-like filters. For query, a filter is any triple whose relation is a function name in a list, e.g., (?year (>) 2000) is a filter that is true if and only if the binding for ?year is greater than 2000.

Filters should work for any defined binary function, including new functions defined with defun. They should handle variable subjects and objects. An error should occur if a variable in a filter has not been bound by a match.

The code in simple-triples.lisp has a start to this problem, but it's broken. If you try (run-tests animals) you'll see how it fails.

Test using (run-tests animals) and (run-tests movies).

Exercise: Reading N-Triples

Instead of converting files to Lisp readable format, it would be better to read RDF triples directly. The simplest format is N-triples. Like our Lisp examples, every line is one triple, ending with a space and period. The difference is that the triples use full URI tokens. Here is an example triple:

<> <> <> .

To read N-triples directly into Lisp, your code needs to

Define the function (read-nt pathname prefixes skip-strings) to read a file of N-triples from the file in pathname, using two lists of data:

For example, the prefix pair (dbp "") says that a URI like <> should be mapped to the Lisp symbol dbp::television-show.

The skip-string "<wordnet_" says you should skip any line containing <wordnet_.

See triple-tests.lisp for the prefixes and skip-strings read-nt should handle.

Test by running (run-tests dbpedia-nt).

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15


Important Links