Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-18T04:20:43.187Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient Computation of the Well-Founded Semantics over Big Data

Published online by Cambridge University Press:  21 July 2014

ILIAS TACHMAZIDIS ,
GRIGORIS ANTONIOU  and
WOLFGANG FABER
ILIAS TACHMAZIDIS
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected])
GRIGORIS ANTONIOU
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected])
WOLFGANG FABER
Affiliation:
University of Huddersfield, UK (e-mail: [email protected], [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Data originating from the Web, sensor readings and social media result in increasingly huge datasets. The so called Big Data comes with new scientific and technological challenges while creating new opportunities, hence the increasing interest in academia and industry. Traditionally, logic programming has focused on complex knowledge structures/programs, so the question arises whether and how it can work in the face of Big Data. In this paper, we examine how the well-founded semantics can process huge amounts of data through mass parallelization. More specifically, we propose and evaluate a parallel approach using the MapReduce framework. Our experimental results indicate that our approach is scalable and that well-founded semantics can be applied to billions of facts. To the best of our knowledge, this is the first work that addresses large scale nonmonotonic reasoning without the restriction of stratification for predicates of arbitrary arity.

Keywords

Well-Founded SemanticsBig DataMapReduce Framework
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 445 - 459
Copyright
Copyright © Cambridge University Press 2014 

References

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley.Google Scholar
Afrati, F. N. and Ullman, J. D. 2010. Optimizing joins in a map-reduce environment. In EDBT, Manolescu, I., Spaccapietra, S., Teubner, J., Kitsuregawa, M., Léger, A., Naumann, F., Ailamaki, A., and Özcan, F., Eds. ACM International Conference Proceeding Series, vol. 426. ACM, 99–110.Google Scholar
Brass, S., Dix, J., Freitag, B., and Zukowski, U. 2001. Transformation-based bottom-up computation of the well-founded model. Theory and Practice of Logic Programming 1, 5, 497–538.Google Scholar
Cluet, S. and Moerkotte, G. 1994. Classification and optimization of nested queries in object bases. Tech. rep.Google Scholar
Dean, J. and Ghemawat, S. 2004. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation - Volume 6. USENIX Association, Berkeley, CA, USA, 10–10.Google Scholar
Fensel, D., van Harmelen, F., Andersson, B., Brennan, P., Cunningham, H., Valle, E. D., Fischer, F., Huang, Z., Kiryakov, A., il Lee, T. K., Schooler, L., Tresp, V., Wesner, S., Witbrock, M., and Zhong, N. 2008. Towards LarKC: A Platform for Web-Scale Reasoning. In ICSC. 524–529.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., and Schnor, B. 2011. Cluster-based asp solving with claspar. In Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings, Delgrande, J. P. and Faber, W., Eds. Lecture Notes in Computer Science, vol. 6645. 364–369.Google Scholar
Gelder, A. V., Ross, K. A., and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3, 620–650.Google Scholar
Gelfond, M. 2008. Chapter 7 answer sets. In Handbook of Knowledge Representation, van Harmelen, V. L. F. and Porter, B., Eds. Foundations of Artificial Intelligence, vol. 3. Elsevier, 285–316.CrossRefGoogle Scholar
Goodman, E. L., Jimenez, E., Mizell, D., Al-Saffar, S., Adolf, B., and Haglin, D. J. 2011. High-performance computing applied to semantic databases. In ESWC (2), Antoniou, G., Grobelnik, M., Simperl, E. P. B., Parsia, B., Plexousakis, D., Leenheer, P. D., and Pan, J. Z., Eds. Lecture Notes in Computer Science, vol. 6644. Springer, 31–45.Google Scholar
Konstantinidis, G., Flouris, G., Antoniou, G., and Christophides, V. 2008. A Formal Approach for RDF/S Ontology Evolution. In ECAI, Ghallab, M., Spyropoulos, C. D., Fakotakis, N., and Avouris, N. M., Eds. Frontiers in Artificial Intelligence and Applications, vol. 178. IOS Press, 70–74.Google Scholar
Kotoulas, S., Oren, E. and van Harmelen, F. 2010. Mind the data skew: distributed inferencing by speeddating in elastic regions. In WWW, Rappa, M., Jones, P., Freire, J., and Chakrabarti, S., Eds. ACM, 531–540.Google Scholar
Liang, S., Fodor, P., Wan, H., and Kifer, M. 2009. Openrulebench: an analysis of the performance of rule engines. In Proceedings of the 18th international conference on World wide web. WWW '09. ACM, New York, NY, USA, 601–610.CrossRefGoogle Scholar
Liu, C., Qi, G., Wang, H., and Yu, Y. 2011. Large scale fuzzy pD* reasoning using mapreduce. In Proceedings of the 10th international conference on The semantic web - Volume Part I. ISWC'11. Springer-Verlag, Berlin, Heidelberg, 405–420.Google Scholar
Liu, C., Qi, G., Wang, H., and Yu, Y. 2012. Reasoning with Large Scale Ontologies in fuzzy pD* Using MapReduce. IEEE Comp. Int. Mag. 7, 2, 54–66.CrossRefGoogle Scholar
Mutharaju, R., Maier, F., and Hitzler, P. 2010. A MapReduce Algorithm for EL+. In Description Logics.Google Scholar
Nicolas, J.-M. 1982. Logic for improving integrity checking in relational data bases. Acta Informatica 18, 227–253.Google Scholar
Oren, E., Kotoulas, S., Anadiotis, G., Siebes, R., ten Teije, A., and van Harmelen, F. 2009. Marvin: Distributed reasoning over large-scale Semantic Web data. J. Web Sem. 7, 4, 305–316.Google Scholar
Perri, S., Ricca, F., and Sirianni, M. 2013. Parallel instantiation of asp programs: techniques and experiments. Theory and Practice of Logic Programming 13, 2, 253–278.Google Scholar
Roussakis, Y., Flouris, G., and Christophides, V. 2011. Declarative Repairing Policies for Curated KBs. In HDMS.Google Scholar
Soma, R. and Prasanna, V. K. 2008. Parallel Inferencing for OWL Knowledge Bases. In ICPP. IEEE Computer Society, 75–82.Google Scholar
Tachmazidis, I. and Antoniou, G. 2013. Computing the Stratified Semantics of Logic Programs over Big Data through Mass Parallelization. In RuleML, Morgenstern, L., Stefaneas, P. S., Lévy, F., Wyner, A., and Paschke, A., Eds. Lecture Notes in Computer Science, vol. 8035. Springer, 188–202.Google Scholar
Tachmazidis, I., Antoniou, G., Flouris, G., and Kotoulas, S. 2012. Towards Parallel Nonmonotonic Reasoning with Billions of Facts. In KR, Brewka, G., Eiter, T., and McIlraith, S. A., Eds. AAAI Press.Google Scholar
Tachmazidis, I., Antoniou, G., Flouris, G., Kotoulas, S., and McCluskey, L. 2012. Large-scale Parallel Stratified Defeasible Reasoning. In ECAI, Raedt, L. D., Bessière, C., Dubois, D., Doherty, P., Frasconi, P., Heintz, F., and Lucas, P. J. F., Eds. Frontiers in Artificial Intelligence and Applications, vol. 242. IOS Press, 738–743.Google Scholar
Urbani, J., Kotoulas, S., Massen, J., van Harmelen, F., and Bal, H. 2012. Webpie: A Web-scale parallel inference engine using MapReduce. Web Semantics: Science, Services and Agents on the World Wide Web 10, 0.Google Scholar
Supplementary material: PDF

TACHMAZIDIS et al.

Efficient Computation of the Well-Founded Semantics over Big Data

Download TACHMAZIDIS et al.(PDF)
PDF 86.2 KB