001: /*
002: * Copyright Aduna (http://www.aduna-software.com/) (c) 1997-2007.
003: * Copyright James Leigh (c) 2006.
004: *
005: * Licensed under the Aduna BSD-style license.
006: */
007:
008: package org.openrdf.sail.memory;
009:
010: import java.util.ArrayList;
011: import java.util.Collections;
012: import java.util.List;
013: import java.util.Set;
014:
015: import info.aduna.concurrent.locks.Lock;
016: import info.aduna.iteration.CloseableIteration;
017: import info.aduna.iteration.CloseableIteratorIteration;
018: import info.aduna.iteration.FilterIteration;
019: import info.aduna.iteration.IteratorIteration;
020: import info.aduna.iteration.LockingIteration;
021: import info.aduna.iteration.UnionIteration;
022:
023: import org.openrdf.model.Namespace;
024: import org.openrdf.model.Resource;
025: import org.openrdf.model.Statement;
026: import org.openrdf.model.URI;
027: import org.openrdf.model.Value;
028: import org.openrdf.query.BindingSet;
029: import org.openrdf.query.Dataset;
030: import org.openrdf.query.QueryEvaluationException;
031: import org.openrdf.query.algebra.QueryRoot;
032: import org.openrdf.query.algebra.StatementPattern;
033: import org.openrdf.query.algebra.TupleExpr;
034: import org.openrdf.query.algebra.Var;
035: import org.openrdf.query.algebra.evaluation.TripleSource;
036: import org.openrdf.query.algebra.evaluation.impl.BindingAssigner;
037: import org.openrdf.query.algebra.evaluation.impl.CompareOptimizer;
038: import org.openrdf.query.algebra.evaluation.impl.ConjunctiveConstraintSplitter;
039: import org.openrdf.query.algebra.evaluation.impl.ConstantOptimizer;
040: import org.openrdf.query.algebra.evaluation.impl.EvaluationStatistics;
041: import org.openrdf.query.algebra.evaluation.impl.EvaluationStrategyImpl;
042: import org.openrdf.query.algebra.evaluation.impl.FilterOptimizer;
043: import org.openrdf.query.algebra.evaluation.impl.QueryJoinOptimizer;
044: import org.openrdf.query.algebra.evaluation.impl.QueryModelPruner;
045: import org.openrdf.query.algebra.evaluation.impl.SameTermFilterOptimizer;
046: import org.openrdf.query.algebra.evaluation.util.QueryOptimizerList;
047: import org.openrdf.sail.SailException;
048: import org.openrdf.sail.helpers.SailConnectionBase;
049: import org.openrdf.sail.inferencer.InferencerConnection;
050: import org.openrdf.sail.memory.model.MemResource;
051: import org.openrdf.sail.memory.model.MemStatement;
052: import org.openrdf.sail.memory.model.MemStatementIterator;
053: import org.openrdf.sail.memory.model.MemStatementList;
054: import org.openrdf.sail.memory.model.MemURI;
055: import org.openrdf.sail.memory.model.MemValue;
056: import org.openrdf.sail.memory.model.MemValueFactory;
057: import org.openrdf.sail.memory.model.ReadMode;
058:
059: /**
060: * Implementation of a Sail Connection for memory stores.
061: *
062: * @author Arjohn Kampman
063: * @author jeen
064: */
065: public class MemoryStoreConnection extends SailConnectionBase implements
066: InferencerConnection {
067:
068: /*-----------*
069: * Variables *
070: *-----------*/
071:
072: protected final MemoryStore store;
073:
074: /**
075: * The exclusive transaction lock held by this connection during
076: * transactions.
077: */
078: private Lock txnLock;
079:
080: /**
081: * A statement list read lock held by this connection during transactions.
082: * Keeping this lock prevents statements from being removed from the main
083: * statement list during transactions.
084: */
085: private Lock txnStLock;
086:
087: /*--------------*
088: * Constructors *
089: *--------------*/
090:
091: protected MemoryStoreConnection(MemoryStore store) {
092: super (store);
093: this .store = store;
094: }
095:
096: /*---------*
097: * Methods *
098: *---------*/
099:
100: @Override
101: protected CloseableIteration<? extends BindingSet, QueryEvaluationException> evaluateInternal(
102: TupleExpr tupleExpr, Dataset dataset, BindingSet bindings,
103: boolean includeInferred) throws SailException {
104: // Clone the tuple expression to allow for more aggresive optimizations
105: tupleExpr = tupleExpr.clone();
106:
107: if (!(tupleExpr instanceof QueryRoot)) {
108: // Add a dummy root node to the tuple expressions to allow the
109: // optimizers to modify the actual root node
110: tupleExpr = new QueryRoot(tupleExpr);
111: }
112:
113: Lock stLock = store.getStatementsReadLock();
114:
115: try {
116: int snapshot = store.getCurrentSnapshot();
117: ReadMode readMode = ReadMode.COMMITTED;
118:
119: if (transactionActive()) {
120: snapshot++;
121: readMode = ReadMode.TRANSACTION;
122: }
123:
124: TripleSource tripleSource = new MemTripleSource(
125: includeInferred, snapshot, readMode);
126: EvaluationStrategyImpl strategy = new EvaluationStrategyImpl(
127: tripleSource, dataset);
128:
129: QueryOptimizerList optimizerList = new QueryOptimizerList();
130: optimizerList.add(new BindingAssigner());
131: optimizerList.add(new ConstantOptimizer(strategy));
132: optimizerList.add(new CompareOptimizer());
133: optimizerList.add(new ConjunctiveConstraintSplitter());
134: optimizerList.add(new SameTermFilterOptimizer());
135: optimizerList.add(new QueryModelPruner());
136: optimizerList.add(new QueryJoinOptimizer(
137: new MemEvaluationStatistics()));
138: optimizerList.add(new FilterOptimizer());
139:
140: optimizerList.optimize(tupleExpr, dataset, bindings);
141:
142: CloseableIteration<BindingSet, QueryEvaluationException> iter;
143: iter = strategy.evaluate(tupleExpr, bindings);
144: return new LockingIteration<BindingSet, QueryEvaluationException>(
145: stLock, iter);
146: } catch (QueryEvaluationException e) {
147: stLock.release();
148: throw new SailException(e);
149: } catch (RuntimeException e) {
150: stLock.release();
151: throw e;
152: }
153: }
154:
155: @Override
156: protected void closeInternal() throws SailException {
157: // do nothing
158: }
159:
160: @SuppressWarnings("unchecked")
161: @Override
162: protected CloseableIteration<? extends Resource, SailException> getContextIDsInternal()
163: throws SailException {
164: Lock stLock = store.getStatementsReadLock();
165:
166: try {
167: // Iterate over all MemURIs and MemBNodes
168: CloseableIteration<MemResource, SailException> iter;
169:
170: iter = new UnionIteration<MemResource, SailException>(
171: new IteratorIteration<MemResource, SailException>(
172: store.getValueFactory().getMemURIs()
173: .iterator()),
174: new IteratorIteration<MemResource, SailException>(
175: store.getValueFactory().getMemBNodes()
176: .iterator()));
177:
178: final int snapshot = transactionActive() ? store
179: .getCurrentSnapshot() + 1 : store
180: .getCurrentSnapshot();
181: final ReadMode readMode = transactionActive() ? ReadMode.TRANSACTION
182: : ReadMode.COMMITTED;
183:
184: iter = new FilterIteration<MemResource, SailException>(iter) {
185:
186: @Override
187: protected boolean accept(MemResource memResource)
188: throws SailException {
189: MemStatementList contextStatements = memResource
190: .getContextStatementList();
191:
192: // Filter resources that are not used as context identifier
193: if (contextStatements.size() == 0) {
194: return false;
195: }
196:
197: // Filter more thoroughly by considering snapshot and read-mode
198: // parameters
199: MemStatementIterator<SailException> iter = new MemStatementIterator<SailException>(
200: contextStatements, null, null, null, false,
201: snapshot, readMode);
202: try {
203: return iter.hasNext();
204: } finally {
205: iter.close();
206: }
207: }
208: };
209:
210: // Release query lock when iterator is closed
211: iter = new LockingIteration<MemResource, SailException>(
212: stLock, iter);
213:
214: return iter;
215: } catch (RuntimeException e) {
216: stLock.release();
217: throw e;
218: }
219: }
220:
221: @Override
222: protected CloseableIteration<? extends Statement, SailException> getStatementsInternal(
223: Resource subj, URI pred, Value obj,
224: boolean includeInferred, Resource... contexts)
225: throws SailException {
226: Lock stLock = store.getStatementsReadLock();
227:
228: try {
229: int snapshot = store.getCurrentSnapshot();
230: ReadMode readMode = ReadMode.COMMITTED;
231:
232: if (transactionActive()) {
233: snapshot++;
234: readMode = ReadMode.TRANSACTION;
235: }
236:
237: return new LockingIteration<MemStatement, SailException>(
238: stLock, store.createStatementIterator(
239: SailException.class, subj, pred, obj,
240: !includeInferred, snapshot, readMode,
241: contexts));
242: } catch (RuntimeException e) {
243: stLock.release();
244: throw e;
245: }
246: }
247:
248: @Override
249: protected long sizeInternal(Resource... contexts)
250: throws SailException {
251: Lock stLock = store.getStatementsReadLock();
252:
253: try {
254: CloseableIteration<? extends Statement, SailException> iter = getStatementsInternal(
255: null, null, null, false, contexts);
256:
257: try {
258: long size = 0L;
259:
260: while (iter.hasNext()) {
261: iter.next();
262: size++;
263: }
264:
265: return size;
266: } finally {
267: iter.close();
268: }
269: } finally {
270: stLock.release();
271: }
272: }
273:
274: @Override
275: protected CloseableIteration<? extends Namespace, SailException> getNamespacesInternal()
276: throws SailException {
277: return new CloseableIteratorIteration<Namespace, SailException>(
278: store.getNamespaceStore().iterator());
279: }
280:
281: @Override
282: protected String getNamespaceInternal(String prefix)
283: throws SailException {
284: return store.getNamespaceStore().getNamespace(prefix);
285: }
286:
287: @Override
288: protected void startTransactionInternal() throws SailException {
289: if (!store.isWritable()) {
290: throw new SailException(
291: "Unable to start transaction: data file is read-only");
292: }
293:
294: txnStLock = store.getStatementsReadLock();
295:
296: // Prevent concurrent transactions by acquiring an exclusive txn lock
297: txnLock = store.getTransactionLock();
298: store.startTransaction();
299: }
300:
301: @Override
302: protected void commitInternal() throws SailException {
303: store.commit();
304: txnLock.release();
305: txnStLock.release();
306: }
307:
308: @Override
309: protected void rollbackInternal() throws SailException {
310: try {
311: store.rollback();
312: } finally {
313: txnLock.release();
314: txnStLock.release();
315: }
316: }
317:
318: @Override
319: protected void addStatementInternal(Resource subj, URI pred,
320: Value obj, Resource... contexts) throws SailException {
321: addStatementInternal(subj, pred, obj, true, contexts);
322: }
323:
324: public boolean addInferredStatement(Resource subj, URI pred,
325: Value obj, Resource... contexts) throws SailException {
326: Lock conLock = getSharedConnectionLock();
327: try {
328: verifyIsOpen();
329:
330: Lock txnLock = getTransactionLock();
331: try {
332: autoStartTransaction();
333: return addStatementInternal(subj, pred, obj, false,
334: contexts);
335: } finally {
336: txnLock.release();
337: }
338: } finally {
339: conLock.release();
340: }
341: }
342:
343: /**
344: * Adds the specified statement to this MemoryStore.
345: *
346: * @throws SailException
347: */
348: protected boolean addStatementInternal(Resource subj, URI pred,
349: Value obj, boolean explicit, Resource... contexts)
350: throws SailException {
351: Statement st = null;
352:
353: if (contexts.length == 0) {
354: st = store.addStatement(subj, pred, obj, null, explicit);
355: if (st != null) {
356: notifyStatementAdded(st);
357: }
358: } else {
359: for (Resource context : contexts) {
360: st = store.addStatement(subj, pred, obj, context,
361: explicit);
362: if (st != null) {
363: notifyStatementAdded(st);
364: }
365: }
366: }
367:
368: // FIXME: this return type is invalid in case multiple contexts were
369: // specified
370: return st != null;
371: }
372:
373: @Override
374: protected void removeStatementsInternal(Resource subj, URI pred,
375: Value obj, Resource... contexts) throws SailException {
376: removeStatementsInternal(subj, pred, obj, true, contexts);
377: }
378:
379: public boolean removeInferredStatement(Resource subj, URI pred,
380: Value obj, Resource... contexts) throws SailException {
381: Lock conLock = getSharedConnectionLock();
382: try {
383: verifyIsOpen();
384:
385: Lock txnLock = getTransactionLock();
386: try {
387: autoStartTransaction();
388: return removeStatementsInternal(subj, pred, obj, false,
389: contexts);
390: } finally {
391: txnLock.release();
392: }
393: } finally {
394: conLock.release();
395: }
396: }
397:
398: @Override
399: protected void clearInternal(Resource... contexts)
400: throws SailException {
401: removeStatementsInternal(null, null, null, true, contexts);
402: }
403:
404: public void clearInferred(Resource... contexts)
405: throws SailException {
406: Lock conLock = getSharedConnectionLock();
407: try {
408: verifyIsOpen();
409:
410: Lock txnLock = getTransactionLock();
411: try {
412: autoStartTransaction();
413: removeStatementsInternal(null, null, null, false,
414: contexts);
415: } finally {
416: txnLock.release();
417: }
418: } finally {
419: conLock.release();
420: }
421: }
422:
423: public void flushUpdates() {
424: // no-op; changes are reported as soon as they come in
425: }
426:
427: /**
428: * Removes the statements that match the specified pattern of subject,
429: * predicate, object and context.
430: *
431: * @param subj
432: * The subject for the pattern, or <tt>null</tt> for a wildcard.
433: * @param pred
434: * The predicate for the pattern, or <tt>null</tt> for a wildcard.
435: * @param obj
436: * The object for the pattern, or <tt>null</tt> for a wildcard.
437: * @param explicit
438: * Flag indicating whether explicit or inferred statements should be
439: * removed; <tt>true</tt> removes explicit statements that match the
440: * pattern, <tt>false</tt> removes inferred statements that match
441: * the pattern.
442: * @throws SailException
443: */
444: protected boolean removeStatementsInternal(Resource subj, URI pred,
445: Value obj, boolean explicit, Resource... contexts)
446: throws SailException {
447: CloseableIteration<MemStatement, SailException> stIter = store
448: .createStatementIterator(SailException.class, subj,
449: pred, obj, explicit,
450: store.getCurrentSnapshot() + 1,
451: ReadMode.TRANSACTION, contexts);
452:
453: return removeIteratorStatements(stIter, explicit);
454: }
455:
456: protected boolean removeIteratorStatements(
457: CloseableIteration<MemStatement, SailException> stIter,
458: boolean explicit) throws SailException {
459: boolean statementsRemoved = false;
460:
461: try {
462: while (stIter.hasNext()) {
463: MemStatement st = stIter.next();
464:
465: if (store.removeStatement(st, explicit)) {
466: statementsRemoved = true;
467: notifyStatementRemoved(st);
468: }
469: }
470: } finally {
471: stIter.close();
472: }
473:
474: return statementsRemoved;
475:
476: }
477:
478: @Override
479: protected void setNamespaceInternal(String prefix, String name)
480: throws SailException {
481: // FIXME: changes to namespace prefixes not isolated in transactions yet
482: try {
483: store.getNamespaceStore().setNamespace(prefix, name);
484: } catch (IllegalArgumentException e) {
485: throw new SailException(e.getMessage());
486: }
487: }
488:
489: @Override
490: protected void removeNamespaceInternal(String prefix)
491: throws SailException {
492: // FIXME: changes to namespace prefixes not isolated in transactions yet
493: store.getNamespaceStore().removeNamespace(prefix);
494: }
495:
496: @Override
497: protected void clearNamespacesInternal() throws SailException {
498: // FIXME: changes to namespace prefixes not isolated in transactions yet
499: store.getNamespaceStore().clear();
500: }
501:
502: /*-----------------------------*
503: * Inner class MemTripleSource *
504: *-----------------------------*/
505:
506: /**
507: * Implementation of the TripleSource interface from the Sail Query Model
508: */
509: protected class MemTripleSource implements TripleSource {
510:
511: protected final int snapshot;
512:
513: protected final ReadMode readMode;
514:
515: protected final boolean includeInferred;
516:
517: public MemTripleSource(boolean includeInferred, int snapshot,
518: ReadMode readMode) {
519: this .includeInferred = includeInferred;
520: this .snapshot = snapshot;
521: this .readMode = readMode;
522: }
523:
524: public CloseableIteration<MemStatement, QueryEvaluationException> getStatements(
525: Resource subj, URI pred, Value obj,
526: Resource... contexts) {
527: return store.createStatementIterator(
528: QueryEvaluationException.class, subj, pred, obj,
529: !includeInferred, snapshot, readMode, contexts);
530: }
531:
532: public MemValueFactory getValueFactory() {
533: return store.getValueFactory();
534: }
535: } // end inner class MemTripleSource
536:
537: /*-------------------------------------*
538: * Inner class MemEvaluationStatistics *
539: *-------------------------------------*/
540:
541: /**
542: * Uses the MemoryStore's statement sizes to give cost estimates based on the
543: * size of the expected results. This process could be improved with
544: * repository statistics about size and distribution of statements.
545: *
546: * @author Arjohn Kampman
547: * @author James Leigh
548: */
549: protected class MemEvaluationStatistics extends
550: EvaluationStatistics {
551:
552: @Override
553: protected CardinalityCalculator getCardinalityCalculator(
554: Set<String> boundVars) {
555: return new MemCardinalityCalculator(boundVars);
556: }
557:
558: protected class MemCardinalityCalculator extends
559: CardinalityCalculator {
560:
561: public MemCardinalityCalculator(Set<String> boundVars) {
562: super (boundVars);
563: }
564:
565: @Override
566: public void meet(StatementPattern sp) {
567: Resource subj = (Resource) getConstantValue(sp
568: .getSubjectVar());
569: URI pred = (URI) getConstantValue(sp.getPredicateVar());
570: Value obj = getConstantValue(sp.getObjectVar());
571: Resource context = (Resource) getConstantValue(sp
572: .getContextVar());
573:
574: MemValueFactory valueFactory = store.getValueFactory();
575:
576: // Perform look-ups for value-equivalents of the specified values
577: MemResource memSubj = valueFactory.getMemResource(subj);
578: MemURI memPred = valueFactory.getMemURI(pred);
579: MemValue memObj = valueFactory.getMemValue(obj);
580: MemResource memContext = valueFactory
581: .getMemResource(context);
582:
583: if (subj != null && memSubj == null || pred != null
584: && memPred == null || obj != null
585: && memObj == null || context != null
586: && memContext == null) {
587: // non-existent subject, predicate, object or context
588: cardinality = 0;
589: return;
590: }
591:
592: // Search for the smallest list that can be used by the iterator
593: List<Integer> listSizes = new ArrayList<Integer>(4);
594: if (memSubj != null) {
595: listSizes.add(memSubj.getSubjectStatementCount());
596: }
597: if (memPred != null) {
598: listSizes.add(memPred.getPredicateStatementCount());
599: }
600: if (memObj != null) {
601: listSizes.add(memObj.getObjectStatementCount());
602: }
603: if (memContext != null) {
604: listSizes
605: .add(memContext.getContextStatementCount());
606: }
607:
608: if (listSizes.isEmpty()) {
609: cardinality = store.size();
610:
611: int sqrtFactor = 2 * countBoundVars(sp);
612:
613: if (sqrtFactor > 1) {
614: cardinality = Math.pow(cardinality,
615: 1.0 / sqrtFactor);
616: }
617: } else {
618: cardinality = Collections.min(listSizes);
619:
620: int constantVarCount = countConstantVars(sp);
621: int boundVarCount = countBoundVars(sp);
622:
623: // Subtract 1 from constantVarCount as this was used for the list
624: // size
625: int sqrtFactor = 2 * boundVarCount
626: + Math.max(0, constantVarCount - 1);
627:
628: if (sqrtFactor > 1) {
629: cardinality = Math.pow(cardinality,
630: 1.0 / sqrtFactor);
631: }
632: }
633: }
634:
635: protected Value getConstantValue(Var var) {
636: if (var != null) {
637: return var.getValue();
638: }
639:
640: return null;
641: }
642: }
643: } // end inner class MemCardinalityCalculator
644: }
|