HTML Microdata document

This HTML5 document contains 48 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
atom	http://atomowl.org/ontologies/atomrdf#
n13	http://xmlns.com/foaf/spec/
foaf	http://xmlns.com/foaf/0.1/
n30	http://virtuoso.openlinksw.com/
n8	http://vos.openlinksw.com/dataspace/services/wiki/
opl	http://www.openlinksw.com/schema/attribution#
n2	http://vos.openlinksw.com/dataspace/owiki/wiki/VOS/
n4	http://vos.openlinksw.com/dataspace/owiki/wiki/VOS/VOSScalableInference/
n6	http://aws.amazon.com/ec2/
dc	http://purl.org/dc/elements/1.1/
n31	http://vos.openlinksw.com/dataspace/dav#
rdfs	http://www.w3.org/2000/01/rdf-schema#
n17	http://www.jisc.ac.uk/whatwedo/programmes/resourcediscovery/
n12	http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/
n9	http://rdfs.org/sioc/services#
sioct	http://rdfs.org/sioc/types#
n19	http://vos.openlinksw.com/dataspace/person/dav#
n24	http://vos.openlinksw.com/dataspace/owiki/wiki/
n18	http://jena.sourceforge.net/inference/
n23	http://
n14	http://www.cs.vu.nl/pmika/swc/
b3s	http://b3s.openlinksw.com/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
n16	http://www.linkedin.com/
n28	http://vos.openlinksw.com/dataspace/owiki#
n29	http://challenge.semanticweb.org/
xsdh	http://www.w3.org/2001/XMLSchema#
n7	http://vos.openlinksw.com/dataspace/%28NULL%29/wiki/VOS/
n10	http://linkeddata.org/
n26	http://vos.openlinksw.com/dataspace/person/owiki#
sioc	http://rdfs.org/sioc/ns#
n22	http://jena.hpl.hp.com/wiki/

Statements

Subject Item: n19:this
foaf:made: n2:VOSScalableInference

Subject Item: n31:this
sioc:creator_of: n2:VOSScalableInference

Subject Item: n8:item
n9:services_of: n2:VOSScalableInference

Subject Item: n28:this
sioc:creator_of: n2:VOSScalableInference

Subject Item: n24:VOS
sioc:container_of: n2:VOSScalableInference
atom:entry: n2:VOSScalableInference
atom:contains: n2:VOSScalableInference

