Source for file RdqlMemEngine.php

Documentation is available at RdqlMemEngine.php

  1. <?php
  2.  
  3. // ----------------------------------------------------------------------------------
  4. // Class: RdqlMemEngine
  5. // ----------------------------------------------------------------------------------
  6.  
  7.  
  8.  
  9. /**
  10. * This class performes as RDQL query on a MemModel.
  11. *
  12. * Provided an rdql query parsed into an array of php variables and constraints
  13. * at first the engine searches for tuples matching all patterns from the WHERE clause
  14. * of the given RDQL query. Then the query result set is filtered with evaluated
  15. * boolean expressions from the AND clause of the given RDQL query.
  16. *
  17. *
  18. * <BR><BR>History:<UL>
  19. * <LI>09-08-2004 : findTriplesMatchingPattern() rewritten to only use the $model->find()
  20. * function for accessing the model. Changed the method of comparing literals to literals->equals
  21. * according to actual specification
  22. * <LI>05-12-2004 : Bug in the handling of empty Literals fixed.</LI>
  23. * <LI>03-17-2004 : Function findTuplesMatchingOnePattern()
  24. * pass-by-reference bug fixed</LI>
  25. * <LI>08-29-2003 : Function filterTuples(): some bugs fixed:
  26. * - strEqExpr with NE operator
  27. * - regExExpr combined with other expr. and negation (!)
  28. * e.g. !(?x ~~ "/sth/" && ?x > 5)
  29. * <LI>07-27-2003 : First version of this class</LI>
  30. *
  31. * @version V0.9.1
  32. * @author Radoslaw Oldakowski <radol@gmx.de>
  33. *
  34. * @package rdql
  35. * @access public
  36. */
  37.  
  38. Class RdqlMemEngine extends RdqlEngine {
  39.  
  40.  
  41. /**
  42. * Parsed query variables and constraints.
  43. *
  44. * @var array ['selectVars'][] = ?VARNAME
  45. * ['sources'][] = URI
  46. * ['patterns'][]['subject']['value'] = VARorURI
  47. * ['predicate']['value'] = VARorURI
  48. * ['object']['value'] = VARorURIorLiterl
  49. * ['is_literal'] = boolean
  50. * ['l_lang'] = string
  51. * ['l_dtype'] = string
  52. * ['filters'][]['string'] = string
  53. * ['evalFilterStr'] = string
  54. * ['reqexEqExprs'][]['var'] = ?VARNAME
  55. * ['operator'] = (eq | ne)
  56. * ['regex'] = string
  57. * ['strEqExprs'][]['var'] = ?VARNAME
  58. * ['operator'] = (eq | ne)
  59. * ['value'] = string
  60. * ['value_type'] = ('variable' | 'URI' | 'Literal')
  61. * ['value_lang'] = string
  62. * ['value_dtype'] = string
  63. * ['numExpr']['vars'][] = ?VARNAME
  64. * ( [] stands for an integer index - 0..N )
  65. * @access private
  66. */
  67. var $parsedQuery;
  68.  
  69.  
  70. /**
  71. * Perform an RDQL Query on the given MemModel.
  72. *
  73. * @param object MemModel &$memModel
  74. * @param array &$parsedQuery (the same format as $this->parsedQuery)
  75. * @param boolean $returnNodes
  76. * @return array [][?VARNAME] = object Node (if $returnNodes = TRUE)
  77. * OR array [][?VARNAME] = string
  78. *
  79. * @access public
  80. */
  81. function & queryModel(&$memModel, &$parsedQuery, $returnNodes = TRUE) {
  82.  
  83. $this->parsedQuery = $parsedQuery;
  84.  
  85. // find tuples matching all patterns
  86. $res = $this->findTuplesMatchingAllPatterns($memModel);
  87.  
  88. // filter tuples
  89. if (isset($parsedQuery['filters']))
  90. $res = $this->filterTuples($res);
  91.  
  92. // select variables to be returned
  93. $res = $this->selectVariables($res);
  94.  
  95. if(!$returnNodes)
  96. return $this->toString($res);
  97.  
  98. return $res;
  99. }
  100.  
  101. /**
  102. * Find triples matching all patterns of an RDQL query and return an array
  103. * with variables from all patterns and their corresponding values.
  104. * The variable values returned are instances of object Node.
  105. *
  106. * @param object MemModel &$memModel
  107. * @return array [][?VARNAME] = object Node
  108. *
  109. * @access private
  110. */
  111. function findTuplesMatchingAllPatterns(&$memModel) {
  112.  
  113. $resultSet = $this->findTuplesMatchingOnePattern($memModel, $this->parsedQuery['patterns'][0]);
  114. for ($i=1; $i<count($this->parsedQuery['patterns']); $i++) {
  115. $rs = $this->findTuplesMatchingOnePattern($memModel, $this->parsedQuery['patterns'][$i]);
  116. $resultSet = $this->joinTuples($resultSet, $rs);
  117. }
  118. return $resultSet;
  119. }
  120.  
  121.  
  122. /**
  123. * Find tuples matching one pattern and return an array with pattern
  124. * variables and their corresponding values (instances of object Node).
  125. *
  126. * @param object MemModel &$memModel
  127. * @param array &$pattern ['subject']['value'] = VARorURI
  128. * ['predicate']['value'] = VARorURI
  129. * ['object']['value'] = VARorURIorLiterl
  130. * ['is_literal'] = boolean
  131. * ['l_lang'] = string
  132. * ['l_dtype'] = string
  133. * @return array [][?VARNAME] = object Node
  134. *
  135. * @access private
  136. */
  137. function findTuplesMatchingOnePattern(&$memModel, &$pattern) {
  138.  
  139. $resultSet = array();
  140. $i = 0;
  141. // parameters to be passed to the method findTriplesMatchingPattern
  142. foreach ($pattern as $key => $v) {
  143. if ($v['value'] && $v['value']{0} == '?') {
  144. if ($key == 'object') {
  145. $param['object']['is_a'] = 'ANY';
  146. $param['object']['string'] = 'ANY';
  147. $param['object']['lang'] = NULL;
  148. $param['object']['dtype'] = NULL;
  149. } else
  150. $param[$key] = 'ANY';
  151. $var[$i]['key'] = $key;
  152. $var[$i++]['val'] = $v['value'];
  153. }else
  154. if (isset($v['is_literal'])) {
  155. $param[$key]['is_a'] = 'Literal';
  156. $param[$key]['string'] = $v['value'];
  157. $param[$key]['lang'] = $v['l_lang'];
  158. $param[$key]['dtype'] = $v['l_dtype'];
  159. }else{
  160. if ($key == 'object') {
  161. $param[$key]['is_a'] = 'Resource';
  162. $param[$key]['string'] = $v['value'];
  163. $param[$key]['lang'] = NULL;
  164. $param[$key]['dtype'] = NULL;
  165. }else
  166. $param[$key] = $v['value'];
  167. }
  168. }
  169. // find pattern internal bindings e.g. (?x, ?z, ?x)
  170. $intBindings = NULL;
  171. for ($i=0; $i<count($var); $i++)
  172. foreach($var as $n => $v)
  173. if ($i != $n && $var[$i]['val'] == $v['val'])
  174. $intBindings[] = $var[$i]['key'];
  175.  
  176. // find triples of the $memModel matching $pattern
  177. $resModel = $this->findTriplesMatchingPattern($memModel, $param['subject'],
  178. $param['predicate'],
  179. $param['object']['is_a'],
  180. $param['object']['string'],
  181. $param['object']['lang'],
  182. $param['object']['dtype'],
  183. $intBindings);
  184.  
  185. // set values of the pattern variables to be returned
  186. if ($pattern['subject']['value']{0} == '?') {
  187. $n = 0;
  188. foreach ($resModel->triples as $triple)
  189. $resultSet[$n++][$pattern['subject']['value']] = $triple->subj;
  190. }
  191. if ($pattern['predicate']['value']{0} == '?') {
  192. $n = 0;
  193. foreach ($resModel->triples as $triple)
  194. $resultSet[$n++][$pattern['predicate']['value']] = $triple->pred;
  195. }
  196. if ($pattern['object']['value'] && $pattern['object']['value']{0} == '?') {
  197. $n = 0;
  198. foreach ($resModel->triples as $triple)
  199. $resultSet[$n++][$pattern['object']['value']] = $triple->obj;
  200. }
  201. return $resultSet;
  202. }
  203.  
  204.  
  205. /**
  206. * Search in $memModel for triples matching one pattern from the WHERE clause.
  207. * 'ANY' input for $subjLabel..$objLabel, $obj_is will match anything.
  208. * NULL input for $objDtype will only match obj->dtype = NULL
  209. * NULL input for $objLanguage will match obj->lang = NULL or anything if a
  210. * literal is datatyped (except for XMLLiterals and plain literals)
  211. * This method also checks internal bindings if provided.
  212. *
  213. * @param object MemModel $memModel
  214. * @param string $subjLabel
  215. * @param string $predLabel
  216. * @param string $objLabel
  217. * @param string $obj_is
  218. * @param string $objLanguage
  219. * @param string $objDtype
  220. * @param array $intBindings [] = string
  221. * @return object MemModel
  222. * @access private
  223. */
  224. function findTriplesMatchingPattern(&$memModel, $subjLabel, $predLabel, $obj_is,
  225. $objLabel, $objLang, $objDtype, &$intBindings) {
  226.  
  227. $res = new MemModel();
  228.  
  229. if($memModel->isEmpty())
  230. return $res;
  231.  
  232. if ($subjLabel=='ANY')
  233. {
  234. $subj=NULL;
  235. } else
  236. {
  237. $subj=new Resource($subjLabel);
  238. };
  239. if ($predLabel=='ANY')
  240. {
  241. $pred=NULL;
  242. } else
  243. {
  244. $pred=new Resource($predLabel);
  245. };
  246. if ($objLabel=='ANY')
  247. {
  248. $obj=NULL;
  249. } else
  250. {
  251. if ($obj_is == 'Literal')
  252. {
  253. $obj=new Literal($objLabel);
  254. $obj->setDatatype($objDtype);
  255. $obj->setLanguage($objLang);
  256. } else {
  257. $obj=new Resource($objLabel);
  258. }
  259. };
  260. $res=$memModel->find($subj,$pred,$obj);
  261.  
  262. if ($intBindings)
  263. foreach ($res->triples as $triple)
  264. {
  265. if (!$this->_checkIntBindings($triple, $intBindings))
  266. {
  267. $res->remove($triple);
  268. }
  269. }
  270.  
  271. return $res;
  272. }
  273.  
  274. /**
  275. * Perform an SQL-like inner join on two resultSets.
  276. *
  277. * @param array &$finalRes [][?VARNAME] = object Node
  278. * @param array &$res [][?VARNAME] = object Node
  279. * @return array [][?VARNAME] = object Node
  280. *
  281. * @access private
  282. */
  283. function joinTuples(&$finalRes, &$res) {
  284.  
  285. if (count($finalRes) == 0 || count($res) == 0)
  286. return array();
  287.  
  288. // find joint variables and new variables to be added to $finalRes
  289. $jointVars = array();
  290. $newVars = array();
  291. foreach ($res[0] as $varname => $node) {
  292. if (array_key_exists($varname, $finalRes[0]))
  293. $jointVars[] = $varname;
  294. else
  295. $newVars[] = $varname;
  296. }
  297.  
  298. // eliminate rows of $finalRes in which the values of $jointVars do not have
  299. // a corresponding row in $res.
  300. foreach ($finalRes as $n => $fRes) {
  301. foreach ($res as $i => $r) {
  302. $ok = TRUE;
  303. foreach ($jointVars as $j_varname)
  304. if ($r[$j_varname] != $fRes[$j_varname]) {
  305. $ok = FALSE;
  306. break;
  307. }
  308. if ($ok)
  309. break;
  310. }
  311. if (!$ok)
  312. unset($finalRes[$n]);
  313. }
  314.  
  315. // join $res and $finalRes
  316. $joinedRes = array();
  317. foreach ($res as $i => $r) {
  318. foreach ($finalRes as $n => $fRes) {
  319. $ok = TRUE;
  320. foreach ($jointVars as $j_varname)
  321. if ($r[$j_varname] != $fRes[$j_varname]) {
  322. $ok = FALSE;
  323. break;
  324. }
  325. if ($ok) {
  326. $joinedRow = $finalRes[$n];
  327. foreach($newVars as $n_varname)
  328. $joinedRow[$n_varname] = $r[$n_varname];
  329. $joinedRes[] = $joinedRow;
  330. }
  331. }
  332. }
  333. return $joinedRes;
  334. }
  335.  
  336. /**
  337. * Filter the result-set of query variables by evaluating each filter from the
  338. * AND clause of the RDQL query.
  339. *
  340. * @param array &$finalRes [][?VARNAME] = object Node
  341. * @return array [][?VARNAME] = object Node
  342. * @access private
  343. */
  344. function filterTuples(&$finalRes) {
  345.  
  346. foreach ($this->parsedQuery['filters'] as $filter) {
  347.  
  348. foreach ($finalRes as $n => $fRes) {
  349. $evalFilterStr = $filter['evalFilterStr'];
  350.  
  351. // evaluate regex equality expressions of each filter
  352. foreach ($filter['regexEqExprs'] as $i => $expr) {
  353.  
  354. preg_match($expr['regex'], $fRes[$expr['var']]->getLabel(), $match);
  355. $op = substr($expr['operator'], 0,1);
  356. if (($op != '!' && !isset($match[0])) || ($op == '!' && isset($match[0])))
  357. $evalFilterStr = str_replace("##RegEx_$i##", 'FALSE', $evalFilterStr);
  358. else
  359. $evalFilterStr = str_replace("##RegEx_$i##", 'TRUE', $evalFilterStr);
  360.  
  361. }
  362.  
  363. // evaluate string equality expressions
  364. foreach ($filter['strEqExprs'] as $i => $expr) {
  365.  
  366. $exprBoolVal = 'FALSE';
  367. switch ($expr['value_type']) {
  368.  
  369. case 'variable':
  370. if (($fRes[$expr['var']] == $fRes[$expr['value']] && $expr['operator'] == 'eq') ||
  371. ($fRes[$expr['var']] != $fRes[$expr['value']] && $expr['operator'] == 'ne'))
  372. $exprBoolVal = 'TRUE';
  373. break;
  374. case 'URI':
  375.  
  376. if (is_a($fRes[$expr['var']], 'Literal')) {
  377. if ($expr['operator'] == 'ne')
  378. $exprBoolVal = 'TRUE';
  379. break;
  380. }
  381.  
  382. if (($fRes[$expr['var']]->getLabel() == $expr['value'] && $expr['operator'] == 'eq') ||
  383. ($fRes[$expr['var']]->getLabel() != $expr['value'] && $expr['operator'] == 'ne'))
  384. $exprBoolVal = 'TRUE';
  385. break;
  386. case 'Literal':
  387.  
  388. if (!is_a($fRes[$expr['var']], 'Literal')) {
  389. if ($expr['operator'] == 'ne')
  390. $exprBoolVal = 'TRUE';
  391. break;
  392. }
  393.  
  394. $filterLiteral= new Literal($expr['value'],$expr['value_lang']);
  395. $filterLiteral->setDatatype($expr['value_dtype']);
  396. $equal=$fRes[$expr['var']]->equals($filterLiteral);
  397. /* if ($fRes[$expr['var']]->getLabel() == $expr['value'] &&
  398. $fRes[$expr['var']]->getDatatype() == $expr['value_dtype']) {
  399. $equal = TRUE;
  400. // Lang tags only differentiate literals in rdf:XMLLiterals and plain literals.
  401. // Therefore if a literal is datatyped ignore the language tag.
  402. if ((($expr['value_dtype'] == NULL) ||
  403. ($expr['value_dtype'] == 'http://www.w3.org/1999/02/22-rdf-syntax-ns#XMLLiteral') ||
  404. ($expr['value_dtype'] == 'http://www.w3.org/2001/XMLSchema#string')) &&
  405. (($fRes[$expr['var']]->getLanguage() != $expr['value_lang'])))
  406. $equal = FALSE;
  407. }else
  408. $equal = FALSE;
  409. */
  410. if (($equal && $expr['operator'] == 'eq') ||
  411. (!$equal && $expr['operator'] == 'ne'))
  412. $exprBoolVal = 'TRUE';
  413. else
  414. $exprBoolVal = 'FALSE';
  415.  
  416. }
  417. $evalFilterStr = str_replace("##strEqExpr_$i##", $exprBoolVal, $evalFilterStr);
  418. }
  419.  
  420. // evaluate numerical expressions
  421. foreach ($filter['numExprVars'] as $varName) {
  422. $varValue = "'" .$fRes[$varName]->getLabel() ."'";
  423. $evalFilterStr = str_replace($varName, $varValue, $evalFilterStr);
  424. }
  425.  
  426. eval("\$filterBoolVal = $evalFilterStr; \$eval_filter_ok = TRUE;");
  427. if (!isset($eval_filter_ok))
  428. trigger_error(RDQL_AND_ERR ."'" .htmlspecialchars($filter['string']) ."'", E_USER_ERROR);
  429.  
  430. if (!$filterBoolVal)
  431. unset($finalRes[$n]);
  432. }
  433. }
  434.  
  435. return $finalRes;
  436. }
  437.  
  438.  
  439. /**
  440. * Remove all conditional variables from the result-set and leave only variables
  441. * specified in the SELECT clause of the RDQL query.
  442. *
  443. * @param array &$finalRes [][?VARNAME] = object Node
  444. * @return array [][?VARNAME] = object Node
  445. * @access private
  446. */
  447. function selectVariables(&$finalRes) {
  448.  
  449. // if nothing has been found return only one row of $finalRes
  450. // with select variables having empty values
  451. if (count($finalRes) == 0) {
  452. foreach ($this->parsedQuery['selectVars'] as $selectVar)
  453. $finalRes[0][$selectVar] = NULL;
  454. return $finalRes;
  455. }
  456. // return only selectVars in the same order as given in the RDQL query
  457. // and reindex $finalRes.
  458. $n = 0;
  459. foreach($finalRes as $key => $val) {
  460. foreach ($this->parsedQuery['selectVars'] as $selectVar)
  461. $resultSet[$n][$selectVar] = $val[$selectVar];
  462. unset($finalRes[$key]);
  463. ++$n;
  464. }
  465.  
  466. return $resultSet;
  467. }
  468.  
  469.  
  470. /**
  471. * Convert the variable values of $finalRes from objects to their string serialization.
  472. *
  473. * @param array &$finalRes [][?VARNAME] = object Node
  474. * @return array [][?VARNAME] = string
  475. * @access private
  476. */
  477. function toString(&$finalRes) {
  478.  
  479. foreach ($finalRes as $n => $tuple)
  480. foreach ($tuple as $varname => $node) {
  481. if (is_a($node, 'Resource'))
  482. $res[$n][$varname] = '<' .$node->getLabel() .'>';
  483. elseif (is_a($node, 'Literal')) {
  484. $res[$n][$varname] = '"' .$node->getLabel() .'"';
  485. if ($node->getLanguage())
  486. $res[$n][$varname] .= ' (xml:lang="' .$node->getLanguage() .'")';
  487. if ($node->getDatatype())
  488. $res[$n][$varname] .= ' (rdf:datatype="' .$node->getDatatype() .'")';
  489. }else
  490. $res[$n][$varname] = $node;
  491. }
  492. return $res;
  493. }
  494.  
  495.  
  496. /**
  497. * Check if the given triple meets pattern internal bindings
  498. * e.g. (?x, ?z, ?x) ==> statement subject must be identical with the statement object
  499. *
  500. * @param object statement &$triple
  501. * @param array &$intBindings [] = string
  502. * @return boolean
  503. * @access private
  504. */
  505. function _checkIntBindings (&$triple, &$intBindings) {
  506.  
  507. if (in_array('subject', $intBindings)) {
  508. if (in_array('predicate', $intBindings))
  509. if ($triple->subj != $triple->pred)
  510. return FALSE;
  511. if (in_array('object', $intBindings)) {
  512. if (is_a($triple->obj, 'Literal'))
  513. return FALSE;
  514. elseif ($triple->subj != $triple->obj)
  515. return FALSE;
  516. }
  517. return TRUE;
  518. }
  519. if (in_array('predicate', $intBindings)) {
  520. if (is_a($triple->obj, 'Literal'))
  521. return FALSE;
  522. elseif ($triple->pred != $triple->obj)
  523. return FALSE;
  524. return TRUE;
  525. }
  526. }
  527.  
  528.  
  529. /**
  530. * Check if the lang and dtype of the passed object Literal are equal $lang and $dtype
  531. * !!! Language only differentiates literals in rdf:XMLLiterals and plain literals (xsd:string).
  532. * !!! Therefore if a literal is datatyped ignore the language.
  533. *
  534. * @param object Literal $literal
  535. * @param string $dtype1
  536. * @param string $dtype2
  537. * @return boolean
  538. * @access private
  539. */
  540. function _equalsLangDtype ($literal, $lang, $dtype) {
  541.  
  542. if ($dtype == $literal->getDatatype()) {
  543. if (($dtype == NULL ||
  544. $dtype == 'http://www.w3.org/2001/XMLSchema#string' ||
  545. $dtype == 'http://www.w3.org/1999/02/22-rdf-syntax-ns#XMLLiteral') &&
  546. ($lang != $literal->getLanguage()))
  547. return FALSE;
  548. return TRUE;
  549. }
  550. return FALSE;
  551. }
  552. } // end: Class RdqlMemEngine
  553.  
  554. ?>

Documentation generated on Fri, 17 Dec 2004 16:17:31 +0100 by phpDocumentor 1.3.0RC3