001/**
002 * Copyright (C) 2007 - 2016, Jens Lehmann
003 *
004 * This file is part of DL-Learner.
005 *
006 * DL-Learner is free software; you can redistribute it and/or modify
007 * it under the terms of the GNU General Public License as published by
008 * the Free Software Foundation; either version 3 of the License, or
009 * (at your option) any later version.
010 *
011 * DL-Learner is distributed in the hope that it will be useful,
012 * but WITHOUT ANY WARRANTY; without even the implied warranty of
013 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
014 * GNU General Public License for more details.
015 *
016 * You should have received a copy of the GNU General Public License
017 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
018 */
019package org.dllearner.algorithms.qtl.operations;
020
021import java.util.ArrayList;
022import java.util.Collections;
023import java.util.Comparator;
024import java.util.HashMap;
025import java.util.HashSet;
026import java.util.Iterator;
027import java.util.LinkedList;
028import java.util.List;
029import java.util.Map;
030import java.util.Map.Entry;
031import java.util.Set;
032import java.util.SortedMap;
033import java.util.SortedSet;
034import java.util.TreeMap;
035import java.util.TreeSet;
036import java.util.concurrent.TimeUnit;
037
038import javax.xml.ws.http.HTTPException;
039
040import org.apache.jena.graph.NodeFactory;
041import org.aksw.jena_sparql_api.cache.core.QueryExecutionFactoryCacheEx;
042import org.aksw.jena_sparql_api.cache.extra.CacheFrontend;
043import org.aksw.jena_sparql_api.cache.h2.CacheUtilsH2;
044import org.aksw.jena_sparql_api.http.QueryExecutionFactoryHttp;
045import org.aksw.jena_sparql_api.model.QueryExecutionFactoryModel;
046import org.apache.log4j.Logger;
047import org.dllearner.algorithms.qtl.datastructures.QueryTree;
048import org.dllearner.algorithms.qtl.datastructures.impl.GeneralisedQueryTree;
049import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeChange;
050import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeChange.ChangeType;
051import org.dllearner.algorithms.qtl.datastructures.impl.QueryTreeImpl;
052import org.dllearner.algorithms.qtl.exception.TimeOutException;
053import org.dllearner.algorithms.qtl.util.SPARQLEndpointEx;
054import org.dllearner.algorithms.qtl.util.TreeHelper;
055import org.dllearner.kb.sparql.SparqlEndpoint;
056
057import org.apache.jena.graph.Node;
058import org.apache.jena.graph.Triple;
059import org.apache.jena.query.Query;
060import org.apache.jena.query.QueryExecution;
061import org.apache.jena.query.QueryExecutionFactory;
062import org.apache.jena.query.QueryFactory;
063import org.apache.jena.query.QuerySolution;
064import org.apache.jena.query.ResultSet;
065import org.apache.jena.rdf.model.Model;
066import org.apache.jena.sparql.engine.http.QueryEngineHTTP;
067import org.apache.jena.sparql.expr.E_Equals;
068import org.apache.jena.sparql.expr.E_LogicalNot;
069import org.apache.jena.sparql.expr.ExprVar;
070import org.apache.jena.sparql.expr.nodevalue.NodeValueNode;
071import org.apache.jena.sparql.syntax.Element;
072import org.apache.jena.sparql.syntax.ElementFilter;
073import org.apache.jena.sparql.syntax.ElementGroup;
074import org.apache.jena.sparql.syntax.ElementOptional;
075import org.apache.jena.sparql.syntax.ElementTriplesBlock;
076import org.apache.jena.vocabulary.RDF;
077import com.jamonapi.Monitor;
078import com.jamonapi.MonitorFactory;
079
080public class NBR<N> {
081        
082        private boolean generalizeSortedByNegatives = false;
083        
084        private volatile boolean stop = false;
085        private boolean isRunning;
086        private int maxExecutionTimeInSeconds = 100;
087        private long startTime;
088        
089        private SparqlEndpoint endpoint;
090        private Model model;
091        private org.aksw.jena_sparql_api.core.QueryExecutionFactory qef;
092        
093        private String query;
094        private int limit;
095        
096        private int nodeId;
097        private QueryTree<N> lgg;
098        private QueryTree<N> postLGG;
099        private List<QueryTree<N>> negTrees;
100        private List<Integer> determiningNodeIds;
101        
102        private List<List<QueryTreeChange>> noSequences;
103        private List<QueryTreeChange> lastSequence;
104        private int negExamplesCount = -1;
105        private Set<String> lggInstances;
106        
107        private LastQueryTreeChangeComparator comparator = new LastQueryTreeChangeComparator();
108        
109        private Monitor mon = MonitorFactory.getTimeMonitor("NBR");
110        
111        private static final Logger logger = Logger.getLogger(NBR.class);
112        
113        public NBR(SparqlEndpoint endpoint){
114                this(endpoint, null);
115        }
116        
117        public NBR(SparqlEndpoint endpoint, String cacheDirectory){
118                this.endpoint = endpoint;
119                
120                noSequences = new ArrayList<>();
121                
122                qef = new QueryExecutionFactoryHttp(endpoint.getURL().toString(), endpoint.getDefaultGraphURIs());
123                if(cacheDirectory != null){
124                                long timeToLive = TimeUnit.DAYS.toMillis(30);
125                                CacheFrontend cacheFrontend = CacheUtilsH2.createCacheFrontend(cacheDirectory, true, timeToLive);
126                                qef = new QueryExecutionFactoryCacheEx(qef, cacheFrontend);
127                }
128        }
129        
130        public NBR(Model model){
131                this.model = model;
132                
133                noSequences = new ArrayList<>();
134                
135                qef = new QueryExecutionFactoryModel(model);
136        }
137        
138        public void setMaxExecutionTimeInSeconds(int maxExecutionTimeInSeconds){
139                this.maxExecutionTimeInSeconds = maxExecutionTimeInSeconds;
140        }
141        
142        
143        private Map<QueryTree<N>, List<Integer>> createMatrix(QueryTree<N> tree, List<QueryTree<N>> negTrees){
144                Map<QueryTree<N>, List<Integer>> matrix = new HashMap<>();
145                for(int i = 0; i < negTrees.size(); i++){
146                        checkTree(matrix, tree, negTrees.get(i), i);
147                }
148                return matrix;
149        }
150        
151        private List<Integer> getDeterminingNodeIds(QueryTree<N> lgg, List<QueryTree<N>> trees){
152                List<Integer> nodeIds = new ArrayList<>();
153                
154                boolean parentIsResource = false;
155                boolean childIsResource = false;
156                for(QueryTree<N> child : lgg.getChildren()){
157                        parentIsResource = !child.getParent().getUserObject().equals("?");
158                        childIsResource = !child.getUserObject().equals("?");
159                        if(parentIsResource && childIsResource && hasAlwaysSameParent(child, trees)){
160                                nodeIds.add(child.getId());
161                        }
162                        if(!child.isLeaf()){
163                                nodeIds.addAll(getDeterminingNodeIds(child, trees));
164                        }
165                }
166                
167                return nodeIds;
168        }
169        
170        public String getQuery(){
171                return query;
172        }
173        
174        private List<QueryTree<N>> getLeafsOrderedByRowSum(QueryTree<N> tree, Map<QueryTree<N>, List<Integer>> matrix){
175                List<QueryTree<N>> leafs = new ArrayList<>();
176                
177                SortedMap<Integer, List<QueryTree<N>>> map = new TreeMap<>();
178                int rowSum;
179                List<QueryTree<N>> treeList;
180                for(Entry<QueryTree<N>, List<Integer>> entry : matrix.entrySet()){
181                        rowSum = sum(entry.getValue());
182                        treeList = map.get(rowSum);
183                        if(treeList == null){
184                                treeList = new ArrayList<>();
185                                map.put(rowSum, treeList);
186                        }
187                        treeList.add(entry.getKey());
188                }
189                
190                for(List<QueryTree<N>> trees : map.values()){
191                        leafs.addAll(trees);
192                }
193                Collections.reverse(leafs);
194                
195                return leafs;
196        }
197        
198        private int sum(List<Integer> list){
199                int sum = 0;
200                for(Integer i : list){
201                        sum += i;
202                }
203                return sum;
204        }
205        
206        private boolean coversNegativeTree(QueryTree<N> lgg, List<QueryTree<N>> negTrees){
207                for(QueryTree<N> negTree : negTrees){
208                        if(negTree.isSubsumedBy(lgg)){
209                                return true;
210                        }
211                }
212                return false;
213        }
214        
215        private void checkTree(Map<QueryTree<N>, List<Integer>> matrix, QueryTree<N> posTree, QueryTree<N> negTree, int index){
216                int entry;
217                Object edge;
218                for(QueryTree<N> child1 : posTree.getChildren()){
219                        entry = 0;
220                edge = posTree.getEdge(child1);
221                for(QueryTree<N> child2 : negTree.getChildren(edge)){
222                        if(child1.getUserObject().equals("?") ||
223                        (!child1.getUserObject().equals("?") && child1.getUserObject().equals(child2.getUserObject()))){
224                                entry = 1;
225                                checkTree(matrix, child1, child2, index);
226                        }
227                }
228                setMatrixEntry(matrix, child1, index, entry);
229                if(entry == 0){
230                        for(QueryTree<N> child : child1.getChildrenClosure()){
231                                if(!child1.equals(child)){
232                                        setMatrixEntry(matrix, child, index, 1);
233                                }
234                        }
235                }
236                }
237                
238        }
239        
240        private void setMatrixEntry(Map<QueryTree<N>, List<Integer>> matrix, QueryTree<N> row, int column, int entry){
241                List<Integer> list = matrix.get(row);
242                if(list == null){
243                        list = new ArrayList<>();
244                        matrix.put(row, list);
245                }
246                try {
247                        list.set(column, entry);
248                } catch (IndexOutOfBoundsException e) {
249                        list.add(entry);
250                }
251        }
252        
253        private String getLimitedEdgeCountQuery(QueryTree<N> tree){
254                List<QueryTree<N>> children;
255                int childCount = 1;
256                for(Object edge : tree.getEdges()){
257                        children = tree.getChildren(edge);
258                        childCount = children.size();
259                        while(childCount > 1){
260                                tree.removeChild((QueryTreeImpl<N>) children.get(childCount-1));
261                                childCount--;
262                        }
263                }
264                return tree.toSPARQLQueryString();
265        }
266        
267        private String printTreeWithValues(QueryTree<N> tree, Map<QueryTree<N>, List<Integer>> matrix){
268                int depth = tree.getPathToRoot().size();
269        StringBuilder sb = new StringBuilder();
270        if(tree.isRoot()){
271                sb.append("TREE\n\n");
272        }
273//        ren = ren.replace("\n", "\n" + sb);
274        sb.append(tree.getUserObject()).append("(").append(matrix.get(tree)).append(")");
275        sb.append("\n");
276        for (QueryTree<N> child : tree.getChildren()) {
277            for (int i = 0; i < depth; i++) {
278                sb.append("\t");
279            }
280            Object edge = tree.getEdge(child);
281            if (edge != null) {
282                sb.append("  ");
283                sb.append(edge);
284                sb.append(" ---> ");
285            }
286            sb.append(printTreeWithValues(child, matrix));
287        }
288        return sb.toString();
289        }
290        
291        
292        public String getQuestion(QueryTree<N> lgg, List<QueryTree<N>> negTrees, List<String> knownResources) throws TimeOutException{
293//              return computeQuestionOptimized(lgg, negTrees, knownResources);
294                mon.start();
295                String question = computeQuestionBetterPerformance(lgg, negTrees, knownResources);
296                mon.stop();
297                return question;
298        }
299        
300        public void setLGGInstances(Set<String> instances){
301                this.lggInstances = instances;
302        }
303        
304        
305        private String computeQuestionBetterPerformance(QueryTree<N> lgg, List<QueryTree<N>> negTrees, List<String> knownResources) throws TimeOutException{
306                startTime = System.currentTimeMillis();
307                this.lgg = lgg;
308                this.negTrees = negTrees;
309                if(userAnsweredWithNo()){
310                        noSequences.add(lastSequence);
311                }
312                negExamplesCount = negTrees.size();
313                determiningNodeIds = getDeterminingNodeIds(lgg, negTrees);
314                logger.debug("Computing next question...");
315                postLGG = getFilteredTree(lgg);
316                PostLGG<N> postGen;
317                if(endpoint != null){
318                        postGen = new PostLGG<>(endpoint);
319                } else {
320                        postGen = new PostLGG<>();
321                }
322                
323                postGen.simplifyTree(postLGG, negTrees);
324                if(logger.isDebugEnabled()){
325                        String treeString;
326                        if(endpoint instanceof SPARQLEndpointEx){
327                                treeString = TreeHelper.getAbbreviatedTreeRepresentation(
328                                                postLGG, ((SPARQLEndpointEx)endpoint).getBaseURI(), ((SPARQLEndpointEx)endpoint).getPrefixes());
329                        } else {
330                                treeString = postLGG.getStringRepresentation();
331                        }
332                        logger.debug("Post LGG(Tree): \n" + treeString);
333                        logger.debug("Post LGG(Query):\n" + postLGG.toSPARQLQueryString());
334                        logger.debug("Post LGG(#Instances):\n" + getAllResources(postLGG.toSPARQLQueryString()).size());
335                }
336                
337                limit = knownResources.size();
338                
339                List<GeneralisedQueryTree<N>> queue = null;
340                if(generalizeSortedByNegatives){
341                        queue = getAllowedGeneralisationsSortedByMatrix(new GeneralisedQueryTree<>(postLGG), negTrees);
342                } else {
343                        queue = getAllowedGeneralisationsSorted2(new GeneralisedQueryTree<>(postLGG));
344                }
345                logger.debug(getQueueLogInfo(queue));
346                
347                GeneralisedQueryTree<N> tree1;
348                GeneralisedQueryTree<N> tree2;
349                GeneralisedQueryTree<N> tmp;
350                List<GeneralisedQueryTree<N>> gens;
351                List<GeneralisedQueryTree<N>> neededGeneralisations;
352                while(!queue.isEmpty()){
353                        neededGeneralisations = new ArrayList<>();
354                        logger.debug("Selecting first tree from queue");
355//                      tree1 = queue.remove(0);
356                        tree1 = getGeneralisedQueryTreeNotContainingNoSequence(queue);
357                        tmp = tree1;
358                        
359                        if(logger.isDebugEnabled()){
360                                logger.debug("Changes: " + tmp.getChanges());
361                        }
362                        boolean coversNegTree = coversNegativeTree(tmp.getQueryTree(), negTrees);
363                        neededGeneralisations.add(tmp);
364                        logger.debug("covers negative tree: " + coversNegTree);
365                        while(!coversNegTree){
366                                if(generalizeSortedByNegatives){
367                                        gens = getAllowedGeneralisationsSortedByMatrix(tmp, negTrees);
368                                } else {
369                                        gens = getAllowedGeneralisationsSorted2(tmp);
370                                }
371                                if(gens.isEmpty()){
372                                        if(logger.isDebugEnabled()){
373                                                logger.debug("Couldn't create a generalisation which covers a negative tree.");
374                                        }
375                                        break;
376                                }
377//                              tmp = gens.remove(0);
378                                tmp = getGeneralisedQueryTreeNotContainingNoSequence(gens);
379                                
380                                if(logger.isDebugEnabled()){
381                                        logger.debug("Changes: " + tmp.getChanges());
382                                }
383                                queue.addAll(0, gens);
384                                logger.debug(getQueueLogInfo(queue));
385                                coversNegTree = coversNegativeTree(tmp.getQueryTree(), negTrees);
386                                if(coversNegTree) {
387                                        logger.debug("covers negative tree by changes " + tmp.getChanges());
388                                } else {
389                                        neededGeneralisations.add(tmp);
390                                }
391                        }
392                
393                        int index = neededGeneralisations.size()-1;
394                        if(coversNegTree){
395                                if(index == -1){
396                                        tree2 = tmp;
397                                }
398                                tree2 = neededGeneralisations.get(index--);
399                        } else {
400                                tree2 = tmp;
401                        }
402                        
403//                      QueryTree<N> newTree = getNewResource(tree2, knownResources);
404                        if(logger.isDebugEnabled()){
405                                logger.debug("Testing tree\n" + tree2.getQueryTree().getStringRepresentation());
406                        }
407                        String newResource = getNewResource2(fSparql(lgg, tree2.getChanges()), knownResources);
408                        if(isTerminationCriteriaReached()){
409                                throw new TimeOutException(maxExecutionTimeInSeconds);
410                        }
411                        logger.debug("New resource before binary search: " + newResource);
412                        if(!(newResource == null)){
413                                logger.debug("binary search for most specific query returning a resource - start");
414                                List<QueryTreeChange> firstChanges = new ArrayList<>(neededGeneralisations.get(0).getChanges());
415                                while(firstChanges.size() > 1){
416                                        firstChanges.remove(firstChanges.size()-1);
417                                        neededGeneralisations.add(0, new GeneralisedQueryTree<>(getTreeByChanges(lgg, firstChanges), firstChanges));
418                                        firstChanges = new ArrayList<>(firstChanges);
419                                }
420                                newResource = findMostSpecificResourceTree2(neededGeneralisations, knownResources, 0, neededGeneralisations.size()-1);
421                                logger.debug("binary search for most specific query returning a resource - completed");
422                                // TODO: probably the corresponding tree, which resulted in the resource, should also be returned
423                                return newResource;
424                        } else {
425                                if(logger.isDebugEnabled()){
426                                        logger.debug("Query result contains no new resources. Trying next tree from queue...");
427                                }
428                        }
429                }
430                return null;
431        }
432        
433        private GeneralisedQueryTree<N> getGeneralisedQueryTreeNotContainingNoSequence(List<GeneralisedQueryTree<N>> queue){
434                GeneralisedQueryTree<N> genTree;
435                for(int i = 0; i < queue.size(); i++){
436                        genTree = queue.get(i);
437                        boolean containsNoSequence = false;
438                        for(List<QueryTreeChange> seq : noSequences){
439                                if(genTree.getChanges().containsAll(seq)){
440                                        logger.info("Skipping sequence from queue " + genTree.getChanges() + " because it contains NO sequence" + seq);
441                                        containsNoSequence = true;
442                                        break;
443                                }
444                        }
445                        if(!containsNoSequence){
446                                return queue.remove(i);
447                        }
448                }
449                return queue.remove(0);
450        }
451        
452        private boolean userAnsweredWithNo(){
453                return (negExamplesCount != -1) && (negTrees.size() > negExamplesCount);
454        }
455        
456        private SortedSet<String> getAllResources(String query){
457                SortedSet<String> resources = new TreeSet<>();
458                query = query + " LIMIT 1000";
459                
460                QueryExecution qe = qef.createQueryExecution(query);
461                ResultSet rs = qe.execSelect();
462                
463                QuerySolution qs;
464                while(rs.hasNext()){
465                        qs = rs.next();
466                        resources.add(qs.getResource("x0").getURI());
467                }
468                qe.close();
469                return resources;
470        }
471        
472        private String findMostSpecificResourceTree2(List<GeneralisedQueryTree<N>> trees, List<String> knownResources, int low, int high) throws TimeOutException {
473                
474//              if(low==high) {
475//                      return low;
476//              }
477                int testIndex = low + (high-low)/2;
478                // perform SPARQL query
479                
480//              QueryTree<N> t = getNewResource(trees.get(testIndex), knownResources);
481                String t = null;
482                GeneralisedQueryTree<N> genTree = trees.get(testIndex);
483                if(logger.isDebugEnabled()){
484                        logger.debug("Binary search: Testing tree\n" + genTree.getQueryTree().getStringRepresentation());
485                }
486                try {
487                        t = getNewResource2(fSparql(lgg, genTree.getChanges()), knownResources);
488                } catch (HTTPException e) {
489                        throw new TimeOutException(maxExecutionTimeInSeconds);
490                }
491                if(isTerminationCriteriaReached()){
492                        throw new TimeOutException(maxExecutionTimeInSeconds);
493                }
494                if(testIndex == high){
495                        lastSequence = trees.get(testIndex).getChanges();
496                        return t;
497                }
498                if(t == null) {
499                        return findMostSpecificResourceTree2(trees,knownResources,testIndex+1,high);
500                } else {
501                        if(logger.isDebugEnabled()){
502                                logger.debug("Binary search: Found new resource \"" + t + "\"");
503                        }
504                        return findMostSpecificResourceTree2(trees,knownResources,low,testIndex);
505                }
506        }
507        
508        public List<GeneralisedQueryTree<N>> getAllowedGeneralisations(GeneralisedQueryTree<N> tree){
509                logger.debug("Computing allowed generalisations...");
510                List<GeneralisedQueryTree<N>> gens = new LinkedList<>();
511                gens.addAll(computeAllowedGeneralisations(tree, tree.getLastChange()));
512                return gens;
513        }
514        
515        private List<QueryTree<N>> getPossibleNodes2Change(QueryTree<N> tree){
516                List<QueryTree<N>> nodes = new ArrayList<>();
517                for(QueryTree<N> child : tree.getChildren()){
518                        if(child.isLeaf()){
519                                nodes.add(child);
520                        } else {
521                                if(child.getParent().getUserObject().equals("?")){
522                                        if(child.getUserObject().equals("?")){
523                                                nodes.addAll(getPossibleNodes2Change(child));
524                                        } else {
525                                                nodes.add(child);
526                                        }
527                                }
528                        }
529                }
530                return nodes;
531        }
532        
533        private List<GeneralisedQueryTree<N>> getAllowedGeneralisationsSortedByMatrix(GeneralisedQueryTree<N> tree, List<QueryTree<N>> negTrees){
534                Map<QueryTree<N>, List<Integer>> matrix = createMatrix(tree.getQueryTree(), negTrees);
535                logger.debug("Matrix:");
536                for(Entry<QueryTree<N>, List<Integer>> entry : matrix.entrySet()){
537                        logger.debug(entry.getKey().getId() + ": " + entry.getValue());
538                }
539                List<GeneralisedQueryTree<N>> gens = new ArrayList<>();
540                if(logger.isDebugEnabled()){
541                        String treeString;
542                        if(endpoint instanceof SPARQLEndpointEx){
543                                treeString = TreeHelper.getAbbreviatedTreeRepresentation(
544                                                negTrees.get(0), ((SPARQLEndpointEx)endpoint).getBaseURI(), ((SPARQLEndpointEx)endpoint).getPrefixes());
545                        } else {
546                                treeString = negTrees.get(0).getStringRepresentation();
547                        }
548                        logger.debug(treeString);
549                }
550                
551                
552                Map<GeneralisedQueryTree<N>, Integer> genTree2Sum = new HashMap<>();
553                
554                QueryTree<N> queryTree = tree.getQueryTree();
555                QueryTreeChange lastChange = tree.getLastChange();
556                List<QueryTreeChange> changes = tree.getChanges();
557                GeneralisedQueryTree<N> genTree;
558                N label;
559                Object edge;
560                QueryTree<N> parent;
561                boolean isLiteralNode;
562                for(QueryTree<N> node : getPossibleNodes2Change(tree.getQueryTree())){
563                        label = node.getUserObject();
564                        parent = node.getParent();
565                        isLiteralNode = node.isLiteralNode();
566                        edge = parent.getEdge(node);
567                        if(lastChange.getType() == ChangeType.REMOVE_NODE){
568                                if(node.getUserObject().equals("?") && node.getId() < lastChange.getNodeId()){
569                                        int pos = parent.removeChild((QueryTreeImpl<N>) node);
570                                        genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
571                                        genTree.addChanges(changes);
572                                        genTree.addChange(new QueryTreeChange(node.getId(), ChangeType.REMOVE_NODE));
573                                        genTree2Sum.put(genTree, sum(matrix.get(node)));
574                                        parent.addChild((QueryTreeImpl<N>) node, edge, pos);
575                                }
576                        } else {
577                                if(node.getUserObject().equals("?")){
578                                        int pos = parent.removeChild((QueryTreeImpl<N>) node);
579                                        genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
580                                        genTree.addChanges(changes);
581                                        genTree.addChange(new QueryTreeChange(node.getId(), ChangeType.REMOVE_NODE));
582                                        genTree2Sum.put(genTree, sum(matrix.get(node)));
583                                        parent.addChild((QueryTreeImpl<N>) node, edge, pos);
584                                } else if(lastChange.getNodeId() < node.getId()){
585                                        node.setUserObject((N) "?");
586                                        node.setVarNode(true);
587                                        genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
588                                        genTree.addChanges(changes);
589                                        genTree.addChange(new QueryTreeChange(node.getId(), ChangeType.REPLACE_LABEL));
590                                        genTree2Sum.put(genTree, sum(matrix.get(node)));
591                                        node.setUserObject(label);
592                                        node.setIsLiteralNode(isLiteralNode);
593                                        node.setIsResourceNode(!isLiteralNode);
594                                }
595                        }
596                }
597                List<Entry<GeneralisedQueryTree<N>, Integer>> entries = new ArrayList<>(genTree2Sum.entrySet());
598                Collections.sort(entries, new NegativeTreeOccurenceComparator());
599                for(Entry<GeneralisedQueryTree<N>, Integer> entry : entries){
600                        gens.add(entry.getKey());
601                }
602                return gens;
603        }
604        
605        private List<GeneralisedQueryTree<N>> getAllowedGeneralisationsSorted2(GeneralisedQueryTree<N> tree){
606                List<GeneralisedQueryTree<N>> gens = getAllowedGeneralisations(tree);
607                Iterator<GeneralisedQueryTree<N>> it = gens.iterator();
608                GeneralisedQueryTree<N> t;
609                while(it.hasNext()){
610                        t = it.next();
611                        for(List<QueryTreeChange> changes : noSequences){
612                                if(t.getChanges().containsAll(changes)){
613                                        it.remove();
614                                        break;
615                                }
616                        }
617                }
618                Collections.sort(gens, comparator);     
619                return gens;
620        }
621        
622        /**
623         * Computing the allowed generalisations, i.e. we traverse the tree from the root depths first. For the current considered node n 
624         * if the label of the parent node is a "?" and n is a resource node, we can replace it with "?", and if the current node n is a "?"
625         * and a leaf node, it can be removed. 
626         */
627        private List<GeneralisedQueryTree<N>> computeAllowedGeneralisations(GeneralisedQueryTree<N> tree, QueryTreeChange lastChange){
628                List<GeneralisedQueryTree<N>> gens = new LinkedList<>();
629                
630                QueryTree<N> queryTree = tree.getQueryTree();
631                List<QueryTreeChange> changes = tree.getChanges();
632                GeneralisedQueryTree<N> genTree;
633                N label;
634                N parentLabel;
635                Object edge;
636                QueryTree<N> parent;
637                boolean isLiteralNode;
638                for(QueryTree<N> child : queryTree.getChildren()){
639                        label = child.getUserObject();
640                        isLiteralNode = child.isLiteralNode();
641                        parent = child.getParent();
642                        parentLabel = parent.getUserObject();
643                        edge = parent.getEdge(child);
644                        if(!label.equals("?") && parentLabel.equals("?")){
645                                if(lastChange.getNodeId() >= child.getId() || lastChange.getType()==ChangeType.REMOVE_NODE){
646                                        continue;
647                                }
648                                if(parent.getChildren(edge).size() >= 2){
649                                        int pos = parent.removeChild((QueryTreeImpl<N>) child);
650                                        genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
651                                        genTree.addChanges(changes);
652                                        genTree.addChange(new QueryTreeChange(child.getId(), ChangeType.REPLACE_LABEL));
653                                        gens.add(genTree);
654                                        parent.addChild((QueryTreeImpl<N>) child, edge, pos);
655                                } else {
656                                        Map<Integer, N> node2Label = new HashMap<>();
657                                        for(QueryTree<N> c : child.getChildren()){
658                                                if(determiningNodeIds.contains(c.getId())){
659                                                        node2Label.put(c.getId(), c.getUserObject());
660                                                        c.setUserObject((N)"?");
661                                                }
662                                        }
663                                        child.setUserObject((N) "?");
664                                        child.setVarNode(true);
665                                        genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
666                                        genTree.addChanges(changes);
667                                        genTree.addChange(new QueryTreeChange(child.getId(), ChangeType.REPLACE_LABEL));
668                                        gens.add(genTree);
669                                        child.setUserObject(label);
670                                        child.setIsLiteralNode(isLiteralNode);
671                                        child.setIsResourceNode(!isLiteralNode);
672                                        for(QueryTree<N> c : child.getChildren()){
673                                                N oldLabel = node2Label.get(c.getId());
674                                                if(oldLabel != null){
675                                                        c.setUserObject(oldLabel);
676                                                }
677                                        }
678                                }
679//                              child.setUserObject((N) "?");
680//                              child.setVarNode(true);
681//                              genTree = new GeneralisedQueryTree<N>(new QueryTreeImpl<N>(queryTree));
682//                              genTree.addChanges(changes);
683//                              genTree.addChange(new QueryTreeChange(child.getId(), ChangeType.REPLACE_LABEL));
684//                              gens.add(genTree);
685//                              child.setUserObject(label);
686//                              child.setLiteralNode(isLiteralNode);
687//                              child.setResourceNode(!isLiteralNode);
688                        } else if(label.equals("?")){
689                                edge = queryTree.getEdge(child);
690                                parent = child.getParent();
691                                if(child.isLeaf()){
692                                        if(lastChange.getNodeId() < child.getId() && lastChange.getType() == ChangeType.REMOVE_NODE){
693                                                continue;
694                                        }
695                                        int pos = parent.removeChild((QueryTreeImpl<N>) child);
696                                        genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
697                                        genTree.addChanges(changes);
698                                        genTree.addChange(new QueryTreeChange(child.getId(), ChangeType.REMOVE_NODE));
699                                        gens.add(genTree);
700                                        parent.addChild((QueryTreeImpl<N>) child, edge, pos);
701                                } else {
702                                        int pos = parent.removeChild((QueryTreeImpl<N>) child);
703                                        for(GeneralisedQueryTree<N> subTree : computeAllowedGeneralisations(new GeneralisedQueryTree<>(child), tree.getLastChange())){
704                                                parent.addChild((QueryTreeImpl<N>) subTree.getQueryTree(), edge, pos);
705                                                genTree = new GeneralisedQueryTree<>(new QueryTreeImpl<>(queryTree));
706                                                genTree.addChanges(changes);
707                                                genTree.addChanges(subTree.getChanges());
708//                                              System.out.println(genTree.getChanges());
709//                                              System.err.println(getSPARQLQuery(genTree.getQueryTree()));
710                                                gens.add(genTree);
711                                                parent.removeChild((QueryTreeImpl<N>) subTree.getQueryTree());
712                                        }
713                                        parent.addChild((QueryTreeImpl<N>) child, edge, pos);
714                                }
715                        }
716                }
717                
718                return gens;
719        }
720        
721        private boolean hasAlwaysSameParent(QueryTree<N> node, List<QueryTree<N>> trees){
722                N parentLabel = node.getParent().getUserObject();
723                N nodeLabel = node.getUserObject();
724                List<Object> path = getPathFromRootToNode(node);
725                List<QueryTree<N>> nodes;
726                for(QueryTree<N> tree : trees){
727                        nodes = getNodesByPath(tree, new ArrayList<>(path));
728                        if(!nodes.isEmpty()){
729                                for(QueryTree<N> otherNode : nodes){
730                                        if(nodeLabel.equals(otherNode.getUserObject()) && !otherNode.getParent().getUserObject().equals(parentLabel)){
731                                                return false;
732                                        }
733                                }
734                        }
735                }
736                return true;
737        }
738        
739        private List<QueryTree<N>> getNodesByPath(QueryTree<N> tree, List<Object> path){
740                List<QueryTree<N>> nodes = new ArrayList<>();
741                for(QueryTree<N> child : tree.getChildren(path.remove(0))){
742                        if(path.isEmpty()){
743                                nodes.add(child);
744                        } else {
745                                nodes.addAll(getNodesByPath(child, new ArrayList<>(path)));
746                        }
747                }
748                return nodes;
749        }
750        
751        private List<Object> getPathFromRootToNode(QueryTree<N> node){
752                List<Object> path = new ArrayList<>();
753                QueryTree<N> parent = node.getParent();
754                path.add(parent.getEdge(node));
755                if(!parent.isRoot()){
756                        path.addAll(getPathFromRootToNode(parent));
757                }
758                Collections.reverse(path);
759                return path;
760        }
761        
762        private SortedSet<String> getResources(String query, int limit, int offset){
763                SortedSet<String> resources = new TreeSet<>();
764                this.query = query;
765                if(logger.isDebugEnabled()){
766                        logger.debug("Testing query\n" + getLimitedQuery(query, limit, offset) + "\n");
767                }
768                
769                QueryExecution qe = qef.createQueryExecution(getLimitedQuery(query, limit, offset));
770                ResultSet rs = qe.execSelect();
771                
772                QuerySolution qs;
773                while(rs.hasNext()){
774                        qs = rs.next();
775                        resources.add(qs.getResource("x0").getURI());
776                }
777                qe.close();
778                
779                return resources;
780        }
781        
782        private String getNewResource2(String query, List<String> knownResources){
783                SortedSet<String> foundResources;
784//              int i = 0;
785//              int chunkSize = 40;
786//              QueryTree<N> newTree;
787//              int foundSize;
788//              do{
789//                      foundResources = getResources(query, chunkSize, chunkSize * i);
790//                      foundSize = foundResources.size();
791//                      foundResources.removeAll(knownResources);
792//                      for(String resource : foundResources){System.err.println(resource);
793//                              newTree = getQueryTree(resource);
794//                              if(!newTree.isSubsumedBy(lgg)){mon.stop();System.err.println(mon.getLastValue());
795//                                      return resource;
796//                              }
797//                      }
798//                      i++;
799//              } while(foundSize == chunkSize);
800                foundResources = getResources(query, lggInstances.size()+1, 0);
801                foundResources.removeAll(knownResources);
802                foundResources.removeAll(lggInstances);
803                if(!foundResources.isEmpty()){
804//                      System.err.println(foundResources.first());
805                        return foundResources.first();
806                }
807                if(logger.isDebugEnabled()){
808                        logger.debug("Found no resource which would modify the LGG");
809                }
810                return null;
811        }
812        
813        private String getLimitedQuery(String query, int limit, int offset){
814                return query + " LIMIT " + limit + " OFFSET " + offset;
815        }
816        
817        private QueryTree<N> getFilteredTree(QueryTree<N> tree){
818                nodeId = 0;
819                QueryTree<N> filteredTree = createFilteredTree(tree);
820                return tree;//filteredTree;
821        }
822        
823        private QueryTree<N> createFilteredTree(QueryTree<N> tree){
824                QueryTree<N> filteredTree = new QueryTreeImpl<>(tree.getUserObject());
825                filteredTree.setId(nodeId);
826                QueryTree<N> subTree;
827                Object predicate;
828        for(QueryTree<N> child : tree.getChildren()){
829//              if(child.isLiteralNode()){
830//                      continue;
831//              }
832                predicate = tree.getEdge(child);
833                if(((String)predicate).startsWith("http://dbpedia.org/property")){
834                        continue;
835                }
836                this.nodeId++;
837                subTree = createFilteredTree(child);
838                subTree.setIsLiteralNode(child.isLiteralNode());
839                subTree.setIsResourceNode(child.isResourceNode());
840                filteredTree.addChild((QueryTreeImpl<N>)subTree, tree.getEdge(child));
841        }
842        return filteredTree;
843        }
844        
845        
846    
847    public QueryTree<N> getPostLGG(){
848        return postLGG;
849    }
850    
851    
852    private String getQueueLogInfo(List<GeneralisedQueryTree<N>> queue) {
853        int displayElements = 3;
854        int max = Math.min(displayElements, queue.size());
855        String str = "queue (size " + queue.size() + "): ";
856        for(int i=0; i<max; i++) {
857                str += queue.get(i).getChanges().toString() + ", ";
858        }
859        if(queue.size()>displayElements) {
860                str += " ... ";
861        }
862        return str;
863    }
864    
865    class GeneralisedQueryTreeComparator implements Comparator<GeneralisedQueryTree<N>>{
866
867        @Override
868                public int compare(GeneralisedQueryTree<N> tree1, GeneralisedQueryTree<N> tree2) {
869                        int aCount1 = 0;
870                        int aCount2 = 0;
871                        int bCount1 = 0;
872                        int bCount2 = 0;
873                        List<QueryTreeChange> changes1 = tree1.getChanges();
874                        List<QueryTreeChange> changes2 = tree2.getChanges();
875                        for(QueryTreeChange change : tree1.getChanges()){
876                                if(change.getType() == ChangeType.REPLACE_LABEL){
877                                        aCount1++;
878                                } else {
879                                        bCount1++;
880                                }
881                        }
882                        for(QueryTreeChange change : tree2.getChanges()){
883                                if(change.getType() == ChangeType.REPLACE_LABEL){
884                                        aCount2++;
885                                } else {
886                                        bCount2++;
887                                }
888                        }
889                        int nodeId1;
890                        int nodeId2;
891                        
892                        if(aCount1 < aCount2){
893                                return 1;
894                        } else if(aCount1 > aCount2){
895                                return -1;
896                        } else {
897                                if(bCount1 < bCount2){
898                                        return -1;
899                                } else if(bCount1 > bCount2){
900                                        return 1;
901                                } else {
902                                        for(int i = 0; i < changes1.size(); i++){
903                                                nodeId1 = changes1.get(i).getNodeId();
904                                                nodeId2 = changes2.get(i).getNodeId();
905                                                
906                                                if(nodeId1 != nodeId2){
907                                                        return nodeId1-nodeId2;
908                                                }
909                                        }
910                                        return 0;
911                                }
912                                
913                        }
914
915                        
916                }
917        
918    }
919    
920    class LastQueryTreeChangeComparator implements Comparator<GeneralisedQueryTree<N>>{
921
922        @Override
923                public int compare(GeneralisedQueryTree<N> tree1, GeneralisedQueryTree<N> tree2) {
924                        QueryTreeChange change1 = tree1.getLastChange();
925                        QueryTreeChange change2 = tree2.getLastChange();
926                        if(change1.getType()==ChangeType.REPLACE_LABEL){
927                                if(change2.getType()==ChangeType.REPLACE_LABEL){
928                                        return change1.getNodeId() - change2.getNodeId();
929                                } else {
930                                        return -1;
931                                }
932                        } else {
933                                if(change2.getType()==ChangeType.REPLACE_LABEL){
934                                        return 1;
935                                } else {
936                                        return change2.getNodeId() - change1.getNodeId();
937                                }
938                        }
939                        
940                }
941        
942    }
943    
944    class NegativeTreeOccurenceComparator implements Comparator<Entry<GeneralisedQueryTree<N>,Integer>>{
945
946                @Override
947                public int compare(Entry<GeneralisedQueryTree<N>, Integer> entry1,
948                                Entry<GeneralisedQueryTree<N>, Integer> entry2) {
949                        int sum1 = entry1.getValue();
950                        int sum2 = entry2.getValue();
951                        if(sum1 == sum2){
952                                QueryTreeChange change1 = entry1.getKey().getLastChange();
953                                QueryTreeChange change2 = entry2.getKey().getLastChange();
954                                if(change1.getType()==ChangeType.REPLACE_LABEL){
955                                        if(change2.getType()==ChangeType.REPLACE_LABEL){
956                                                return change1.getNodeId() - change2.getNodeId();
957                                        } else {
958                                                return -1;
959                                        }
960                                } else {
961                                        if(change2.getType()==ChangeType.REPLACE_LABEL){
962                                                return 1;
963                                        } else {
964                                                return change2.getNodeId() - change1.getNodeId();
965                                        }
966                                }
967                        } else {
968                                return sum2-sum1;
969                        }
970                }
971        
972    }
973    
974    private void limitEqualEdgesToLeafs(QueryTree<N> tree, int maxEqualEdgeCount){
975        if(tree.getChildren().isEmpty()){
976                return;
977        }
978        Set<QueryTree<N>> parents = new HashSet<>();
979        for(QueryTree<N> leaf : tree.getLeafs()){
980                if(leaf.getUserObject().equals("?")){
981                        parents.add(leaf.getParent());
982                }
983        }
984        for(QueryTree<N> parent : parents){
985                for(Object edge : parent.getEdges()){
986                        int cnt = 0;
987                        boolean existsResourceChild = false;
988                        for(QueryTree<N> child : parent.getChildren(edge)){
989                                if(!child.getUserObject().equals("?")){
990                                        existsResourceChild = true;
991                                        break;
992                                }
993                        }
994                        for(QueryTree<N> child : parent.getChildren(edge)){
995                                if(child.getUserObject().equals("?")){
996                                        if(child.isLeaf()){
997                                                cnt++;
998                                                if(existsResourceChild || cnt>maxEqualEdgeCount){
999                                                        parent.removeChild((QueryTreeImpl<N>) child);
1000                                                }
1001                                        }
1002                                }
1003                        }
1004                }
1005        }
1006        
1007    }
1008    
1009    public void stop(){
1010        stop = true;
1011    }
1012    
1013    public boolean isRunning(){
1014        return isRunning;
1015    }
1016    
1017    private boolean isTerminationCriteriaReached(){
1018        if(stop){
1019                return true;
1020        }
1021        boolean result = false;
1022        long totalTimeNeeded = System.currentTimeMillis() - this.startTime;
1023                long maxMilliSeconds = maxExecutionTimeInSeconds * 1000;
1024        result = totalTimeNeeded >= maxMilliSeconds;
1025        return result;
1026    }
1027    
1028    private String fSparql(QueryTree<N> tree, List<QueryTreeChange> changes){
1029        logger.debug("fSparql uses:" + changes);
1030        QueryTree<N> copy = new QueryTreeImpl<>(tree);
1031        StringBuilder query = new StringBuilder();
1032        StringBuilder triples = new StringBuilder();
1033        List<String> optionals = new ArrayList<>();
1034        List<String> filters = new ArrayList<>();
1035        query.append("SELECT DISTINCT ?x0 WHERE{\n");
1036        buildSPARQLQueryString(copy, changes, triples, optionals, filters);
1037        if(triples.toString().isEmpty()){
1038                triples.append("?x0 ?p ?o.\n");
1039        }
1040        query.append(triples.toString());
1041        for(String optional : optionals){
1042                query.append("OPTIONAL{").append(optional).append("}\n");
1043        }
1044        if(filters.size() > 0){
1045                query.append("FILTER(");
1046                for(int i = 0; i < filters.size()-1; i++){
1047                        query.append("(").append(filters.get(i)).append(") || ");
1048                }
1049                query.append("(").append(filters.get(filters.size()-1)).append(")");
1050                query.append(")\n");
1051        }
1052        query.append("}");
1053//      if(logger.isDebugEnabled()){
1054//              logger.debug("fsparql: generated query: \n" + query.toString());
1055//      }
1056        return query.toString();
1057        
1058    }
1059    
1060    private String fSparql2(QueryTree<N> tree, List<QueryTreeChange> changes){
1061        logger.debug("fSparql uses:" + changes);//getSPARQLQueries(tree, changes);
1062        QueryTree<N> copy = new QueryTreeImpl<>(tree);
1063        StringBuilder query = new StringBuilder();
1064        StringBuilder triples = new StringBuilder();
1065        List<String> optionals = new ArrayList<>();
1066        Map<String, String> filters = new HashMap<>();
1067        List<String> bounds = new ArrayList<>();
1068        query.append("SELECT DISTINCT ?x0 WHERE{\n");
1069        buildSPARQLQueryString2(copy, changes, triples, optionals, filters, bounds);
1070        if(triples.toString().isEmpty()){
1071                triples.append("?x0 ?p ?o.\n");
1072        }
1073        query.append(triples.toString());
1074        for(String optional : optionals){
1075                query.append("OPTIONAL{").append(optional).append("}\n");
1076        }
1077        List<String> filterParts = new ArrayList<>();
1078        filterParts.addAll(filters.keySet());
1079        filterParts.addAll(bounds);
1080        if(filterParts.size() > 0){
1081                query.append("FILTER(\n");
1082                String currentPart = null;
1083                for(int i = 0; i < filterParts.size(); i++){
1084                        int cnt = 1;
1085                        query.append("(");
1086                        currentPart = filterParts.get(i);
1087                        if(filters.get(currentPart) != null){
1088                                currentPart = currentPart + "!=" + filters.get(currentPart);
1089                                cnt++;
1090                                query.append(currentPart);
1091                                if(filters.keySet().size() > 1){
1092                                        query.append(" && ");
1093                                }
1094                        } else if(bounds.contains(currentPart)){
1095                                currentPart = "!BOUND(" + currentPart + ")";
1096                                query.append(currentPart);
1097                                if(!filters.keySet().isEmpty()){
1098                                        query.append(" && ");
1099                                }
1100                        }
1101                        for(String f : filters.keySet()){
1102                                if(!filterParts.get(i).equals(f)){
1103                                        query.append(f).append("=").append(filters.get(f));
1104                                        if(cnt < filters.keySet().size()){
1105                                                query.append(" && ");
1106                                        }
1107                                        cnt++;
1108                                } else {
1109//                                      cnt++;
1110                                }
1111                                
1112                                
1113                        }
1114                        query.append(")");
1115                        if(i < filterParts.size()-1){
1116                                query.append("\n||\n");
1117                                }
1118                        
1119                        
1120                }
1121                query.append("\n)\n");
1122        }
1123        query.append("}");
1124        if(logger.isDebugEnabled()){
1125                logger.debug("fsparql: generated query: \n" + query.toString());
1126        }
1127        return query.toString();
1128        
1129    }
1130    
1131    
1132    private void buildSPARQLQueryString(QueryTree<N> tree, List<QueryTreeChange> changes, StringBuilder triples, List<String> optionals, List<String> filters){
1133        Object subject = null;
1134        if(tree.getUserObject().equals("?")){
1135                subject = "?x" + tree.getId();
1136        } else {
1137                subject = "<" + tree.getUserObject() + ">";
1138        }
1139        Object predicate;
1140        Object object;
1141        if(!tree.isLeaf()){
1142                for(QueryTree<N> child : tree.getChildren()){
1143                        predicate = tree.getEdge(child);
1144                        object = child.getUserObject();
1145                        
1146                        boolean addFilter = false;
1147                        boolean removed = false;
1148                        String uri = null;
1149                        QueryTreeChange c = getChange(changes, child.getId());
1150                        if(c != null){
1151                                if(c.getType() == ChangeType.REPLACE_LABEL){
1152                                        uri = (String) object;
1153                                        if(((String)child.getUserObject()).contains("^^") || ((String)child.getUserObject()).contains("@")){
1154                                                filters.add("?x" + child.getId() + "!=" + uri);
1155                                        } else {
1156                                                filters.add("?x" + child.getId() + "!=<" + uri + ">");
1157                                        }
1158                                        
1159                                        child.setUserObject((N)"?");
1160                                } else {
1161                                        removed = true;
1162                                        if(!predicate.equals(RDF.type.toString())){
1163                                                optionals.add(subject + " <" + predicate + "> ?x" + child.getId());
1164//                                              triples.append("OPTIONAL{").append(subject).
1165//                                              append(" <").append(predicate).append("> ").append("?x").append(child.getId()).append("}\n");
1166                                                filters.add("!BOUND(?x" + child.getId() + ")");
1167                                        }
1168                                        child.getParent().removeChild((QueryTreeImpl<N>) child);
1169                                }
1170                                
1171                        }
1172                        object = child.getUserObject();
1173                        boolean objectIsResource = !object.equals("?");
1174                        if(!objectIsResource){
1175                                object = "?x" + child.getId();
1176                        } else if(((String)object).startsWith("http://")){
1177                                object = "<" + object + ">";
1178                        }
1179                        if(!removed){
1180                                triples.append(subject).append(" <").append(predicate).append("> ").append(object).append(".\n");
1181                        }
1182                        if(!objectIsResource){
1183                                buildSPARQLQueryString(child, changes, triples, optionals, filters);
1184                        }
1185                }
1186        }
1187    }
1188    
1189    private void buildSPARQLQueryString2(QueryTree<N> tree, List<QueryTreeChange> changes, StringBuilder triples, List<String> optionals, Map<String, String> filters, List<String> bounds){
1190        Object subject = null;
1191        if(tree.getUserObject().equals("?")){
1192                subject = "?x" + tree.getId();
1193        } else {
1194                subject = "<" + tree.getUserObject() + ">";
1195        }
1196        Object predicate;
1197        Object object;
1198        if(!tree.isLeaf()){
1199                for(QueryTree<N> child : tree.getChildren()){
1200                        predicate = tree.getEdge(child);
1201                        object = child.getUserObject();
1202                        
1203                        boolean addFilter = false;
1204                        boolean removed = false;
1205                        String uri = null;
1206                        QueryTreeChange c = getChange(changes, child.getId());
1207                        if(c != null){
1208                                if(c.getType() == ChangeType.REPLACE_LABEL){
1209                                        uri = (String) object;
1210                                        if(((String)child.getUserObject()).contains("^^") || ((String)child.getUserObject()).contains("@")){
1211//                                              filters.add("?x" + child.getId() + "!=" + uri);
1212                                                filters.put("?x" + child.getId(), uri);
1213                                        } else {
1214//                                              filters.add("?x" + child.getId() + "!=<" + uri + ">");
1215                                                filters.put("?x" + child.getId(), "<" + uri + ">");
1216                                        }
1217                                        
1218                                        child.setUserObject((N)"?");
1219                                } else {
1220                                        removed = true;
1221                                        if(!predicate.equals(RDF.type.toString())){
1222                                                optionals.add(subject + " <" + predicate + "> ?x" + child.getId());
1223        //                                      triples.append("OPTIONAL{").append(subject).
1224        //                                      append(" <").append(predicate).append("> ").append("?x").append(child.getId()).append("}\n");
1225//                                              filters.add("!BOUND(?x" + child.getId() + ")");
1226                                                bounds.add("?x" + child.getId());
1227                                        }
1228                                        child.getParent().removeChild((QueryTreeImpl<N>) child);
1229                                }
1230                                
1231                        }
1232                        object = child.getUserObject();
1233                        boolean objectIsResource = !object.equals("?");
1234                        if(!objectIsResource){
1235                                object = "?x" + child.getId();
1236                        } else if(((String)object).startsWith("http://")){
1237                                object = "<" + object + ">";
1238                        }
1239                        if(!removed){
1240                                triples.append(subject).append(" <").append(predicate).append("> ").append(object).append(".\n");
1241                        }
1242                        if(!objectIsResource){
1243                                buildSPARQLQueryString2(child, changes, triples, optionals, filters, bounds);
1244                        }
1245                }
1246        }
1247    }
1248    
1249    private List<String> getSPARQLQueries(QueryTree<N> tree, List<QueryTreeChange> changes){
1250        List<String> queries = new ArrayList<>();
1251        
1252        String originalQuery = tree.toSPARQLQueryString();
1253        
1254        for(QueryTree<N> leaf : tree.getLeafs()){
1255                QueryTreeChange c = getChange(changes, leaf.getId());
1256                if(c != null){
1257                        if(c.getType() == ChangeType.REPLACE_LABEL){
1258                                System.out.println("JENA:\n " + getSPARQLQuery(originalQuery, nodeId, (String) leaf.getUserObject()));
1259                        } else if(c.getType() == ChangeType.REMOVE_NODE){
1260                                System.out.println("JENA:\n " + getSPARQLQuery2(tree.toQuery(), nodeId));
1261                        }
1262                }
1263        }
1264        
1265        
1266        
1267        return queries;
1268    }
1269    
1270    private String getSPARQLQuery2(Query originalQuery, int nodeId){
1271                Query query = QueryFactory.create(originalQuery);
1272                Element elt = query.getQueryPattern();
1273                if ( elt instanceof ElementGroup ){
1274                        Node node = null;
1275                        Triple optional = null;
1276                        for (Element el : ((ElementGroup) elt).getElements()) {
1277                                if (el instanceof ElementTriplesBlock) {
1278                                        Triple current;
1279                                        int position = 1;
1280                                        for (Iterator<Triple> iter = ((ElementTriplesBlock) el).getPattern().iterator(); iter.hasNext();) {
1281                                                current = iter.next();
1282                                                if (current.getObject().isVariable() && current.getObject().getName().equals("x" + nodeId)) {
1283                                                        node = current.getObject();
1284                                                        position = ((ElementTriplesBlock) el).getPattern().getList().indexOf(current);
1285                                                        optional = current;
1286                                                        iter.remove();
1287                                                }
1288                                        }
1289                                }
1290                        }
1291                        
1292                        if(optional != null){
1293                                ElementTriplesBlock optionalTriplesBlock = new ElementTriplesBlock();
1294                                optionalTriplesBlock.addTriple(optional);
1295                                ((ElementGroup) elt).addElement(new ElementOptional(optionalTriplesBlock));
1296                                
1297                                
1298                                ElementFilter filter = new ElementFilter(new E_LogicalNot(new ExprVar(optional.getObject().getName())));
1299                ((ElementGroup)elt).addElementFilter(filter);
1300                        }
1301                }
1302                return query.toString();
1303        }
1304    
1305    private String getSPARQLQuery(String queryString, int nodeId, String label){
1306                Query query = QueryFactory.create(queryString);
1307                Element elt = query.getQueryPattern();
1308                if ( elt instanceof ElementGroup ){
1309                        Node node = null;
1310                        boolean addFilter = false;
1311                        for(Element el : ((ElementGroup)elt).getElements()){
1312                                if ( el instanceof ElementTriplesBlock )
1313                    {   Triple add = null;
1314                    Triple current;
1315                    int position = 1;
1316                        for(Iterator<Triple> iter = ((ElementTriplesBlock) el).getPattern().iterator() ; iter.hasNext() ; ){
1317                                current = iter.next();
1318                                if(current.getObject().toString().equals(label)){
1319                                        node = current.getObject();
1320                                        position = ((ElementTriplesBlock) el).getPattern().getList().indexOf(current);
1321                                        add = Triple.create(current.getSubject(), current.getPredicate(), NodeFactory.createVariable("x" + nodeId));
1322                                        iter.remove();
1323                                }
1324                        }
1325                        if(add != null){
1326                                ((ElementTriplesBlock) el).addTriple(position, add);
1327                                addFilter = true;
1328                        }
1329                    }
1330                        }
1331                        if(addFilter){
1332                                ElementFilter filter = new ElementFilter(new E_Equals(new ExprVar(Integer.toString(nodeId)), new NodeValueNode(node)));
1333                ((ElementGroup)elt).addElementFilter(filter);
1334                        }
1335                }
1336                return query.toString();
1337        }
1338    
1339//    private void buildSPARQLQueryString(QueryTree<N> tree, List<QueryTreeChange> changes, StringBuilder triples, List<String> filters){
1340//      Object subject = null;
1341//      if(tree.getUserObject().equals("?")){
1342//              subject = "?x" + tree.getId();
1343//      } else {
1344//              subject = "<" + tree.getUserObject() + ">";
1345//      }
1346//      Object predicate;
1347//      Object object;
1348//      if(!tree.isLeaf()){
1349//              for(QueryTree<N> child : tree.getChildren()){
1350//                      predicate = tree.getEdge(child);
1351//                      object = child.getUserObject();
1352//                      boolean objectIsResource = !object.equals("?");
1353//                      boolean addFilter = false;
1354//                      boolean removed = false;
1355//                      String uri = null;
1356//                      if(!objectIsResource){
1357//                              object = "?x" + child.getId();
1358//                      } else if(((String)object).startsWith("http://")){
1359//                              QueryTreeChange c = getChange(changes, child.getId());
1360//                              if(c != null){
1361//                                      if(c.getType() == ChangeType.REPLACE_LABEL){
1362//                                              uri = (String) object;
1363//                                      child.setUserObject((N)"?");
1364//                                      object = "?x" + child.getId();
1365//                                      addFilter = true;
1366//                                      } else {
1367//                                              removed = true;
1368//                                              triples.append("OPTIONAL{").append(subject).
1369//                                              append(" <").append(predicate).append("> ").append("?x").append(child.getId()).append("}\n");
1370//                                              filters.add("!BOUND(?x" + child.getId() + ")");
1371//                                              child.getParent().removeChild((QueryTreeImpl<N>) child);
1372//                                      }
1373//                                      
1374//                              } else {
1375//                                      object = "<" + object + ">";
1376//                              }
1377//                              
1378//                      }
1379//                      if(!removed){
1380//                              triples.append(subject).append(" <").append(predicate).append("> ").append(object).append(".\n");
1381//                      }
1382//                      if(addFilter){
1383//                              filters.add("?x" + child.getId() + "!=<" + uri + ">");
1384//                      }
1385//                      if(!objectIsResource){
1386//                              buildSPARQLQueryString(child, changes, triples, filters);
1387//                      }
1388//              }
1389//      }
1390//    }
1391    
1392    private QueryTree<N> getTreeByChanges(QueryTree<N> originalTree, List<QueryTreeChange> changes){
1393        QueryTree<N> copy = new QueryTreeImpl<>(originalTree);
1394        QueryTree<N> node;
1395        for(QueryTreeChange change : changes){
1396                node = copy.getNodeById(change.getNodeId());
1397                if(change.getType() == ChangeType.REPLACE_LABEL){
1398                        node.setUserObject((N)"?");
1399                } else {
1400                        node.getParent().removeChild((QueryTreeImpl<N>) node);
1401                }
1402        }
1403        return copy;
1404    }
1405    
1406    private QueryTreeChange getChange(List<QueryTreeChange> changes, int nodeId){
1407        QueryTreeChange change = null;
1408        for(QueryTreeChange c : changes){
1409                if(c.getNodeId() == nodeId){
1410                        if(c.getType() == ChangeType.REMOVE_NODE){
1411                                return c;
1412                        } else {
1413                                change = c;
1414                        }
1415                }
1416        }
1417        return change;
1418    }
1419    
1420    private ResultSet executeSelectQuery(String query){
1421        ResultSet rs;
1422        if(model == null){
1423                QueryEngineHTTP queryExecution = new QueryEngineHTTP(endpoint.getURL().toString(), query);
1424                queryExecution.setTimeout(maxExecutionTimeInSeconds * 1000);
1425                for (String dgu : endpoint.getDefaultGraphURIs()) {
1426                        queryExecution.addDefaultGraph(dgu);
1427                }
1428                for (String ngu : endpoint.getNamedGraphURIs()) {
1429                        queryExecution.addNamedGraph(ngu);
1430                }                       
1431                rs = queryExecution.execSelect();
1432        } else {
1433                rs = QueryExecutionFactory.create(query, model).execSelect();
1434        }
1435        
1436                return rs;
1437    }
1438
1439}