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}