Re: Blending RDF graphs (was: Merging RDF graphs)

Hi Florian, very interesting problem. See my comments below.

On Mon, 2017-11-20 at 19:09 +0100, Florian Kleedorfer wrote:
> (Note: I changed the subject of this thread following Pat Hayes' 
> suggestion [1])
> 
> After some on-list and off-list discussions, the problem is becoming 
> clearer. I'll try to state it again, along with some ideas for a 
> solution. Any comments, criticism, and suggestions to collaborate are 
> highly welcome ;-)
> 
> # Blending:
> ## Definition
> Given two RDF graphs g1 and g2, blending refers to the pairwise renaming 
> of resources (blank nodes or URI nodes) r1 in g1 and r2 in g2 such that 
> one resource name (which may be r1, r2, or any other URI) is used 
> instead of r1 and r2. The nodes r1 and r2 are said to be blended (ideas 
> for a better term, anyone?). The resulting graphs are merged (avoiding 
> accidental blank node identification, see RDF 1.1 Semantics[2]). The 
> blending function b maps the input graphs to the set of all possible 
> output graphs.

I wonder why you do not frame the problem more in terms of description
logics. "Blending" as you have described it seems to be a much looser
(flexible?) way of finding the intersection of 2 classes. If the
provider has defined the classes of goods/services they can provide, and
the consumer defines the class(es) he wishes to buy, then before they
can do business they must find an instance of good or service that falls
in the intersection of those classes.

Suppose the provider defines class P, the consumer class C. Then any
transaction between them would be in the class defined by
intersectionOf(P C). If this class is unsatisfiable (cannot have any
members, for instance if P has :price = 20 and C has :price < 15), you
want an algorithm to define and rank ways in which the provider's and
consumer's class definitions could be modified to make the intersection
satisfiable. These "negotiating rules" (or "distance measurements") are
the interesting part of the problem.

I do not know if there are implementable solutions to these problems in
the description logics literature, but it might be worth a little
searching before building the graph-manipulation approach you have
outlined here. 

