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

Year, pages: 2019, 19 - 56

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.

Cao, S., Nguyen, L. 2019. Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases. In Computing and Informatics, vol. 38, no.1, pp. 19-56. 1335-9150. DOI: https://doi.org/10.31577/cai_2019_1_19

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

Publisher: Ústav informatiky SAV