Subject Item: n2:VOSScalableInference
rdf:type: sioct:Comment atom:Entry
dcterms:created: 2017-06-13T05:46:48.732831
dcterms:modified: 2019-09-20T10:23:24.885721
rdfs:label: VOSScalableInference
foaf:maker: n26:this n19:this
dc:title: VOSScalableInference
opl:isDescribedUsing: n4:sioc.rdf
sioc:has_creator: n28:this n31:this
sioc:content: %VOSWARNING% ---+ SPARQL and Scalable Inference on Demand By Orri Erling and Ivan Mikhailov ---++ Abstract This paper discusses integrating inference capabilities into OpenLink Virtuosos SPARQL implementation[1]. Our goal is to do inference at run time and on demand whenever possible, instead of materializing entailed facts ahead of demand. In an open web scenario, facts are liable to change, to be retracted, to be contradictory and to be malicious. Therefore, heavy investment in materializing consequences for a very large body of likely questionable facts is in our view not advisable. In the same spirit, we support partial query evaluation, so as to return possibly incomplete results within a fixed response time window. We present Virtuoso's run time implementation of <code>owl:sameAs</code>, inferred identity based on inverse functional properties, generic SPARQL extensions for arbitrary transitive subqueries and partial query evaluation. As future work, we suggest ways of generalizing these features for support of arbitrary backward and forward chaining rules. ---++ Introduction OpenLink Virtuoso[6] is a general purpose RDBMS with extensive SPARQL and RDF support. The background of the present work is hosting the entire Linked Open Data[5] cloud and various web crawls in Virtuoso's RDF store. From extensive experimentation with the Billion Triples Challenge data set[7][9], we find that many interesting uses of the data apply only to a fraction of the corpus and require run time intelligence, specifically for inferring identity and transitivity. Also, since the corpus is large, almost all queries use a combination of group by and order by, with occasional scalar subqueries. Returning individuals only, without ranking by frequency of occurrence or other aggregate properties does not generally yield a general view on the data set. Therefore we have extended SPARQL in all the ways required for ad hoc exploration and analysis of complex data without, as a general rule, relying on materialization of entailment as a preprocessing step. This includes addition of aggregation, grouping and subqueries[3] as well as the features discussed below. An often encountered counter-argument to publishing SPARQL end points is that the Web 2.0 world essentially never gives SQL access to their data, even though the data is generally stored in SQL databases. There are dual reasons for this: 1. data is proprietary, thus offering it for economical reuse by arbitrary third parties is not desired in terms of the business model and 2. SQL queries over large corpora, such as the millions of end user records and tens of millions of related rows of relational data in large Web 2.0 sites are potentially very expensive and constitute a very concrete denial of service threat. The Linked Open Data world has a slightly different starting point. The data is usually not proprietary and the schema/ontology is open, with a view on making data ad hoc joinable. Web 2.0 silos on the other hand optimize their data model for their relatively fixed workload and do not publish their schema. Thus, for supporting arbitrarily complex ad hoc queries on very large corpora within bounded response times, we introduce an anytime query approach that applies to all types of queries and always returns the most complete answer that could be arrived at within the resource constraints. Answers indicate whether they are complete and come with a summary of resource utilization. The examples below use the Yahoo and Falcon web crawls from the Billion Triples Challenge data set as sample data. The sample size is 135 Mtriples, 20 GB worth of used database pages. All the samples are run on a single 2.0 GHz 2x2core machine with 8G RAM. The software is Virtuoso 6 Cluster with the data in 4 partitions on the same machine. ---++ Transitivity OWL allows defining a property as transitive. Typically, for a situation where <code>{ X P Y }</code> and <code>{ Y P Z }</code> and <code>P</code> is transitive, the implied fact <code>{ X P Z }</code> is added to the corpus of data by a reasoner such as forward chaining engine of Jena's <code>GenericRuleReasoner</code> [12]. There are however many cases, such as for example social network data, where the count of transitive <code>foaf:knows</code> [11] steps is significant, as well as the reciprocality of the <code>foaf:knows</code> relation, etc. In such densely connected and constantly changing graphs, it is difficult to keep the implied facts up to date if all the consequences are materialized. Jena introduces a path extension for SPARQL[13]. This allows for example saying that <code>{<Alice> foaf:knows* ?x}</code>, meaning that <code>?x</code> is bound to the transitive closure of all people <code><Alice></code> knows. In Virtuoso, we take a more general approach and allow an arbitrary subquery to be made transitive. This has the advantage of being able to also retrieve properties of steps and to have complex conditions for what conditions define relatedness. In the social network example, we can for example return the graph where the <code>foaf:knows</code> triples come from. In a project management case, we could return the length of time associated with each transitive step and so forth. The general form of the transitive subquery is: <verbatim> { SELECT ?v1, ... ( FROM from-clause )* WHERE where-body } OPTION ( transitive t_in ( variables ) t_out ( variables ) (t_step ( variable ) AS alias)* (t_direction direction)? (t_min ( const-expn ))? (t_max ( const-expn ))? t_distinct? t_no_cycles? t_cycles_only? t_shortest_only? ) </verbatim> This may occur anywhere in the place of a triple pattern in a SPARQL query. The variables in the selection are designated as either input, output, or data. Conditions in the enclosing query must provide bindings for all input variables, or all output variables, or both. For example, we could define <code>sameAs</code> using this feature as follows: <verbatim> SELECT ?syn WHERE { { SELECT ?x ?syn WHERE { { ?x owl:sameAs ?syn } UNION { ?syn owl:sameAs ?x } } } OPTION ( transitive t_in (?x), t_out (?syn), t_distinct, t_min(0) ) } </verbatim> In order to use this to iterate over the <code>sameAs</code> closure of <code><Alice></code> we would write <verbatim> SELECT ?syn WHERE { { SELECT ?x ?syn WHERE { { ?x owl:sameAs ?syn } UNION { ?syn owl:sameAs ?x } } } OPTION ( transitive t_in (?x), t_out (?syn), t_distinct, t_min (0) ) FILTER ( ?x = <Alice> ) } </verbatim> In this case, we provide a binding for <code>?x</code> in the filter outside of the transitive subquery. The subquery therefore is made to run from in to out. The same effect would be accomplished if we bound <code>?syn</code> and <code>SELECT ?x</code>; the designations of in and out are arbitrary, and for transitive steps that can be evaluated equally well in both directions this makes no difference. To find out what graphs contain <code>owl:sameAs</code> for Dan York, we do <verbatim> SELECT ?g COUNT (*) WHERE { { SELECT ?x ?alias ?g WHERE { { GRAPH ?g { ?x owl:sameAs ?alias } } UNION { GRAPH ?g { ?alias owl:sameAs ?x } } } } OPTION ( transitive, t_in (?x), t_out (?alias), t_distinct, t_min (1) ) . FILTER ( ?x = <http://www.advogato.org/person/dyork/foaf.rdf#me> ) } GROUP BY ?g ORDER BY DESC 2 LIMIT 30 </verbatim> For each <code>sameAs</code> alias, this will produce the path from the source, one result row per step, with <code>?g</code> bound to the graph where the <code>sameAs</code> statement was found. Thus graphs with immediate <code>sameAs</code> get counted extra times, once for the immediate <code>sameAs</code> and once for each path containing this <code>sameAs</code> as an intermediate step. If we bind both <code>?x</code> and <code>?alias</code>, then we get a row of result if there is some combination of <code>owl:sameAs</code> that implies that <code>?x</code> and <code>?alias</code> are the same. We can use this feature to return information about how things are related. For example, using the social web data from the Billion Triples Challenge[8], we can write: <verbatim> SELECT ?o ?dist (( SELECT COUNT (*) WHERE { ?o foaf:knows ?xx } )) WHERE { { SELECT ?s ?o WHERE { ?s foaf:knows ?o } } OPTION ( transitive, t_distinct, t_in (?s), t_out (?o), t_min (1), t_max (4), t_step ('step_no') as ?dist ) } FILTER ( ?s = <http://www.w3.org/People/Berners-Lee/card#i> ) } ORDER BY ?dist DESC 3 LIMIT 50 </verbatim> This query takes all the people known by Tim Berners-Lee, to a depth between 1 and 4 applications of the subquery. It then sorts them by the distance and the descending count of connections of each found connection. This is equivalent to the default connections list shown by <nowiki>LinkedIn</nowiki>[14]. More interestingly, we can find the distinct paths between two points in a network: <verbatim> SELECT ?link ?g ?step ?path WHERE { { SELECT ?s ?o ?g WHERE { GRAPH ?g { ?s foaf:knows ?o } } } OPTION ( transitive, t_distinct, t_in (?s), t_out (?o), t_no_cycles, t_shortest_only, t_direction 3, t_step (?s) AS ?link, t_step ('path_id') AS ?path, t_step ('step_no') AS ?step ) FILTER ( ?s = <http://www.w3.org/People/Berners-Lee/card#i> ) FILTER ( ?o = <http://www.advogato.org/person/mparaz.rdf#me> ) } LIMIT 20 </verbatim> This query binds both the <code><nowiki>t_in</nowiki></code> and <code><nowiki>t_out</nowiki></code> variables. The <code>?g</code> is left as a free variable. Also, specifying <code>?s</code> and the system defined constants <code><nowiki>step_no</nowiki></code> and <code><nowiki>path_id</nowiki></code> as with <code><nowiki>t_step</nowiki></code>, we get for each transitive step a row of results with the intermediate binding of <code>?s</code>, the count of steps from the initial <code>?s</code> and a distinct identifier for the individual path, since there can be many distinct paths that link the <code>?s</code> and <code>?o</code> specified in the filter. For evaluating this query, we note that the <code>{ ?s foaf:knows ?o }</code> step can be evaluated equally well from <code>?s</code> to <code>?o</code> as the reverse, given the index scheme in use on the system. Thus the SPARQL/SQL compiler expands the query into two transitive subqueries, one starting from <code>?s</code> and the other from <code>?o</code>. The result is considered complete when the transitive closure being expanded breadth first from <code>?s</code> first intersects the transitive closure expanded breadth first from <code>?o</code> or vice versa. The <code><nowiki>t_shortest_only</nowiki></code> flag means that only paths of length equal to the shortest path found will be returned. The <code><nowiki>t_distinct</nowiki></code> switch means that not all possible paths to intermediate steps on the complete result paths are generated. After the set of shortest paths is found, the results are returned as a result set, one row per step in each path. ---++ Cost Model and Optimization When a query contains multiple transitive subqueries joined with each other, the optimal query plan is not readily obvious. The join order options are the same as in the case of any subqueries with distinct or aggregation. The presence of distinctness or aggregation means that the subquery cannot simply be inlined, with component patterns becoming direct component patterns of the enclosing group pattern. The optimizer must be able to distinguish between tree- and graph-shaped cases. If the step consists of a predicate with a generally asymmetric cardinality like <code>part-of</code>, where there are more subparts than super-parts, the compiler will naturally prefer the path from the leaves to the root to the path from root to leaves when determining whether two points are parent and child, for example. It turns out that the general cardinality statistics of the predicates making up the step provide reasonable grounds for such determinations. It is also possible to explicitly state that a transitive subquery must be evaluated from in to out, from out to in, or from both ends. ---++ owl:sameAs and Identity with Inverse Functional Properties While powerful, the general form of the transitive subquery is quite verbose and queries making extensive use of such easily become quite unreadable. For this reason we offer two built-in special cases of transitive queries: One for automatic run-time expansion of <code>owl:sameAs</code> and another for inferring identity between two subjects that share a value of an inverse functional property. The default way of dealing with identity is "smooshing" the supposedly same URIs together. This means that all the properties of all the allegedly-equal subjects are explicitly asserted for each. If the descriptions are identical, there is no new information but if not, we have duplication. Also, this process loses information since one no longer knows what was originally stated and what was copied. ---+++ Exceptions For example, we could think that subjects that have an equal <code>foaf:mbox</code> <code>sha1sum</code> are the same. This may be so, except when the SHA1 sum is the one for "<code>mailto://</code>". This is filled in by many FOAF generators for an empty email address field. Thus, for each distinct IFP, we allow declaring a set of values which will be considered null, i.e., sharing a null value with another subject will not imply equality. ---+++ Distinctness When multiple URIs mean the same entity, we can get problems with counting, distinct, and grouping. Thus, for better quality of results, we should, for purposes of <code>DISTINCT</code> or <code>GROUP BY</code>, consider two instances that are the same through <code>owl:sameAs</code> or through sharing of IFPs to be the same. Whenever bindings that come from patterns for which the <code>sameAs</code> of IFP inference is enabled are used in a <code>DISTINCT</code> or <code>GROUP BY</code>, the SPARQL compiler inserts an extra operation for canonicalizing the value. Since the values in question are IRIs, each with a unique internal ID, for convenience, we use the one with the smallest internal ID as the canonical IRI for these purposes. Using a subset of the Billion Triples data set, we get: <verbatim> SELECT COUNT (*) WHERE { ?x foaf:knows ?y } 1080205 DEFINE input:same-as "yes" SELECT COUNT (*) WHERE { { SELECT DISTINCT ?x ?y WHERE { ?x foaf:knows ?y } } } 1075161 </verbatim> ---+++ Examples Consider the graph: <verbatim> <john1> <name> "John" . <john2> <name> "John" . <john1> <address> "101 A street" . <john2> <address> "102 B street" . <john2> <knows> <mike> . <mike> <knows> <john1> . <mike> <knows> <john2> . </verbatim> We declare <code><name></code> to be inversely functional in the context below called ifps. <verbatim> DEFINE input:inference "ifps" SELECT * FROM <ifps> WHERE { <john1> <address> ?a } 101 A street 102 B street </verbatim> We get both addresses because <code><john1></code> and <code><john2></code> are the same by virtue of being called "John". <verbatim> DEFINE input:inference "ifps" SELECT DISTINCT ?x FROM <ifps> WHERE { <mike> <knows> ?x } </verbatim> We get only one because <code><john1></code> and <code><john2></code> are the same. ---++ Comparison With Materialization To provide a baseline, we materialized entailment of identity, where identity was defined as having a <code>foaf:name</code> in common and being both instances of <code>foaf:Person</code>. We used the Yahoo and Falcon data sets from the Billion Triples Challenge data set for the experiment. In the unmodified data, there were 3.32 Mtriples in any graph where the subject was in some graph a <code>foaf:Person</code> and had a <code>foaf:name</code> in some graph. This is defined by the below query. <verbatim> SELECT COUNT (*) WHERE { { SELECT DISTINCT ?person WHERE { ?person a foaf:Person } } FILTER ( bif:exists (( SELECT (1) WHERE { ?person foaf:name ?nn } )) ) ?person ?p ?o } </verbatim> We collapsed these all into one graph, choosing a canonical ID for all the <code>foaf:Person</code> subjects with the same <code>foaf:name</code> and gave this subject all the properties of all the synonyms. If the object was a member of this set of subjects, the reference was canonicalized. This gave us 2.17 Mtriples. Then we looked at leaving the identities be, but collapsing all the persons into a single graph and giving each of the subjects all the properties of all other subjects with the same <code>foaf:name</code> that also were <code>foaf:Persons</code>. This gave us 167.4 Mtriples. No reasoner was used; we did the operations in SQL so as to get the performance baseline without unknown overheads. Thus, if the set is static, normalizing identities pays and copying all to all is not profitable, as one would expect. Both approaches lose the provenance information since all are inserted into the same graph. Performing all these manipulations in SPARUL and SQL is error-prone and takes time. Inserting 167 Mtriples does not happen in interactive time even with a lot of hardware. On the test system (4 core Xeon), inserting just one key of the 167 Mtriples took 35m, for 77K inserts per second. On a larger system, we could have 100-200K full triples per second. This is still slow. And if we have tens of users doing the same thing at the same time, it is worse still. Actual throughput depends on many factors beyond the scope of this paper, but as a ballpark figure for such materialization, we are talking low hundreds of thousands of triples per second for a cluster of 2–4 commodity servers. If the logic for inferring identity is more complex than comparing IFP values, doing the inference as a preprocessing step makes sense. The preprocessing step can insert <code>owl:sameAs</code> triples that are then followed at run time. Inserting a synthetic IFP value shared by all subjects that are to be considered equivalent is a little more efficient since these do not have to be followed transitively, like <code>owl:sameAs</code>. Such materialization should be done in a separate graph so as not to contaminate the source data. Copying properties between IRIs considered equivalent is in general discouraged. ---++ Partial Query Answering The Linked Open Data community has recently seen discussion about the safety and wisdom of offering publicly available SPARQL end-points. Also, projects such as Fly Web[15] have experience with hosting end-points in Amazon EC2[16] and/or other cloud computing providers. The observation is that users, once they are given the option to compose queries, will compose complex queries that will take long or not complete at all. To this effect, Fly Web has installed diverse restrictions in front of their Jena-based back-end. Our approach is different. From DBpedia onwards, we have had public end-points with processing timeouts enforced by the back end database. This is also not perfect since many interesting questions will end in a timeout, which is completely uninformative as concerns the data itself or the query, and says nothing about the possibilities of further scoping the search. When scaling the Linked Data model, we have to take it as a given that the workload will be unexpected and that the query writers will often be unskilled in databases. Insofar as is possible, we wish to promote the forming of a culture of creative reuse of data. To this effect, even poorly formulated questions deserve an answer that is better than just a timeout. If a query produces a steady stream of results, interrupting it after a certain quota is simple. However, most interesting queries do not work in this way. They contain aggregation, sorting, maybe transitivity. When evaluating a query with a time limit in a cluster setup, all nodes monitor the time left for the query. When dealing with a potentially partial query to begin with, there is little point in transactionality; thus timeouts will occur approximately at the same time in all places, lock waiting not being involved. A read-committed query will never block, since it will see the before-image of any transactionally updated row. Thus, when having a partitioned count, for example, we expect all the partitions to time out around the same time and send a ready message with the timeout information to the cluster node coordinating the query. This timeout differs from a run time error in that it leaves the query state intact on all participating nodes. This allows the timeout handling to come fetch any accumulated aggregates. Thus, after activity has timed out, the cluster node coordinating the query can read through the execution plan and find the first/innermost aggregation step that was interrupted. No more information will be added to this aggregate state. Thus the query graph nodes that produce more solutions for the aggregate can be canceled. Instead the aggregated data can now be read and fed to the next stage; for example, the state of a <code>GROUP BY</code> can flow into an <code>ORDER BY</code> for sorting. Since this is a continuation of the query evaluation, the timeout is reset and some extra time is allocated for post-processing. If this is interrupted by a new timeout, then results that were unprocessed at this aggregation step are abandoned and processing moves to the output of the next outer aggregation. In this way, any query is guaranteed to finish in a fixed number of steps, each terminated by timeout or by natural completion. A transitive operation is processed like an aggregation. If a timeout interrupts it, no more results are generated and the results known to date are sent onward. The same applies to subqueries. Typically, if a subquery is at the end of the plan, like in the query counting the friends of friends and sorting by this count, we will be running the subquery concurrently for a large number of bindings. If this is interrupted, we have multiple partial counts that are then used as they are. To make this more concrete, let us consider a query that looks for people with a common interest which few people share and who do not know each other. <verbatim> SPARQL SELECT ?i ?cnt ?n1 ?n2 ?p1 ?p2 WHERE { { SELECT ?i COUNT (*) AS ?cnt WHERE { ?p foaf:interest ?i } GROUP BY ?i } FILTER ( ?cnt > 1 && ?cnt < 10 ) . ?p1 foaf:interest ?i . ?p2 foaf:interest ?i . FILTER ( ?p1 != ?p2 && !bif:exists (( SELECT (1) WHERE { ?p1 foaf:knows ?p2 } )) && !bif:exists (( SELECT (1) WHERE { ?p2 foaf:knows ?p1 } )) ) . ?p1 foaf:nick ?n1 . ?p2 foaf:nick ?n2 . } ORDER BY ?cnt LIMIT 10 </verbatim> The result set has an interest, the count of people having this interest, two person URIs, and their <code>foaf:nick</code>s. The first subquery counts the interested for each interest. The part after this finds two different people with the interest. The next filter checks that they do not know each other. Finally the <code>foaf:nick</code>s are retrieved. A sample run against the Yahoo and Falcon crawls gives us: <verbatim> http://www.livejournal.com/interests.bml?int=zui 2 zuicidal xcaddlecott_ nodeID://5104696 nodeID://0380826 http://www.livejournal.com/interests.bml?int=zui 2 xcaddlecott_ zuicidal nodeID://0380826 nodeID://5104696 http://www.livejournal.com/interests.bml?int=lt.+george 2 falxxx bitsofstephen nodeID://4697073 nodeID://3662566 ... </verbatim> The first thing to time out is the subquery counting the interests. Then the operations feeding the final <code>ORDER BY</code> time out. After this the <code>ORDER BY</code> returns what state is accumulated. Thus the query produces results in no more than 3 timeouts worth of time. As a point of comparison, the full evaluation on the Yahoo plus Falcons sample takes 165 seconds, whereas the above portion run takes 3. The resource summary line for the full query is <verbatim> 22.56MR rnd 1.102GR seq 10P disk 1.341GB / 102.7K messages </verbatim> (Numbers are explained below). We note that partial results always satisfy all the query criteria. The exception is that when an aggregate is used as a criterion, as in the above query, the aggregate value may be based on incomplete data. ---+++ Resource Utilization Metrics When a query is only partly evaluated, it is necessary to have an idea of how much work went into evaluating it and to have an idea of what percentage of the data set was accessed. Also, for purposes of billing for resource utilization, it is useful to be able to demonstrate the actual utilization. A query by query breakdown of resource utilization is also useful for distinguishing between having a heavily loaded system and a poorly optimized or overly complex query. To this effect, we gather the count of all single row random accesses, all sequentially accessed rows, all disk reads, and the byte and message count of cluster interconnect messages on behalf of a query. Whenever a partial result is returned, the result set ends with an error mentioning these metrics. These metrics are also programmatically available. For example: <verbatim> SPARQL SELECT COUNT (*) WHERE { ?s ?p ?o }; 1933805 *** Error S1TAT: [Virtuoso Driver][Virtuoso Server]RC...: Returning incomplete results, query interrupted by result timeout. Activity: 4R rnd 1.933MR seq 7.28KP disk 939B / 9 messages </verbatim> This is 4 random lookups, one per server, the count's worth of sequential fetches, 28000 pages read from disk, 9 messages between cluster nodes for a total of 939 bytes. ---++ Implications for Scalability As discussed in [4], the key requirement for scalability on clusters is optimization of message flow, request batching, and latency tolerance. All the work presented here is ipso facto optimized for these operating conditions. As seen in the previous section, distributed evaluation of partial queries differs only little from single process evaluation of same. For transitivity, especially when doing this with <code>owl:sameAs</code>, where no or few synonyms are expected per each binding but checking for these is required, we must process the <code>owl:sameAs</code> lookup for batches of several thousand bindings at a time. After enough distinct bindings of a variable are gathered, the lookups are dispatched to the partitions responsible for the data. Results are received and if synonyms are found, these are fed back into the process. The transitive closure is constructed once per distinct binding. The IFP identity inference is similar, except that it has a maximum depth of 1; i.e., all matches are found in the first lookup. ---++ Future Work We plan to generalize the Virtuoso transitivity support for evaluating arbitrary backward chaining rules. In such a situation, a step would produce two sorts of outputs: Bindings that are solutions for further processing in the query and lists of sub-goals from rule bodies whose heads matched the input bindings. Rule bodies can be thought of like SPARQL queries and they can be optimized as such, for example as concerns join order when matching physical data. When invoking a rule from a rule, one must pass enough state to allow the processing of the invoked rule to continue once the invoking rule produces bindings. This is no different from an implementation of Prolog. To maintain good performance on a cluster of machines, we will run with a large set of concurrent bindings. When matching patterns to partitioned data, messages will be batched together and join order optimized as in regular queries. ---++ Conclusions We believe the features discussed herein to be essential for widespread exploitation of linked data. By eliminating potentially hours-long preprocessing of IFPs and <code>sameAs</code> triples for identity, we allow the users to decide what sets of <code>sameAs</code> assertions they will trust or wish to see, changing this from query to query. Also, the sets of IFPs that will be considered as constituting identity are a matter of use case and opinion. Keeping data sets free of forward-chained extra is also important for database performance. Database performance most critically depends on having things in cache. A thousand random lookups can easily be made in the time of a single disk read. The likelihood of disk access increases if data is blown up to double size by forward chaining. A blow up from 1G to 2G is not significant on the desktop but for clusters, whether one needs 128G or 256G of RAM to have acceptable RAM-to-disk ratio already makes a significant difference in cost. Also, providing partial answers in guaranteed time goes a long way towards dissolving the fear of publishing data for open query. For users, it makes the data discovery process more interactive and hence more rewarding. Avoiding materialization of entailment in many cases also makes it possible to make queries on the spur of the moment, without having to design queries days in advance and then waiting for the needed materialization. Materialization is not excluded in the cases where it is really justified, though. If one knows what materialization is needed, then one already has an idea of the workload profile and is no longer in the realm of the pure ad hoc. Many of the queries discussed in this paper are live on the web in OpenLink's billion triples demo or its successors at [[http://b3s.openlinksw.com][http://b3s.openlinksw.com]]. We also plan to offer the software with pre-loaded data on Amazon EC2. We believe that the techniques discussed here will significantly contribute to low-cost, creative use of structured data on the web. Together with SPARQL federation, these will enable new types of information value-add services, a whole ecosystem of mesh-ups. ---++ References 1. Erling, O., Mikhailov, I.: RDF Support in the Virtuoso DBMS. Proceedings of the 1st Conference on Social Semantic Web (CSSW), 2007, Leipzig, Germany. LNI 113 GI 2007, ISBN 978-3-88579-207-9: 59-68 2. Erling, O., Mikhailov, I.: Integrating Open Sources and Relational Data with SPARQL. The Semantic Web: Research and Applications, 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, June 1-5, 2008, Proceedings. LNCS 5021 Springer 2008, ISBN 978-3-540-68233-2: 838-842 3. Erling, O., Mikhailov, I.: [[http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/VOSArticleBISPARQL2.pdf][Business Intelligence Extensions for SPARQL]]. [[http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/VOSArticleBISPARQL2.pdf][http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/VOSArticleBISPARQL2.pdf]] 4. Erling, O., Mikhailov, I.: [[http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/VOSArticleWebScaleRDF.pdf][Towards Web-Scale RDF]]. [[http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/VOSArticleWebScaleRDF.pdf][http://virtuoso.openlinksw.com/dataspace/dav/wiki/Main/VOSArticles/VOSArticleWebScaleRDF.pdf]] 5. Linked Data ? Connect Distributed Data across the Web. [[http://linkeddata.org/][http://linkeddata.org/]] 6. OpenLink Universal Integration Middleware ? Virtuoso Product Family. [[http://virtuoso.openlinksw.com/][http://virtuoso.openlinksw.com/]] 7. Semantic Web Challenge. [[http://challenge.semanticweb.org/][http://challenge.semanticweb.org/]] 8. Billion Triples dataset. [[http://www.cs.vu.nl/pmika/swc/btc.html][http://www.cs.vu.nl/pmika/swc/btc.html]] 9. OpenLink Billion Triple Demo queries. [[http://b3s.openlinksw.com/][http://b3s.openlinksw.com/]] 10. OpenLink Billion Triple Demo: Social Connections a la LinkedIn. [[http://b3s.openlinksw.com/search.vsp?q=6][http://b3s.openlinksw.com/search.vsp?q=6]] 11. Brickley, D., Miller, L.: FOAF Vocabulary Specification 0.91. [[http://xmlns.com/foaf/spec/20071002.html][http://xmlns.com/foaf/spec/20071002.html]] 12. Reynolds D.: Jena 2 Inference support. [[http://jena.sourceforge.net/inference/][http://jena.sourceforge.net/inference/]] 13. Seaborne A. (ed.): Jena SPARQL Extensions. [[http://jena.hpl.hp.com/wiki/SPARQL%20Extensions][http://jena.hpl.hp.com/wiki/SPARQL%20Extensions]] 14. LinkedIn ? Business-Oriented Social Networking. [[http://www.linkedin.com/static?key=company%20info][http://www.linkedin.com/static?key=company%20info]] 15. FlyWeb ? Linking Laboratory Image Data with Public Databases and Publication Repositories [[http://www.jisc.ac.uk/whatwedo/programmes/resourcediscovery/flyweb.aspx][http://www.jisc.ac.uk/whatwedo/programmes/resourcediscovery/flyweb.aspx]] 16. Amazon Elastic Compute Cloud (Amazon EC2). [[http://aws.amazon.com/ec2/][http://aws.amazon.com/ec2/]]
sioc:id: 1d6bc97180645456df7dc78b2845c116
sioc:link: n2:VOSScalableInference
sioc:has_container: n24:VOS
n9:has_services: n8:item
atom:title: VOSScalableInference
sioc:links_to: n6: n7:LinkedIn n10: b3s:search.vsp?q=6 n12:VOSArticleWebScaleRDF.pdf n13:20071002.html n14:btc.html b3s: n16:static?key=company%20info n17:flyweb.aspx n18: n22:SPARQL%20Extensions n7:FlyWeb n23:b3s.openlinksw.com n12:VOSArticleBISPARQL2.pdf n7:GenericRuleReasoner n2:OpenLink n29: n30:
atom:source: n24:VOS
atom:author: n19:this
atom:published: 2017-06-13T05:46:48Z
atom:updated: 2019-09-20T10:23:24Z
sioc:topic: n24:VOS