On the Feasibility of Handling Uncertainty in SPARQL Queries in the Case of Sparse Graphs
Keywords:
RDF graph, SPARQL query, probabilistic SPARQL query, sparse matrices, probabilistic matricesAbstract
The purpose of this paper is to explore the possibility of evaluating SPARQL queries containing probabilities using linear algebraic methods and techniques. This approach has many important advantages, such as simplicity, succinctness, elegance and greater familiarity to a wide base of practitioners. On the other hand, there are questions regarding its efficiency in view of the huge datasets of the current era. In this paper, we advocate that in the case of sparse RDF graphs we can resort to sparse matrices for computing complicated probabilistic queries. It is demonstrated that via probabilistic sparse matrices one can evaluate specific types of queries involving transitive predicates, which are of great practical importance. The algorithm and data structures that are currently available for handling sparse matrices promise improved performance in pragmatic situations, which constitutes this line of approach particularly promising.
Downloads
References
Andronikos, T., “Classification of SPARQL queries into equivalence classes of relevant queries”, International Journal of Advanced Research in Computer Science, December 2017, Volume 8, No. 9, pages 152-159.
Andronikos, T., Complex Matrices for the Approximate Evaluation of Probabilistic Queries, International Journal of Engineering Research and Applications (IJERA), Vol. 10, Issue 11, (Series-I) November 2020, pp. 23-30.
Andronikos T., Singh A., Giannakis K., Sioutas S., Computing probabilistic queries in the presence of uncertainty via probabilistic automata, Algorithmic Aspects of Cloud Computing, Third International Workshop, ALGOCLOUD 2017, Vienna, Austria, 5 September, 2017, Revised Selected Papers. Springer Theoretical Computer Science and General Issues, Volume 10739, pp. 106-122, 2018.
Motik, B., Representing and querying validity time in RDF and OWL: A logic-based approach, Journal of Web Semantics, Elsevier BV, 2012, 12-13, 3-21.
Andronikos T., Stefanidakis M., Papadakis I., Adding Temporal Dimension to Ontologies via OWL Reification, Proceedings of the 13th Panhellenic Conference on Informatics - PCI 2009 Conference, 10-12 September, Corfu, Greece, IEEE Computer Society, pp. 19-22, 2009.
López, C. P., MATLAB Linear Algebra, Apress, 2014.
Fang, H. pSPARQL: A Querying Language for Probabilistic RDF Data Complexity, Hindawi Limited, 2019, 1-7.
H. Fang and X. Zhang, “pSPARQL: a querying language for probabilistic RDF (extended abstract),” in Proceedings of the ISWC’16, Posters, 2016.
Giannakis K., Andronikos T., Querying Linked Data and Büchi Automata, IEEE Proceedings of the 9th International Workshop on Semantic and Social Media Adaptation and Personalization (SMAP), 6-7 November, Corfu, Greece, pp. 110 - 114, 2014.
Giannakis K., Theocharopoulou G., Papalitsas C., Andronikos T., Vlamos P., Associating ω-automata to Path Queries on Webs of Linked Data, Engineering Applications of Artificial Intelligence, Elsevier, Volume 51, May 2016, pages 115-123.
Lay, D., Linear algebra and its applications, Pearson, 2016.
Hua, M., Pei, J.: Probabilistic path queries in road networks: traffic uncertainty aware path selection. In: Proceedings of the 13th International Conference on Extending Database Technology, pp. 347–358, ACM, 2010.
Huang, H., Liu, C.: Query evaluation on probabilistic RDF databases. In: International Conference on Web Information Systems Engineering, pp. 307–320, Springer, 2009.
Szeto C., Hung E., Y. Deng, SPARQL query answering with RDFS reasoning on correlated probabilistic data, in Proceedings of the WAIM’11, pp. 56–67, 2011.
Zhang X., J. Van den Bussche, On the primitivity of operators in SPARQL, Information Processing Letters, vol. 114, no. 9, pp. 480–485, 2014.
Lian, X., Chen, L., Wang, G.: Quality-aware subgraph matching over inconsistent probabilistic graph databases. IEEE Transactions on Knowledge and Data Engineering 28(6), 1560–1574, 2016.
LOD Project, 2014. Linking Open (LOD) Data Project, http://esw.w3.org/topic/SweoIG/TaskForces/Commun ityProjects/LinkingOpenData.
Papalitsas C., Andronikos T., “Unconventional GVNS for Solving the Garbage Collection Problem with Time Windows”, (MDPI - Open Access Publishing), Technologies 2019, 7(3), 61; https://doi.org/10.3390/technologies7030061.
Papalitsas C., Andronikos T., Giannakis K., Theocharopoulou G., Fanarioti S., “A QUBO Model for the Traveling Salesman Problem with Time Windows”, (MDPI - Open Access Publishing), Algorithms 2019, 12(11), 224; https://doi.org/10.3390/a12110224.
Papalitsas C., Karakostas P., Andronikos T., “A Performance Study of the Impact of Different Perturbation Methods on the Efficiency of GVNS for Solving TSP”, (MDPI - Open Access Publishing), Applied System Innovation 2019, 2(4), 31; https://doi.org/10.3390/asi2040031.
Golub, G. H., Matrix Computations, Johns Hopkins University Press, Fourth Edition, 2013.
Banerjee, S. & Roy, A., Linear Algebra and Matrix Analysis for Statistics, Chapman and Hall/CRC, 2014. [23]Resource Description Framework (RDF),
https://www.w3.org/TR/2015/NOTE-rdfa-primer-201 50317/.
Reynolds, D.: Position paper: Uncertainty reasoning for Linked Data. In: Workshop, vol. 14, 2014. [25]Sistla, A.P., Hu, T., Chowdhry, V.: Similarity based retrieval from sequence databases using automata as queries. In: Proceedings of the eleventh international conference on Information and knowledge management, pp. 237–244, ACM, 2002.
Schmidt M., Meier M., Lausen G.: Foundations of SPARQL Query Optimization. In: Proceedings of the 13th International Conference on Database Theory (ICDT '10), pp. 4–33, Lausanne, Switzerland, 2010.
Schoenfisch, J.: Querying probabilistic ontologies with SPARQL, GI-Edition/Proceedings 232, 2245–2256, 2014.
SPARQL 1.1 Query Language. Tech. rep., W3C (2013),
https://www.w3.org/TR/2013/REC-sparql11-query-20 130321/.
Wang, X., Ling, J., Wang, J., Wang, K., Feng, Z.: Answering provenance-aware regular path queries on RDF graphs using an automata-based algorithm. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 395–396, ACM, 2014.
Zhang, X., Feng, Z., Wang, X., Rao, G., Wu, W.: Context-free path queries on RDF graphs. In: International Semantic Web Conference, pp. 632–648, Springer, 2016.
Gutierrez C., Hurtado C. A. and Vaisman A., "Introducing Time into RDF," in IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 2, pp. 207-218, Feb. 2007, doi: 10.1109/TKDE.2007.34.
Kepner J. G., Graph Algorithms in the Language of Linear Algebra Society for Industrial and Applied Mathematics, 2011.
Strang, G., Introduction to Linear Algebra, Cambridge University Press, 2016.
Erisman, A. M., Reid, J. K. and Duff, I. S., Direct Methods for Sparse Matrices, Oxford University Press; 2nd edition, 2017.
