query for walking through a loop

[Marco Perone]

Hi,

I am experimenting with CQL and I'm trying to do the following:

I have two schemas

schema S = literal : T {

entities

// transitions

   Login

   AddProduct

Checkout

// links between transitions

LoginToAddProduct

AddProductToAddProduct

AddProductToCheckout

foreign_keys

// the links between transitions have foreign keys to transitions

l2aInput : LoginToAddProduct -> Login

l2aOutput : LoginToAddProduct -> AddProduct

a2aInput : AddProductToAddProduct -> AddProduct

a2aOutput : AddProductToAddProduct -> AddProduct

a2cInput : AddProductToCheckout -> AddProduct

a2cOutput : AddProductToCheckout -> Checkout

}

and

schema R = literal : T {

entities

// transitions

Start

Finish

// links between transitions

StartToFinish

foreign_keys

s2fInput : StartToFinish -> Start

s2fOutput : StartToFinish -> Finish

}

I'm trying to define a query to migrate data from S to R as follows

query Q = literal : S -> R {

entity Start -> {

from

l : Login

}

entity Finish -> {

from

c : Checkout

}

entity StartToFinish -> {

from

a : AddProduct

l2a : LoginToAddProduct

a2c : AddProductToCheckout

where

// actually this should be something like:

// there exist rows in `AddProductToAddProduct` which form a path between

// l2a and a2c

l2aOutput(l2a) = a

a2cInput(a2c) = a

foreign_keys

s2fInput -> {l -> l2aInput(l2a)}

s2fOutput -> {c -> a2cOutput(a2c)}

}

}

The problem is that in this way I'm selecting only the executions where the user added only one product before checking out. Is there a way to require that there is a path (of any possible length) of `AddProductToAddProduct` rows going from `l2a` to `a2c`?

Thanks

[David Spivak]

This is a case of transitive closure. Basically, you need to replace the relation

AddProductToAddProduct ---> AddProduct x AddProduct

with its transitive closure, which means add all paths.

This can be done in CQL by expressing transitive closure using constraints, and then using the chase. See the built-in example "Constraints". The constraint you want is:

constraints transitiveclosure = literal S // S is the name of your schema

forall tr1 tr2 : AddProductToAddProduct

where tr1.a2aOutput = tr2. a2aInput

->

exists path : AddProductToAddProduct

where path.a2aInput = tr1.Input  path.a2aOutput=tr2.Output

You then write

instance ReadyToQuery = chase transitiveclosure I // I is the name of your S-instance

--
You received this message because you are subscribed to the Google Groups "Categorical Data" group.
To unsubscribe from this group and stop receiving emails from it, send an email to categoricalda...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/categoricaldata/290b6dd3-13c6-4d3f-9866-feed7fbf3cb4%40googlegroups.com.

[Ryan Wisnesky]

Quick follow-up: 1) transitive closure is also inexpressible in relational algebra. 2) If you want a symmetric, transitive, reflexive closure, that can be done with Sigma (see the Simpsons Likes example).

> To view this discussion on the web visit https://groups.google.com/d/msgid/categoricaldata/CACcOXSHGPvLKZa3tOw291Ogo0OV%3DTVS0Fh5-nkDSNVaKRZxqLg%40mail.gmail.com.

[Marco Perone]

Thanks David and Ryan,

your response was really useful!

I actually needed a bit more than the transitive closure. I solved it as follows

constraints transitiveClosure = literal : S {

forall

  a2a1 a2a2 : AddProductToAddProduct

where

  a2aOutput(a2a1) = a2aInput(a2a2)

-> exists

  a2a : AddProductToAddProduct

where

  a2aInput(a2a) = a2aInput(a2a1)

  a2aOutput(a2a) = a2aOutput(a2a2)

}

constraints removeAddProductToAddProduct = literal : S {

forall

l2a : LoginToAddProduct

a1 a2 : AddProduct

a2a : AddProductToAddProduct

a2c : AddProductToCheckout

where

l2aOutput(l2a) = a1

a2aInput(a2a) = a1

a2aOutput(a2a) = a2

a2cInput(a2c) = a2

->

exists

l2a : LoginToAddProduct

a : AddProduct

a2c : AddProductToCheckout

where

l2aOutput(l2a) = a

a2cInput(a2c) = a

}

instance II = chase transitiveClosure I

instance III = chase removeAddProductToAddProduct II

because I needed to consider also the case where there were no `AddProductToAddProduct` rows.

This leads me to a small additional question. Is there a way to pass to `chase` multiple constraints to be applied sequentially, so that I could write something like

instance II = chase [transitiveClosure, removeAddProductToAddProduct] I

Thanks again

To view this discussion on the web visit https://groups.google.com/d/msgid/categoricaldata/4AEA6B4B-ED35-4218-B39C-3D98B86A9200%40gmail.com.

--

Marco Perone

@marcoshuttle

https://github.com/marcosh

http://marcosh.github.io/

[Ryan Wisnesky]

Yes, the constraints literals actually accept lists of "forall ... " expressions.

> To view this discussion on the web visit https://groups.google.com/d/msgid/categoricaldata/CAARDrK-f4fouWVWMtRGG0o8SwStYvfMdvYcgJcj3kCj0o6iWHw%40mail.gmail.com.

[David Spivak]

It sounds like you wanted the "poset closure": you want to add reflexivity and transitivity. As Ryan said, you can put both of these into a single constraint. 

To view this discussion on the web visit https://groups.google.com/d/msgid/categoricaldata/A7B382A8-24ED-4883-87D6-B7E3603F6D41%40gmail.com.