Eclipse Community Forums: VIATRA » Support for transitive closure maintenance via IncSCC

Help

Home

Home » Modeling » VIATRA » Support for transitive closure maintenance via IncSCC

Show: Today's Messages :: Show Polls :: Message Navigator

Support for transitive closure maintenance via IncSCC [message #1829784]

Fri, 10 July 2020 14:26

Hans van der Laan

Messages: 34
Registered: February 2020

Member

Hey,

I'm currently working on patterns which have cyclic recursion. Specifically, I have a pattern which determines reachability: given a person, what are all the rooms this person can reach given he/she has a certain security clearance.

Today, I came across an old paper which discusses the implementation of the computation of the transitive closure in Viatra [1]. Specifically, it explains how DRED and another technique called IncSCC work and how they stack up against each other.

As far as I can see, there is no mentation of an "IncSCC mode" in the documentation nor does there exist something akin to an "IncSCCReteBackendFactory". The only reference I can find is a class called "IncSCCAlg". Am I correct to assume the support for this method of incrementally computing the transitive closure is dropped? If so, out of interest, why has support been dropped? Can I still use it somehow to incrementally keep track of the SCC's?

- Hans

[1] Incremental Pattern Matching for the Efficient Computation of Transitive Closure?

Report message to a moderator

Re: Support for transitive closure maintenance via IncSCC [message #1829789 is a reply to message #1829784]

Fri, 10 July 2020 15:02

Gabor Bergmann

Messages: 36
Registered: July 2009

Member

Hi Hans,

if you use recursive patterns, their results will be maintained by DRed or DDF, whichever you select.
DRed is described here: https://www.eclipse.org/viatra/documentation/query-language.html#recursion
DDF is not currently documented, but you need to specifyTimelyReteBackendFactory .FAITHFUL_PARALLEL as the query backend factory when initializing the engine.

The transitive closure language element (find foobar*, find foobar+) is maintained by IncSCC, which is an algorithm specific to transitive closure (as opposed to recursion in general).
This language element must not be used if the called pattern is mutually recursive with the calling one; in that case please specify the transitive closure using recursive patterns.

Cheers,
Gábor

Report message to a moderator

Re: Support for transitive closure maintenance via IncSCC [message #1829924 is a reply to message #1829789]

Tue, 14 July 2020 08:21

Hans van der Laan

Messages: 34
Registered: February 2020

Member

Thanks for the reply! This again makes it much clearer!

Another quick question regarding the transitive closure: what would you recommend to do when dealing with relations which have more than 2 parameters but where all but 2 parameters are just "contextual information"?
Specifically, imagine a reachability pattern in which you capture reachability for a given context, e.g. zones in a building for a specific user. You would have pattern akin to :

 pattern Reachable(user: User, zone1: Zone, zone2: Zone)

Would you recommend in for cases like this to create a new java class representing a pair <Context,Element> and rewrite patterns such as the pattern above into:

 pattern ReachableAccess(user_and_zone1: Pair, user_and_zone: Pair)

Or would you recommend something else?

Report message to a moderator

Re: Support for transitive closure maintenance via IncSCC [message #1830260 is a reply to message #1829924]

Wed, 22 July 2020 09:41

Gabor Bergmann

Messages: 36
Registered: July 2009

Member

This would totally be possible to handle via the existing transitive closure algorithm, but unfortunately we have never gotten around to exposing such advanced transitive closure applications in the language.
I would suggest recursion in this case.

Report message to a moderator

Previous Topic:	Rete Visualizer Node Explanations
Next Topic:	Disadvantages of IMatchUpdateListener

Goto Forum:

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

]

Current Time: Tue Apr 16 20:44:47 GMT 2024

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter