What a terrible word, smooshing... I have understood it to mean that when you have two names for one thing, you give each all the attributes of the other. This smooshes them together, makes them interchangeable.
This is complex, so I will begin with the point and the interested may read on for the details and implications. Starting with soon to be released version 6, Virtuoso allows you to say that two things, if they share a uniquely identifying property, are the same. Examples of uniquely identifying properties would be a book's ISBN number, or a person's social security plus full name. In relational language this is a unique key, and in RDF parlance, an inverse functional property.
In most systems, such problems are dealt with as a preprocessing step before querying. For example, all the items that are considered the same will get the same properties or at load time all identifiers will be normalized according to some application rules. This is good if the rules are clear and understood. This is so in closed situations, where things tend to have standard identifiers to begin with. But on the open web this is not so clear cut.
In this post, we show how to do these things ad hoc, without materializing anything. At the end, we also show how to materialize identity and what the consequences of this are with open web data. We use real live web crawls from the Billion Triples Challenge data set.
On the linked data web, there are independently arising descriptions of the same thing and thus arises the need to smoosh, if these are to be somehow integrated. But this is only the beginning of the problems.
To address these, we have added the option of specifying that some property will be considered inversely functional in a query. This is done at run time and the property does not really have to be inversely functional in the pure sense. foaf:name will do for an example. This simply means that for purposes of the query concerned, two subjects which have at least one foaf:name in common are considered the same. In this way, we can join between FOAF files. With the same database, a query about music preferences might consider having the same name as "same enough," but a query about criminal prosecution would obviously need to be more precise about sameness.
Our ontology is defined like this:
-- Populate a named graph with the triples you want to use in query time inferencing
ttlp ( '
@prefix foaf: <xmlns="http" xmlns.com="xmlns.com" foaf="foaf">
</>
@prefix owl: <xmlns="http" www.w3.org="www.w3.org" owl="owl">
</>
foaf:mbox_sha1sum a owl:InverseFunctionalProperty .
foaf:name a owl:InverseFunctionalProperty .
',
'xx',
'b3sifp'
);
-- Declare that the graph contains an ontology for use in query time inferencing
rdfs_rule_set ( 'http://example.com/rules/b3sifp#',
'b3sifp'
);
Then use it:
sparql
DEFINE input:inference "http://example.com/rules/b3sifp#"
SELECT DISTINCT ?k ?f1 ?f2
WHERE { ?k foaf:name ?n .
?n bif:contains "'Kjetil Kjernsmo'" .
?k foaf:knows ?f1 .
?f1 foaf:knows ?f2
};
VARCHAR VARCHAR VARCHAR
______________________________________ _______________________________________________ ______________________________
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/dajobe
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/net_twitter
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/amyvdh
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/pom
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/mattb
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/davorg
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/distobj
http://www.kjetil.kjernsmo.net/foaf#me http://norman.walsh.name/knows/who/robin-berjon http://twitter.com/perigrin
....
Without the inference, we get no matches. This is because the data in question has one graph per FOAF file, and blank nodes for persons. No graph references any person outside the ones in the graph. So if somebody is mentioned as known, then without the inference there is no way to get to what that person's FOAF file says, since the same individual will be a different blank node there. The declaration in the context named b3sifp just means that all things with a matching foaf:name or foaf:mbox_sha1sum are the same.
Sameness means that two are the same for purposes of DISTINCT or GROUP BY, and if two are the same, then both have the UNION of all of the properties of both.
If this were a naive smoosh, then the individuals would have all the same properties but would not be the same for DISTINCT.
If we have complex application rules for determining whether individuals are the same, then one can materialize owl:sameAs triples and keep them in a separate graph. In this way, the original data is not contaminated and the materialized volume stays reasonable — nothing like the blow-up of duplicating properties across instances.
The pro-smoosh argument is that if every duplicate makes exactly the same statements, then there is no great blow-up. Best and worst cases will always depend on the data. In rough terms, the more ad hoc the use, the less desirable the materialization. If the usage pattern is really set, then a relational-style application-specific representation with identity resolved at load time will perform best. We can do that too, but so can others.
The principal point is about agility as concerns the inference. Run time is more agile than materialization, and if the rules change or if different users have different needs, then materialization runs into trouble. When talking web scale, having multiple users is a given; it is very uneconomical to give everybody their own copy, and the likelihood of a user accessing any significant part of the corpus is minimal. Even if the queries were not limited, the user would typically not wait for the answer of a query doing a scan or aggregation over 1 billion blog posts or something of the sort. So queries will typically be selective. Selective means that they do not access all of the data, hence do not benefit from ready-made materialization for things they do not even look at.
The exception is corpus-wide statistics queries. But these will not be done in interactive time anyway, and will not be done very often. Plus, since these do not typically run all in memory, these are disk bound. And when things are disk bound, size matters. Reading extra entailment on the way is just a performance penalty.
Enough talk. Time for an experiment. We take the Yahoo and Falcon web crawls from the Billion Triples Challenge set, and do two things with the FOAF data in them:
- Resolve identity at insert time. We remove duplicate person URIs, and give the single URI all the properties of all the duplicate URIs. We expect these to be most often repeats. If a person references another person, we normalize this reference to go to the single URI of the referenced person.
- Give every duplicate URI of a person all the properties of all the duplicates. If these are the same value, the data should not get much bigger, or so we think.
For the experiment, we will consider two people the same if they have the same foaf:name and are both instances of foaf:Person. This gets some extra hits but should not be statistically significant.
The following is a commented SQL script performing the smoosh. We play with internal IDs of things, thus some of these operations cannot be done in SPARQL alone. We use SPARQL where possible for readability. As the documentation states, iri_to_id converts from the qualified name of an IRI to its ID and id_to_iri does the reverse.
We count the triples that enter into the smoosh:
-- the name is an existence because else we'd get several times more due to
-- the names occurring in many graphs
sparql
SELECT COUNT(*)
WHERE { { SELECT DISTINCT ?person
WHERE { ?person a foaf:Person }
} .
FILTER ( bif:exists ( SELECT (1)
WHERE { ?person foaf:name ?nn }
)
) .
?person ?p ?o
};
-- We get 3284674
We make a few tables for intermediate results.
-- For each distinct name, gather the properties and objects from
-- all subjects with this name
CREATE TABLE name_prop
( np_name ANY,
np_p IRI_ID_8,
np_o ANY,
PRIMARY KEY ( np_name,
np_p,
np_o
)
);
ALTER INDEX name_prop
ON name_prop
PARTITION ( np_name VARCHAR (-1, 0hexffff) );
-- Map from name to canonical IRI used for the name
CREATE TABLE name_iri ( ni_name ANY PRIMARY KEY,
ni_s IRI_ID_8
);
ALTER INDEX name_iri
ON name_iri
PARTITION ( ni_name VARCHAR (-1, 0hexffff) );
-- Map from person IRI to canonical person IRI
CREATE TABLE pref_iri
( i IRI_ID_8,
pref IRI_ID_8,
PRIMARY KEY ( i )
);
ALTER INDEX pref_iri
ON pref_iri
PARTITION ( i INT (0hexffff00) );
-- a table for the materialization where all aliases get all properties of every other
CREATE TABLE smoosh_ct
( s IRI_ID_8,
p IRI_ID_8,
o ANY,
PRIMARY KEY ( s,
p,
o
)
);
ALTER INDEX smoosh_ct
ON smoosh_ct
PARTITION ( s INT (0hexffff00) );
-- disable transaction log and enable row auto-commit. This is necessary, otherwise
-- bulk operations are done transactionally and they will run out of rollback space.
LOG_ENABLE (2);
-- Gather all the properties of all persons with a name under that name.
-- INSERT SOFT means that duplicates are ignored
INSERT SOFT name_prop
SELECT "n", "p", "o"
FROM ( sparql
DEFINE output:valmode "LONG"
SELECT ?n ?p ?o
WHERE { ?x a foaf:Person .
?x foaf:name ?n .
?x ?p ?o
}
) xx ;
-- Now choose for each name the canonical IRI
INSERT INTO name_iri
SELECT np_name,
( SELECT MIN (s)
FROM rdf_quad
WHERE o = np_name
AND p = IRI_TO_ID ('http://xmlns.com/foaf/0.1/name')
) AS mini
FROM name_prop
WHERE np_p = IRI_TO_ID ('http://xmlns.com/foaf/0.1/name') ;
-- For each person IRI, map to the canonical IRI of that person
INSERT SOFT pref_iri (i, pref)
SELECT s,
ni_s
FROM name_iri,
rdf_quad
WHERE o = ni_name
AND p = IRI_TO_ID ('http://xmlns.com/foaf/0.1/name') ;
-- Make a graph where all persons have one iri with all the properties of all aliases
-- and where person-to-person refs are canonicalized
INSERT SOFT rdf_quad (g,s,p,o)
SELECT IRI_TO_ID ('psmoosh'),
ni_s,
np_p,
COALESCE ( ( SELECT pref
FROM pref_iri
WHERE i = np_o
),
np_o
)
FROM name_prop,
name_iri
WHERE ni_name = np_name
OPTION ( loop, quietcast ) ;
-- A little explanation: The properties of names are copied into rdf_quad with the name
-- replaced with its canonical IRI. If the object has a canonical IRI, this is used as
-- the object, else the object is unmodified. This is the COALESCE with the sub-query.
-- This takes a little time. To check on the progress, take another connection to the
-- server and do
STATUS ('cluster');
-- It will return something like
-- Cluster 4 nodes, 35 s. 108 m/s 1001 KB/s 75% cpu 186% read 12% clw threads 5r 0w 0i
-- buffers 549481 253929 d 8 w 0 pfs
-- Now finalize the state; this makes it permanent. Else the work will be lost on server
-- failure, since there was no transaction log
CL_EXEC ('checkpoint');
-- See what we got
sparql
SELECT COUNT (*)
FROM <psmoosh>
WHERE {?s ?p ?o};
-- This is 2253102
-- Now make the copy where all have the properties of all synonyms. This takes so much
-- space we do not insert it as RDF quads, but make a special table for it so that we can
-- run some statistics. This saves time.
INSERT SOFT smoosh_ct (s, p, o)
SELECT s, np_p, np_o
FROM name_prop,
rdf_quad
WHERE o = np_name
AND p = IRI_TO_ID ('http://xmlns.com/foaf/0.1/name') ;
-- as above, INSERT SOFT so as to ignore duplicates
SELECT COUNT (*)
FROM smoosh_ct;
-- This is 167360324
-- Find out where the bloat comes from
SELECT TOP 20 COUNT (*),
ID_TO_IRI (p)
FROM smoosh_ct
GROUP BY p
ORDER BY 1 DESC;
The results are:
54728777 http://www.w3.org/2002/07/owl#sameAs
48543153 http://xmlns.com/foaf/0.1/knows
13930234 http://www.w3.org/2000/01/rdf-schema#seeAlso
12268512 http://xmlns.com/foaf/0.1/interest
11415867 http://xmlns.com/foaf/0.1/nick
6683963 http://xmlns.com/foaf/0.1/weblog
6650093 http://xmlns.com/foaf/0.1/depiction
4231946 http://xmlns.com/foaf/0.1/mbox_sha1sum
4129629 http://xmlns.com/foaf/0.1/homepage
1776555 http://xmlns.com/foaf/0.1/holdsAccount
1219525 http://xmlns.com/foaf/0.1/based_near
305522 http://www.w3.org/1999/02/22-rdf-syntax-ns#type
274965 http://xmlns.com/foaf/0.1/name
155131 http://xmlns.com/foaf/0.1/dateOfBirth
153001 http://xmlns.com/foaf/0.1/img
111130 http://www.w3.org/2001/vcard-rdf/3.0#ADR
52930 http://xmlns.com/foaf/0.1/gender
48517 http://www.w3.org/2004/02/skos/core#subject
45697 http://www.w3.org/2000/01/rdf-schema#label
44860 http://purl.org/vocab/bio/0.1/olb
Now compare with the predicate distribution of the smoosh with identities canonicalized
sparql
SELECT COUNT (*) ?p
FROM <psmoosh>
WHERE { ?s ?p ?o }
GROUP BY ?p
ORDER BY 1 DESC
LIMIT 20;
Results are:
748311 http://xmlns.com/foaf/0.1/knows
548391 http://xmlns.com/foaf/0.1/interest
140531 http://www.w3.org/2000/01/rdf-schema#seeAlso
105273 http://www.w3.org/1999/02/22-rdf-syntax-ns#type
78497 http://xmlns.com/foaf/0.1/name
48099 http://www.w3.org/2004/02/skos/core#subject
45179 http://xmlns.com/foaf/0.1/depiction
40229 http://www.w3.org/2000/01/rdf-schema#comment
38272 http://www.w3.org/2000/01/rdf-schema#label
37378 http://xmlns.com/foaf/0.1/nick
37186 http://dbpedia.org/property/abstract
34003 http://xmlns.com/foaf/0.1/img
26182 http://xmlns.com/foaf/0.1/homepage
23795 http://www.w3.org/2002/07/owl#sameAs
17651 http://xmlns.com/foaf/0.1/mbox_sha1sum
17430 http://xmlns.com/foaf/0.1/dateOfBirth
15586 http://xmlns.com/foaf/0.1/page
12869 http://dbpedia.org/property/reference
12497 http://xmlns.com/foaf/0.1/weblog
12329 http://blogs.yandex.ru/schema/foaf/school
We can drop the owl:sameAs triples from the count, so the bloat is a bit less by that but it still is tens of times larger than the canonicalized copy or the initial state.
Now, when we try using the psmoosh graph, we still get different results from the results with the original data. This is because foaf:knows relations to things with no foaf:name are not represented in the smoosh. The exist:
sparql
SELECT COUNT (*)
WHERE { ?s foaf:knows ?thing .
FILTER ( !bif:exists ( SELECT (1)
WHERE { ?thing foaf:name ?nn }
)
)
};
-- 1393940
So the smoosh graph is not an accurate rendition of the social network. It would have to be smooshed further to be that, since the data in the sample is quite irregular. But we do not go that far here.
Finally, we calculate the smoosh blow up factors. We do not include owl:sameAs triples in the counts.
select (167360324 - 54728777) / 3284674.0;
34.290022997716059
select 2229307 / 3284674.0;
= 0.678699621332284
So, to get a smoosh that is not really the equivalent of the original, either multiply the original triple count by 34 or 0.68, depending on whether synonyms are collapsed or not.
Making the smooshes does not take very long, some minutes for the small one. Inserting the big one would be longer, a couple of hours maybe. It was 33 minutes for filling the smoosh_ct table. The metrics were not with optimal tuning so the performance numbers just serve to show that smooshing takes time. Probably more time than allowable in an interactive situation, no matter how the process is optimized.