On the Feasibility of Handling Uncertainty in SPARQL Queries in the Case of Sparse Graphs

Authors

  • Theodore Andronikos Associate Professor, Department of Informatics, Ionian University, 7 Tsirigoti Square, Corfu, Greece Author

Keywords:

RDF graph, SPARQL query, probabilistic SPARQL query, sparse matrices, probabilistic matrices

Abstract

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

Download data is not yet available.

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.

Downloads

Published

2020-11-30

Issue

Vol. 8 No. 6 (2020): International Journal of Innovative Research in Computer Science and Technology (Nov) 2020

Section

Articles

How to Cite

On the Feasibility of Handling Uncertainty in SPARQL Queries in the Case of Sparse Graphs . (2020). International Journal of Innovative Research in Computer Science & Technology, 8(6), 396–402. Retrieved from https://acspublisher.com/journals/index.php/ijircst/article/view/13037