tag:blogger.com,1999:blog-6819827262735986893.post3374459501658992527..comments2019-09-20T10:01:24.392+02:00Comments on Computer Science Blog: A Quick View on Compositionality in Graph Pattern MatchingUnknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6819827262735986893.post-48586111831527295822016-10-10T15:34:23.241+02:002016-10-10T15:34:23.241+02:00Thanks for clarifying about the search plans. I in...Thanks for clarifying about the search plans. I initially understood the compositionality result as a formal underpinning for one particular search plan - in your example, the span (A<-B) <- B -> (B->C), which did not seem to be most efficient. But I now see that by considering larger diagrams, with pushouts over pushouts, you can indeed represent arbitary search plans using this approach. Nice!Daniel StrĂ¼berhttps://www.blogger.com/profile/04427178855744819960noreply@blogger.comtag:blogger.com,1999:blog-6819827262735986893.post-50590971845384095732016-10-10T08:26:54.495+02:002016-10-10T08:26:54.495+02:00Graph pattern matching engines usually use some ki...Graph pattern matching engines usually use some kind of search plan. The decomposition of a pattern into a multiple subpatterns together with the order how these subpatterns are being matched is essentially the search plan. For example, consider a pattern of three nodes and two edges: A->B->C. Two possible decompositions of this pattern are (((A)->B)->C) and (A->(B->(C))). In the first decomposition we first match A, then B, then C. In the second, we do it the other way around. Both decompositions can be described as a diagram in GRAPH plus an order on how they are glued together to form the complete pattern. If the engine does not support traversing edges in backward direction, the first decomposition is much more efficient of course. However, if you have an attribute constraint on C and you can traverse in backward direction, the second decomposition can be more efficient. It is the task of the optimizer to find out which plan is the best.<br />Christian Krausehttps://www.blogger.com/profile/01663803042276257449noreply@blogger.comtag:blogger.com,1999:blog-6819827262735986893.post-52027225210894453952016-10-09T18:03:09.646+02:002016-10-09T18:03:09.646+02:00Hi Christian! Nice stuff, I like the clever proof ...Hi Christian! Nice stuff, I like the clever proof for the compositionality result.<br /><br />I wonder, though, if we can actually expect practical performance benefits from decomposing P into multiple sub-patterns. The reason for my doubt is that current graph pattern matching engines are less efficient at matching and combining multiple isolated patterns than at finding one large pattern: the latter problem seems inherently easier, since being able to navigate along the adjacent edges of partial solutions can help us to reduce the search space. I think you described this idea in your AMT2013 paper, in the explanation for the "LHS not connected" smell. But maybe you have some situations in mind where decomposing would indeed make things faster?Daniel StrĂ¼berhttps://www.blogger.com/profile/04427178855744819960noreply@blogger.com