To begin with, create a file called simplegraph.py. The first thing we’ll do is create a class that will be our triplestore and add an initialization method that creates the three indexes:

class SimpleGraph:
    def __init__(self):
        self._spo = {}
        self._pos = {}
        self._osp = {} 

Each of the three indexes holds a different permutation of each triple that is stored in the graph. The name of the index indicates the ordering of the terms in the index (i.e., the pos index stores the predicate, then the object, and then the subject, in that order). The index is structured using a dictionary containing dictionaries that in turn contain sets, with the first dictionary keyed off of the first term, the second dictionary keyed off of the second term, and the set containing the third terms for the index. For example, the pos index could be instantiated with a new triple like so:

self._pos = {predicate:{object:set([subject])}}

A query for all triples with a specific predicate and object could be answered like so:

for subject in self._pos[predicate][object]: yield (subject, predicate, object)

Each triple is represented in each index using a different permutation, and this allows any query across the triples to be answered simply by iterating over a single index.

The add method permutes the subject, predicate, and object to match the ordering of each index:

    def add(self, (sub, pred, obj)):
        self._addToIndex(self._spo, sub, pred, obj)
        self._addToIndex(self._pos, pred, obj, sub)
        self._addToIndex(self._osp, obj, sub, pred)

The _addToIndex method adds the terms to the index, creating a dictionary and set if the terms are not already in the index:

    def _addToIndex(self, index, a, b, c):
        if a not in index: index[a] = {b:set([c])}
        else:
            if b not in index[a]: index[a][b] = set([c])
            else: index[a][b].add(c)     

The remove method finds all triples that match a pattern, permutes them, and removes them from each index:

    def remove(self, (sub, pred, obj)):
        triples = list(self.triples((sub, pred, obj)))
        for (delSub, delPred, delObj) in triples:
            self._removeFromIndex(self._spo, delSub, delPred, delObj)
            self._removeFromIndex(self._pos, delPred, delObj, delSub)
            self._removeFromIndex(self._osp, delObj, delSub, delPred)

The _removeFromIndex walks down the index, cleaning up empty intermediate dictionaries and sets while removing the terms of the triple:

    def _removeFromIndex(self, index, a, b, c):
        try:
            bs = index[a]
            cset = bs[b]
            cset.remove(c)
            if len(cset) == 0: del bs[b]
            if len(bs) == 0: del index[a]
        # KeyErrors occur if a term was missing, which means that it wasn't a
        # valid delete:
        except KeyError:
            pass        

Finally, we’ll add methods for loading and saving the triples in the graph to comma-separated files. Make sure to import the csv module at the top of your file:

    def load(self, filename):
        f = open(filename, "rb")
        reader = csv.reader(f)
        for sub, pred, obj in reader:
            sub = unicode(sub, "UTF-8")
            pred = unicode(pred, "UTF-8")
            obj = unicode(obj, "UTF-8")
            self.add((sub, pred, obj))
        f.close()

     def save(self, filename):
        f = open(filename, "wb")
        writer = csv.writer(f)
        for sub, pred, obj in self.triples((None, None, None)):
            writer.writerow([sub.encode("UTF-8"), pred.encode("UTF-8"), 
                obj.encode("UTF-8")])
        f.close()

