Fair enough, the single comparison is indeed in O(size(algebra_expression)) but then doing it naively I would have to compare my tree with all the already existing ones in the cache. And that's not really an option I think. Unless there is some way of ordering the algebras so I could compare mine with like logarithm or so of the number of already existing algebras in the cache ?
But I guess there isn't any obvious way of doing so, so it seems that the option for me is to implement an OpVisitor and traverse the algebra tree modifying the subsequent nodes one by one, isn't ? Speaking of NodeIsomorphismMap. How do you make the bgp (triple ?s ?p ?o) isomorphic with the infinite number of patterns bgp (triple ?s' ?p' ?o') that are different only by variable names ? >>> So the question is whether we are missing something and there is >>> indeed a general way of obtaining the algebras that wouldn¹t be any >>> different for semantically identical queries (like those two above) >>> or we have to resort to some built in-house tweaks and tricks (e.g. >>> normalizing variable names, sorting algebra nodes on the same tree >>> level alphabetically etc. etc.) ? >> >> There might well be transformers doing some of this work (ISTR a >> variable reassignment mechanism) -- Andy would know best. I wrote a >> little piece on manipulating sparql [1] which shows a simple transformer. > > Yes. > > Every Op has an .equalTo method. This is not .equals(). > > Op.equalTo(Op other, NodeIsomorphismMap labelMap) > > > Op.equals is implemented as a call of .equalTo with a bNode mapping > isomorphism map. > > You could write your own NodeIsomorphismMap (inherit) and change it to > be variable name mapping as well. Then you would get the isomorphic > equality test you need to do this. > > If there is an isomorphism mapping, then the code will return true and > what is more, the map will give the association of names so you can > remap the variables in the result as well. > > The algorithm is linear in the size of the algebra expression because > expressions are trees so it's walking two trees to see if one can be > isomorphically mapped to the other. > > Andy > > ******************************************************************************** DISCLAIMER: This e-mail is confidential and should not be used by anyone who is not the original intended recipient. If you have received this e-mail in error please inform the sender and delete it from your mailbox or any other storage mechanism. Neither Macmillan Publishers Limited nor any of its agents accept liability for any statements made which are clearly the sender's own and not expressly made on behalf of Macmillan Publishers Limited or one of its agents. Please note that neither Macmillan Publishers Limited nor any of its agents accept any responsibility for viruses that may be contained in this e-mail or its attachments and it is your responsibility to scan the e-mail and attachments (if any). No contracts may be concluded on behalf of Macmillan Publishers Limited or its agents by means of e-mail communication. Macmillan Publishers Limited Registered in England and Wales with registered number 785998 Registered Office Brunel Road, Houndmills, Basingstoke RG21 6XS ********************************************************************************
