Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases
Son Thanh Cao; Faculty of Information Technology, Vinh University ; Linh Anh Nguyen; Institute of Informatics, University of Warsaw
Computing and Informatics, Tome 37 (2019) no. 6, / Harvested from Computing and Informatics
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.
Publié le : 2019-04-26
Classification:  Knowledge and Information Engineering,  Deductive databases, datalog with negation, query processing,  68N17; 68P15
@article{cai2019_1_19,
     author = {Son Thanh Cao; Faculty of Information Technology, Vinh University and Linh Anh Nguyen; Institute of Informatics, University of Warsaw},
     title = {Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases},
     journal = {Computing and Informatics},
     volume = {37},
     number = {6},
     year = {2019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai2019_1_19}
}
Son Thanh Cao; Faculty of Information Technology, Vinh University; Linh Anh Nguyen; Institute of Informatics, University of Warsaw. Incorporating Stratified Negation into Query-Subquery Nets for Evaluating Queries to Stratified Deductive Databases. Computing and Informatics, Tome 37 (2019) no. 6, . http://gdmltest.u-ga.fr/item/cai2019_1_19/