The basic query method takes a (subject, predicate, object) pattern and returns all triples that match the pattern. Terms in the triple that are set to None are treated as wildcards. The triples method determines which index to use based on which terms of the triple are wildcarded, and then iterates over the appropriate index, yielding triples that match the pattern:

    def triples(self, (sub, pred, obj)):
        # check which terms are present in order to use the correct index:
        try:
            if sub != None: 
                if pred != None:
                    # sub pred obj
                    if obj != None:
                        if obj in self._spo[sub][pred]: 
                            yield (sub, pred, obj)
                    # sub pred None
                    else:
                        for retObj in self._spo[sub][pred]: 
                             yield (sub, pred, retObj)
                else:
                    # sub None obj
                    if obj != None:
                        for retPred in self._osp[obj][sub]: 
                             yield (sub, retPred, obj)
                    # sub None None
                    else:
                        for retPred, objSet in self._spo[sub].items():
                            for retObj in objSet:
                                yield (sub, retPred, retObj)
            else:
                if pred != None:
                    # None pred obj
                    if obj != None:
                        for retSub in self._pos[pred][obj]:
                            yield (retSub, pred, obj)
                    # None pred None
                    else:
                        for retObj, subSet in self._pos[pred].items():
                            for retSub in subSet:
                                yield (retSub, pred, retObj)
                else:
                    # None None obj
                    if obj != None:
                        for retSub, predSet in self._osp[obj].items():
                            for retPred in predSet:
                                yield (retSub, retPred, obj)
                    # None None None
                    else:
                        for retSub, predSet in self._spo.items():
                            for retPred, objSet in predSet.items():
                                for retObj in objSet:
                                    yield (retSub, retPred, retObj)
        # KeyErrors occur if a query term wasn't in the index, 
        # so we yield nothing:
        except KeyError:
            pass        

Now, we’ll add a convenience method for querying a single value of a single triple:

    def value(self, sub=None, pred=None, obj=None):
         for retSub, retPred, retObj in self.triples((sub, pred, obj)):
             if sub is None: return retSub
             if pred is None: return retPred
             if obj is None: return retObj
             break
         return None

That’s all you need for a basic in-memory triplestore. Although you’ll see more sophisticated implementations throughout this book, this code is sufficient for storing and querying all kinds of semantic information. Because of the indexing, the performance will be perfectly acceptable for tens of thousands of triples.

Launch a Python prompt to try it out:

>>> from simplegraph import SimpleGraph
>>> movie_graph=SimpleGraph()
>>> movie_graph.add(('blade_runner','name','Blade Runner'))
>>> movie_graph.add(('blade_runner','directed_by','ridley_scott'))
>>> movie_graph.add(('ridley_scott','name','Ridley Scott'))
>>> list(movie_graph.triples(('blade_runner','directed_by',None)))
[('blade_runner', 'directed_by', 'ridley_scott')]
>>> list(movie_graph.triples((None,'name',None)))
[('ridley_scott', 'name', 'Ridley Scott'), ('blade_runner', 'name', 'Blade Runner')]
>>> movie_graph.value('blade_runner','directed_by',None)
ridley_scott

Places are particularly interesting because there is so much data about cities and countries available from various sources. Places also provide context for many things, such as news stories or biographical information, so it’s easy to imagine wanting to link other datasets into comprehensive information about locations. Places can be difficult to model, however, in part because of the wide variety of types of data available, and also because there’s no clear way to define them—a city’s name can refer to its metro area or just to its limits, and concepts like counties, states, parishes, neighborhoods, and provinces vary throughout the world.

Figure 2-7 shows a graph centered around “San Francisco”. You can see that San Francisco is in California, and California is in the United States. By structuring the places as a graphical hierarchy we avoid the complications of defining a city as being in a state, which is true in some places but not in others. We also have the option to add more information, such as neighborhoods, to the hierarchy if it becomes available. The figure shows various information about San Francisco through relationships to people and numbers and also the city’s geolocation (longitude and latitude), which is important for mapping applications and distance calculations.

Figure 2-7. An example of location data expressed as a graph

You can download a file containing triples about places from http://semprog.com/psw/chapter2/place_triples.txt. In a Python session, load it up and try some simple queries:

>>> from simplegraph import SimpleGraph
>>> placegraph=SimpleGraph()
>>> placegraph.loadfile("place_triples.txt")

This pattern returns everything we know about San Francisco:

>>> for t in placegraph.triples((None,"name","San Francisco")): 
...     print t
... 
(u'San_Francisco_California', 'name', 'San Francisco')
>>> for t in placegraph.triples(("San_Francisco_California",None,None)):
...     print t
... 
('San_Francisco_California', u'name', u'San Francisco')
('San_Francisco_California', u'inside', u'California')
('San_Francisco_California', u'longitude', u'-122.4183')
('San_Francisco_California', u'latitude', u'37.775')
('San_Francisco_California', u'mayor', u'Gavin Newsom')
('San_Francisco_California', u'population', u'744042')

