Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases

Authors

  • Son Thanh Cao School of Engineering and Technology, Vinh University, Vinh, Nghe An, Vietnam & Nguyen Tat Thanh University, Ho Chi Minh City, Vietnam
  • Linh Anh Nguyen Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam & Institute of Informatics, University of Warsaw, 02-097 Warsaw, Poland

DOI:

https://doi.org/10.31577/cai_2019_1_19

Keywords:

Deductive databases, datalog with negation, query processing

Abstract

Most of the previously known evaluation methods for deductive databases are either breadth-first or depth-first (and recursive). There are cases when these strategies are not the best ones. It is desirable to have an evaluation framework for stratified DatalogN that is goal-driven, set-at-a-time (as opposed to tuple-at-a-time) and adjustable w.r.t. flow-of-control strategies. These properties are important for efficient query evaluation on large and complex deductive databases. In this paper, by incorporating stratified negation into so-called query-subquery nets, we develop an evaluation framework, called QSQNSTR, with such properties for evaluating queries to stratified DatalogN databases. A variety of flow-of-control strategies can be used for QSQNSTR. The generic evaluation method QSQNSTR for stratified DatalogN is sound, complete and has a PTIME data complexity.

Downloads

Download data is not yet available.

Published

2019-04-26

How to Cite

Cao, S. T., & Nguyen, L. A. (2019). Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases. Computing and Informatics, 38(1), 19–56. https://doi.org/10.31577/cai_2019_1_19