triplestore.java

这是外国一个开源推理机

		// Get best matching index
		int bestScore = -1;
		TripleIndex bestIndex = null;
		for (int i = 0; i < _indexes.length; i++) {
			int score = _indexes[i].getPatternScore(subj, pred, obj);
			if (score > bestScore) {
				bestScore = score;
				bestIndex = _indexes[i];
			}
		}

		byte[] searchKey = _getSearchKey(subj, pred, obj);
		byte[] searchMask = _getSearchMask(subj, pred, obj);

		if (bestScore > 0) {
			// Use ranged search
			byte[] minValue = _getMinValue(subj, pred, obj);
			byte[] maxValue = _getMaxValue(subj, pred, obj);

			//ThreadLog.trace("using " + bestIndex.getFieldSeq() + " index with a score of " +
			//		bestScore + " for pattern (" + subj + ", " + pred + ", " + obj + ")");

			return bestIndex.getBTree().iterateValues(searchKey, searchMask, minValue, maxValue);
		}
		else {
			//ThreadLog.trace("using sequential search for pattern (" + subj + ", " + pred + ", " + obj + ")");
			// Use sequential scan
			return bestIndex.getBTree().iterateValues(searchKey, searchMask);
		}
	}

	public void startTransaction()
		throws IOException
	{
		for (int i = 0; i < _indexes.length; i++) {
			_indexes[i].getBTree().startTransaction();
		}
	}

	public void commitTransaction()
		throws IOException
	{
		for (int i = 0; i < _indexes.length; i++) {
			_indexes[i].getBTree().commitTransaction();
		}
	}

	public void rollbackTransaction()
		throws IOException
	{
		// FIXME: transaction rollback not implemented yet
		throw new IOException("transaction rollback not implemented yet");
	}

	public void clear()
		throws IOException
	{
		for (int i = 0; i < _indexes.length; i++) {
			_indexes[i].getBTree().clear();
		}
	}

	public byte[] storeTriple(int subj, int pred, int obj)
		throws IOException
	{
		byte[] data = _getData(subj, pred, obj);

		byte[] oldData = _indexes[0].getBTree().insert(data);

		if (oldData == null || !Arrays.equals(data, oldData)) {
			// new or changed data was inserted into the first index,
			// also insert it into the other indexes
			for (int i = 1; i < _indexes.length; i++) {
				_indexes[i].getBTree().insert(data);
			}
		}

		return oldData;
	}

	public int removeTriples(int subj, int pred, int obj)
		throws IOException
	{
		// FIXME: naive implementation below
		ArrayList removeList = new ArrayList();

		BTreeIterator iter = getTriples(subj, pred, obj);
		byte[] value = iter.next();
		while (value != null) {
			removeList.add(value);
			value = iter.next();
		}

		for (int i = 0; i < _indexes.length; i++) {
			BTree btree = _indexes[i].getBTree();

			for (int j = 0; j < removeList.size(); j++) {
				btree.remove( (byte[])removeList.get(j) );
			}
		}

		return removeList.size();
	}

	private byte[] _getData(int subj, int pred, int obj) {
		byte[] data = new byte[RECORD_LENGTH];

		ByteArrayUtil.putInt(subj, data, SUBJ_IDX);
		ByteArrayUtil.putInt(pred, data, PRED_IDX);
		ByteArrayUtil.putInt(obj, data, OBJ_IDX);
		data[FLAG_IDX] = EXPLICIT_FLAG;

		return data;
	}

	private byte[] _getSearchKey(int subj, int pred, int obj) {
		byte[] searchKey = _getData(subj, pred, obj);
		searchKey[FLAG_IDX] = 0;
		return searchKey;
	}

	private byte[] _getSearchMask(int subj, int pred, int obj) {
		byte[] mask = new byte[RECORD_LENGTH];

		if (subj != 0) {
			ByteArrayUtil.putInt(0xffffffff, mask, SUBJ_IDX);
		}
		if (pred != 0) {
			ByteArrayUtil.putInt(0xffffffff, mask, PRED_IDX);
		}
		if (obj != 0) {
			ByteArrayUtil.putInt(0xffffffff, mask, OBJ_IDX);
		}

		return mask;
	}

	private byte[] _getMinValue(int subj, int pred, int obj) {
		byte[] minValue = new byte[RECORD_LENGTH];

		// No need to check for values being equal to 0 as
		// this happens to be the minimum value anyway
		ByteArrayUtil.putInt(subj, minValue, SUBJ_IDX);
		ByteArrayUtil.putInt(pred, minValue, PRED_IDX);
		ByteArrayUtil.putInt(obj, minValue, OBJ_IDX);

		return minValue;
	}

	private byte[] _getMaxValue(int subj, int pred, int obj) {
		byte[] maxValue = new byte[RECORD_LENGTH];

		ByteArrayUtil.putInt( (subj == 0 ? 0xffffffff : subj), maxValue, SUBJ_IDX);
		ByteArrayUtil.putInt( (pred == 0 ? 0xffffffff : pred), maxValue, PRED_IDX);
		ByteArrayUtil.putInt( (obj  == 0 ? 0xffffffff : obj),  maxValue, OBJ_IDX);

		return maxValue;
	}

	private File _getIndexFile(String fieldSeq) {
		return new File(_dir, "triples-" + fieldSeq + ".dat");
	}

	private void _loadProperties(File propFile)
		throws IOException
	{
		InputStream in = new FileInputStream(propFile);
		try {
			_properties.clear();
			_properties.load(in);
		}
		finally {
			in.close();
		}
	}

	private void _storeProperties(File propFile)
		throws IOException
	{
		OutputStream out = new FileOutputStream(propFile);
		try {
			_properties.store(out, "triple indexes meta-data, DO NOT EDIT!");
		}
		finally {
			out.close();
		}
	}