Regards,
--Paul
> 
> ## Discussion
> There are many ways to blend two graphs, and none of these ways are 
> deemed correct or incorrect.
> We require this operation to combine two data structures held by 
> mutually independent agents that have certain expectations about the 
> blending solution. These expectations divide the set of possible 
> outcomes at least in acceptable and unacceptable ones, possibly even in 
> a preference ranking. I'll try to formulate that as well in the 
> following.
> 
> 
> # Node blendability
> ## Rationale
> One way of constraining the result is to restrict which nodes can be 
> blended. So far, we have identified three types: variable nodes, 
> constant nodes, and unblendable nodes. Each node in an RDF graph has 
> exactly one of the three types. A variable node may be blended and its 
> name may be changed. A constant node may also be blended, but its name 
> is not allowed to change. An unblendable node must not be blended.
> 
> One may note that blending g1 and g2 is equivalent to merging them if no 
> variable nodes are present in either graph.
> 
> It is currently unclear how the constant/variable/unblendable property 
> should be expressed. My intuition is that in most practical use cases, 
> most nodes need to be unblendable (ontology/TBox resources, properties 
> in general), therefore it would be more economical to assume nodes to be 
> unblendable by default. Then, variable/constant nodes have to be 
> annotated as such explicitly.
> Maybe it would be an option to make definitions by URI prefix, so we can 
> define a complete vocabulary as unblendable with one statement. 
> (opinions on that?)
> 
> ## Definition
> Given two graphs g1 and g2, a blendability-aware blending function is a 
> blending function for g1 and g2 that only replaces resources that have 
> not been declared as constant with respect to blending. The latter is 
> done by specifying a triple "<graph> bl:containsConstant <resource> ." 
> or "<graph> bl:containsVariable <resource> ." in an additional graph 
> passed to the blendability-aware blending function. Such a graph is 
> called a 'blendability graph'.
> 
> 
> # Constraints on the blending solution:
> ## Rationale
> As explained earlier, there may be multiple parties that have 
> expectations for the blending solution. So far, we have talked about the 
> originators of the data. There may also be one or more intended 
> consumers of the data. Nothing prevents the expectations from being 
> mutually incompatible (meaning that there exists no graph that satisfies 
> them all) or that they are even unsatisfiable by themselves. It would of 
> course be beneficial if such cases could be detected automaticall, but 
> for now, let's just leave it at noting the possibility. Now, if the 
> information the agents provided, when considered in total, has spurious 
> or conflicting information, or if information is missing (taking their 
> respective expectations as a definition of what is acceptable), the 
> blending solution cannot meet the expectations. Nevertheless, it has to 
> be computed, in order to be able to take the next step and "repair" 
> (better word, please) one or both graphs and try again.
> 
> It would be nice to use constraints for the following goals during the 
> calculation of the blending solution:
> 1. pruning wholly unacceptable solutions
> 2. ranking unacceptable solutions by badness
> 3. ranking acceptable-looking, but incomplete solutions ("so far so 
> good")
> 
> Constraints should allow us to identify an acceptable result, or to 
> select the best result of a number of unacceptable ones, and report them 
> to users so that they can repair them.
> 
> However, if the expectations define an acceptable result, anything else, 
> however close, is unacceptable, and in the absence of acceptable results 
> we are left with unacceptable ones, some of which may be completely 
> bogus while others are almost acceptable. So, the three categories above 
> cannot be separated, and the best we can hope for is reasonable ranking 
> of unacceptable solutions.
> 
> For the conceptualization, we go with a simple SHACL-based approach. 
> Other systems (SPARQL, ShEx) are definitely possible as well.
> 
> ## Definition
> The constraints-aware blending function is a blending function for two 
> RDF graphs g1 and g2 and takes optional graph names s1,...,sN that 
> denote graphs which contain SHACL shapes constraining the result. Each 
> blending solution is validated using s1,...,sN; the result of the 
> function is a mapping of the blending solutions to their respective 
> SHACL validation results, indexed by shape graph name (s1,...,sN). A 
> blending solution is called accepted with respect to a constraints graph 
> s if it causes no SHACL validation results when validated against s. A 
> blending solution is called accepted if it is accepted with respect to 
> all specified shapes graphs.
> 
> ## Discussion
> The main issue in this step seems to be the pruning and ordering of 
> unacceptable results. Blending functions may choose to drop blending 
> solutions if they are deemed too bad - but where should they draw the 
> line and still report an unacceptable blending solution while dropping 
> another?
> 
> With respect to one shapes graph, we could define that validation result 
> graphs are ranked by maximum severity (1 sh:Violation is worse than 1000 
> sh:Warnings), and within those classes by number of validation results 
> (2 Violations and 1 Warnings is worse than 1 Violation and 1000 
> Warnings).
> 
> I'm suspecting that the validation results should allow us to prune at 
> least some bad blending solutions if their validation results are 
> supersets of other solutions' validation results: if solution A has 
> validation results (R1) and solution B has validation result (R1, R2) we 
> can say that solution B is a deterioration of solution A and should not 
> be reported.
> 
> In addition to constraint-based pruning and ranking, it is of course 
> possible to perform reasoning-based pruning and validate the blending 
> solution according to appropriate reasoning logics (RDFS, OWL, ...). 
> However, I am not sure as to the usefulness of this approach if no 
> solution is found that is consistent according to the logic.
> 
> 
> # Graph blending algorithms
> Let's assume for this section that we are blending two graphs g1 and g2, 
> and we know we have variable nodes var(g1) and constant nodes const(g1) 
> in g1, and var(g2) and const(g2) in g2.
> 
> ## Complete
> The complete algorithm consists of enumerating all possible solutions
> For each n in var(g1), there are the following solutions:
> * 1 solution in which n is not blended at all
> * 1 solution for each m in var(g2), in which n is blended with m
> * 1 solution for each m in const(g2), in which n is blended with m
> symmetrically the same is true for each n in var(g2).
> Removal of duplicate solutions yields the set of solutions.
> 
> ## Heuristic
> We may interpret blending as a heuristic search and apply an A*-like 
> algorithm to finding good results, assessing the distance to the goal by 
> evaluating the constraints, and the distance from the start by the 
> number of node blendings.
> 
> ## Knowledge-based
> Exploiting knowledge about the actual structures in g1 and g2, the 
> heuristic approach could be enhanced to apply more appropriate distance 
> estimates and select more promising paths first.
> 
> 
> 
> Links:
> 1. https://lists.w3.org/Archives/Public/semantic-web/2017Nov/0067.html
> 2. https://www.w3.org/TR/rdf11-mt/
> 
> 
> 
> 
> Am 2017-11-16 19:37, schrieb Florian Kleedorfer:
> > Hi,
> > 
> > As you may recall, I've asked this list about messaging/negotiating
> > using linked data[1], and it led me and my colleagues to a concept of
> > RDF-based agreements[2]. (Thanks again for your input!)
> > 
> > Now it's time for us to define how the negotiating parties come up
> > with the data (set of rdf triples) that they agree on.
> > 
> > One Idea we have is that both particpants (P1,P2) specify 'goals',
> > each consisting of a SHACL shapes graph and a data graph. Two goals
> > can be tested for compatibility by merging the two data graphs and
> > then testing if the resulting graph is valid given the shapes defined
> > by both goals. The problem we face with this approach is merging the
> > two data graphs. Consider the example in this gist:
> > 
> > https://gist.github.com/fkleedorfer/81b32e3235105a4a4743e9fa76ba9332
> > 
> > In that example, we would want to merge these two graphs:
> > 
> > ex1:p1g-data {
> >     ex1:ride1 a taxi:Ride .
> >     ex1:ride1 taxi:hasDriver ex1:p1 .
> >     ex1:ride1 taxi:hasPickupLocation ex1:pickup1;
> > }
> > 
> > and
> > 
> > ex2:p2g-data {
> >     ex2:myRide a taxi:Ride.
> >     ex2:myRide taxi:hasClient ex2:p2 .
> >     ex2:myRide taxi:hasPickupLocation ex2:myPickupLocation .
> >     ex2:myPickupLocation a s:GeoCoordinates ;
> >         s:latitude   "48.213814" ;
> >         s:longitude  "16.340870" .
> > }
> > 
> > We want that merge to happen in such a way that the shapes in
> > ex1:p1g-shapes and ex2:p2g-shapes can be evaluated, which will require
> > to merge some of the nodes. (In the example, we'll find out that a
> > taxi:hasPickupTime property is missing. One of the participants is
> > then to add that property, and the whole structure becomes valid
> > according to both goals' shapes.)
> > 
> > The question is how exactly to achieve that merge. Intuitively, the
> > result in this case should be
> > 
> >    :mergedNode1 a taxi:Ride .
> >    :mergedNode1 taxi:hasDriver ex1:p1 . # note: p1 links her own
> > identifier to the structure
> >    :mergedNode1 taxi:hasPickupLocation :mergedNode2;
> >    :mergedNode1 a taxi:Ride.
> >    :mergedNode1 taxi:hasClient ex2:p2 .
> >    :mergedNode1 taxi:hasPickupLocation :mergedNode2 .
> >    :mergedNode2 a s:GeoCoordinates ;
> >         s:latitude   "48.213814" ;
> >         s:longitude  "16.340870" .
> > 
> > and after removal of duplicate triples
> > 
> >    :mergedNode1 a taxi:Ride .
> >    :mergedNode1 taxi:hasDriver ex1:p1 .
> >    :mergedNode1 taxi:hasClient ex2:p2 .
> >    :mergedNode1 taxi:hasPickupLocation :mergedNode2 .
> >    :mergedNode2 a s:GeoCoordinates ;
> >         s:latitude   "48.213814" ;
> >         s:longitude  "16.340870" .
> > 
> > (I currently don't care about the URIs of the mergedNodes - just
> > something one can mint when doing the merge)
> > 
> > 
> > Do you have any hints on how to perform such a merge reliably, also
> > with more complex structures?
> > 
> > Thank you very much in advance!
> > 
> > Best regards,
> > Florian
> > 
> > 
> > Links:
> > 1. Negotiations discussion thread:
> > https://lists.w3.org/Archives/Public/semantic-web/2017Jul/0004.html
> > 2. Agreements paper: http://ceur-ws.org/Vol-1934/contribution-07.pdf
>

Received on Tuesday, 21 November 2017 02:52:20 UTC