Multicolumn indexes

[kris-brown]

Multicolumn indexes are useful in databases and also would be useful for ACSets. For example, a mapping table (i.e. a span A<-R->B, encoding a relation) is naturally indexed by its two outgoing morphisms to quickly check if (a,b) are related.

I'm not sure what needs to change in the underlying data structure, but an interface might look like this:

@present SchTest(FreeSchema) begin
 (A,B,C,R)::Ob
 f::Hom(R,A)
 g::Hom(R,B)
 h::Hom(R,C)
end

@acset_type Test(SchTest, index=[:h, (:f,:g)])

X = apex(terminal(Test))

incident(X, (1,1), (:f,:g)) # == [1]

[slwu89]

@kris-brown just want to note that I think this would be fantastically useful. In trying to use acsets to store data to parameterize practical optimization tasks, I have found myself wishing this feature existed.

I wonder also if it might work nicely with the ideas in AlgebraicJulia/Catlab.jl#844, certainly it would be very nice to index products this way.

[slwu89]

In addition to being able to do something similar to @kris-brown's proposed interface as above, I wonder if sequences of morphisms could also be supported in some future implementation of this feature. The following example is an example of a pattern that seems to come up very often in working with data in applied settings:

using ACSets

MySch = BasicSchema(
    [:X,:Y,:Rel],
    [(:proj_x,:Rel,:X),(:proj_y,:Rel,:Y)],
    [:NameType,:NumberType],
    [(:xname,:X,:NameType),(:yname,:Y,:NameType),(:cost,:Rel,:NumberType)]
)

@acset_type MyDataType(MySch, index=[:proj_x,:proj_y], unique_index=[:xname,:yname])

mydata = @acset MyDataType{Symbol,Float64} begin
    X = 4
    Y = 3
    xname = [:widget1,:widget2,:widget3,:widget4]
    yname = [:place1,:place2,:place3]
end

costs = rand(4,3)

add_parts!(
    mydata, :Rel, prod(size(costs)),
    proj_x = repeat(1:4,3),
    proj_y = vcat(map(i->fill(i,4),1:3)...),
    cost = vcat(costs...)
)

# a pattern that comes up very, very often
mydata[
    intersect(
        incident(mydata, :widget3, [:proj_x,:xname]),
        incident(mydata, :place2, [:proj_y,:yname])
    ),
    :cost
]

In addition, I believe it was previously discussed that at least in the case where the relation is a binary product, and where we want to be able to efficiently do this with caching, one would store a matrix to get these preimages, or an multidimensional array for the n-ary product. I'm not sure if the initial implementation of this feature also needs to consider the general case of a relation that may not be a (multi)product, where I guess one would store a sparse array.

I think that a prototype that nontheless would be useful immediately upon release would be to get the "non cached" version working that computes everything on the fly. This would also help work out the general methods and or structs that need to be implemented/modified for the overall case.