/*------------------------+
| Inner class TripleIndex |
+------------------------*/

	private class TripleIndex {

		private String _fieldSeq;
		private File _file;
		private BTree _btree;

		public TripleIndex(String fieldSeq)
			throws IOException
		{
			_fieldSeq = fieldSeq;
			_file = _getIndexFile(fieldSeq);
			_btree = new BTree(_file, 2048, RECORD_LENGTH, new TripleComparator(_fieldSeq));
		}

		public String getFieldSeq() {
			return _fieldSeq;
		}

		public File getFile() {
			return _file;
		}

		public BTree getBTree() {
			return _btree;
		}

		/**
		 * Determines the 'score' of this index on the supplied pattern of
		 * subject, predicate and object IDs. The higher the score, the better
		 * the index is suited for matching the pattern. Lowest score is 0,
		 * which means that the index will perform a sequential scan.
		 */
		public int getPatternScore(int subj, int pred, int obj) {
			int score = 0;

			for (int i = 0; i < _fieldSeq.length(); i++) {
				char field = _fieldSeq.charAt(i);
				if (field == 's') {
					if (subj == 0) {
						break;
					} else {
						score++;
					}
				}
				else if (field == 'p') {
					if (pred == 0) {
						break;
					} else {
						score++;
					}
				}
				else if (field == 'o') {
					if (obj == 0) {
						break;
					} else {
						score++;
					}
				}
			}

			return score;
		}
	}

/*-----------------------------+
| Inner class TripleComparator |
+-----------------------------*/

	/**
	 * A BTreeValueComparator that can be used to create indexes with a
	 * configurable order of the subject, predicate and object fields.
	 */
	private static class TripleComparator implements BTreeValueComparator {

		private String _fieldSeq;

		public TripleComparator(String fieldSeq) {
			_fieldSeq = fieldSeq;
		}

		// implements BTreeValueComparator.compareBTreeValues()
		public final int compareBTreeValues(byte[] key, byte[] data, int offset, int length) {
			int result = 0;

			for (int i = 0; result == 0 && i < _fieldSeq.length(); i++) {
				switch (_fieldSeq.charAt(i)) {
					case 's': result = ByteArrayUtil.compareRegion(key, SUBJ_IDX, data, offset + SUBJ_IDX, 4); break;
					case 'p': result = ByteArrayUtil.compareRegion(key, PRED_IDX, data, offset + PRED_IDX, 4); break;
					case 'o': result = ByteArrayUtil.compareRegion(key, OBJ_IDX, data, offset + OBJ_IDX, 4); break;
					default: throw new IllegalArgumentException(
							 "invalid character '" + _fieldSeq.charAt(i) + "' in field sequence: " + _fieldSeq);
				}
			}

			return result;
		}
	}
}