This pattern shows all the mayors in the graph:

>>> for t in placegraph.triples((None,'mayor',None)):
...     print t
... 
(u'Aliso_Viejo_California', 'mayor', u'Donald Garcia')
(u'San_Francisco_California', 'mayor', u'Gavin Newsom')
(u'Hillsdale_Michigan', 'mayor', u'Michael Sessions')
(u'San_Francisco_California', 'mayor', u'John Shelley')
(u'Alameda_California', 'mayor', u'Lena Tam')
(u'Stuttgart_Germany', 'mayor', u'Manfred Rommel')
(u'Athens_Greece', 'mayor', u'Dora Bakoyannis')
(u'Portsmouth_New_Hampshire', 'mayor', u'John Blalock')
(u'Cleveland_Ohio', 'mayor', u'Newton D. Baker')
(u'Anaheim_California', 'mayor', u'Curt Pringle')
(u'San_Jose_California', 'mayor', u'Norman Mineta')
(u'Chicago_Illinois', 'mayor', u'Richard M. Daley')

...

We can also try something a little bit more sophisticated by using a loop to get all the cities in California and then getting their mayors:

>>> cal_cities=[p[0] for p in placegraph.triples((None,'inside','California'))]
>>> for city in cal_cities:
...     for t in placegraph.triples((city,'mayor',None)):
...        print t
... 
(u'Aliso_Viejo_California', 'mayor', u'William Phillips')
(u'Chula_Vista_California', 'mayor', u'Cheryl Cox')
(u'San_Jose_California', 'mayor', u'Norman Mineta')
(u'Fontana_California', 'mayor', u'Mark Nuaimi')
(u'Half_Moon_Bay_California', 'mayor', u'John Muller')
(u'Banning_California', 'mayor', u'Brenda Salas')
(u'Bakersfield_California', 'mayor', u'Harvey Hall')
(u'Adelanto_California', 'mayor', u'Charley B. Glasper')
(u'Fresno_California', 'mayor', u'Alan Autry')
(etc...)

This is a simple example of joining data in multiple steps. As mentioned previously, the next chapter will show you how to build a simple graph-query language to do all of this in one step.

Our next example is a fun one: celebrities. The wonderful thing about famous people is that other people are always talking about what they’re doing, particularly when what they’re doing is unexpected. For example, take a look at the graph around the ever-controversial Britney Spears, shown in Figure 2-8.

Figure 2-8. An example of celebrity data expressed as a graph

Even from this very small section of Ms. Spears’s life, it’s clear that there are lots of different things and, more importantly, lots of different types of things we say about celebrities. It’s almost comical to think that one could frontload the schema design of everything that a famous musician or actress might do in the future that would be of interest to people. This graph has already failed to include such things as favorite nightclubs, estranged children, angry head-shavings, and cosmetic surgery controversies.

We’ve created a sample file of triples about celebrities at http://semprog.com/psw/chapter2/celeb_triples.txt. Feel free to download this, load it into a graph, and try some fun examples:

>>> from simplegraph import SimpleGraph
>>> cg=SimpleGraph()
>>> cg.load('celeb_triples.csv')
>>> jt_relations=[t[0] for t in cg.triples((None,'with','Justin Timberlake'))]
>>> jt_relations # Justin Timberlake's relationships
[u'rel373', u'rel372', u'rel371', u'rel323', u'rel16', u'rel15', 
 u'rel14', u'rel13', u'rel12', u'rel11']
>>> for rel in jt_relations:
...     print [t[2] for t in cg.triples((rel,'with',None))]
... 
[u'Justin Timberlake', u'Jessica Biel']
[u'Justin Timberlake', u'Jenna Dewan']
[u'Justin Timberlake', u'Alyssa Milano']
[u'Justin Timberlake', u'Cameron Diaz']
[u'Justin Timberlake', u'Britney Spears']
[u'Justin Timberlake', u'Jessica Biel']
[u'Justin Timberlake', u'Jenna Dewan']
[u'Justin Timberlake', u'Alyssa Milano']
[u'Justin Timberlake', u'Cameron Diaz']
[u'Justin Timberlake', u'Britney Spears']
>>> bs_movies=[t[2] for t in cg.triples(('Britney Spears','starred_in',None))]
>>> bs_movies # Britney Spears' movies
[u'Longshot', u'Crossroads', u"Darrin's Dance Grooves", u'Austin Powers: Goldmember']
>> movie_stars=set()
>>> for t in cg.triples((None,'starred_in',None)):
...     movie_stars.add(t[0])
... 
>>> movie_stars # Anyone with a 'starred_in' assertion
set([u'Jenna Dewan', u'Cameron Diaz', u'Helena Bonham Carter', u'Stephan Jenkins', 
u'Penxe9lope Cruz', u'Julie Christie', u'Adam Duritz', u'Keira Knightley',
(etc...)

As an exercise, see if you can write Python code to answer some of these questions:

Hopefully you’re starting to get a sense of not only how easy it is to add new assertion types to a triplestore, but also how easy it is to try things with assertions created by someone else. You can start asking questions about a dataset from a single file of triples. The essence of semantic data is ease of extensibility and ease of sharing.

Lest you think that semantic data modeling is all about movies, entertainment, and celebrity rivalries, Figure 2-9 shows an example with a little more gravitas: data from the business world. This graph shows several different types of relationships, such as company locations, revenue, employees, directors, and political contributions.

Figure 2-9. An example of business data expressed as a graph

Obviously, a lot of information that is particular to these businesses could be added to this graph. The relationships shown here are actually quite generic and apply to most companies, and since companies can do so many different things, it’s easy to imagine more specific relationships that could be represented. We might, for example, want to know what investments Berkshire Hathaway has made, or what software products Microsoft has released. This just serves to highlight the importance of a flexible schema when dealing with complex domains such as business.

Again, we’ve provided a file of triples for you to download, at http://semprog.com/psw/chapter2/business_triples.csv. This is a big graph, with 36,000 assertions about 3,000 companies.

Here’s an example session:

>>> from simplegraph import SimpleGraph
>>> bg=SimpleGraph()
>>> bg.load('business_triples.csv')

>>> # Find all the investment banks
>>> ibanks=[t[0] for t in bg.triples((None,'industry','Investment Banking'))]
>>> ibanks
[u'COWN', u'GBL', u'CLMS', u'WDR', u'SCHW', u'LM', u'TWPG', u'PNSN', u'BSC', u'GS', 
 u'NITE', u'DHIL', u'JEF', u'BLK', u'TRAD', u'LEH', u'ITG', u'MKTX', u'LAB', u'MS', 
 u'MER', u'OXPS', u'SF']

>>> bank_contrib={}  # Contribution nodes from Investment banks
>>> for b in ibanks:
...     bank_contrib[b]=[t[0] for t in bg.triples((None,'contributor',b))]

>>> # Contributions from investment banks to politicians
>>> for b,contribs in bank_contrib.items():
...     for contrib in contribs:
...             print [t[2] for t in bg.triples((contrib,None,None))]

[u'BSC', u'30700.0', u'Orrin Hatch']
[u'BSC', u'168335.0', u'Hillary Rodham Clinton']
[u'BSC', u'5600.0', u'Christopher Shays']
[u'BSC', u'5000.0', u'Barney Frank']
(etc...)

>>> sw=[t[0] for t in bg.triples((None,'industry','Computer software'))]
>>> sw
[u'GOOG', u'ADBE', u'IBM',   # Google, Adobe, IBM

>>> # Count locations
>>> locations={}
>>> for company in sw:
...     for t in bg.triples((company,'headquarters',None)):
...             locations[t[2]]=locations.setdefault(t[2],0)+1

>>> # Locations with 3 or more software companies
>>> [loc for loc,c in locations.items() if c>=3]
[u'Austin_Texas', u'San_Jose_California', u'Cupertino_California', 
u'Seattle_Washington']

Notice that we’ve used ticker symbols as IDs, since they are guaranteed to be unique and short.

We hope this gives you a good idea of the many different types of data that can be expressed in triples, the different things you might ask of the data, and how easy it is to extend it. Now let’s move on to creating a better method of querying.