NDLI: Modular stratification and magic sets for Datalog programs with negation

Content Provider	ACM Digital Library
Author	Ross, Kenneth A.
Copyright Year	1994
Abstract	A class of “modularly stratified” logic programs is defined. Modular stratification generalizes stratification and local stratification, while allowing programs that are not expressible as stratified programs. For modularly stratified programs, the well-founded semantics coincides with the stable model semantics and makes every ground literal true or false. Modularly stratified programs are weakly stratified, but the converse is false. Unlike some weakly stratified programs, modularly stratified programs can be evaluated in a subgoal-at-a time fashion. An extension of top-down methods with memoing that handles this broader class of programs is presented. A technique for rewriting a modularly stratified program for bottom-up evaluation is demonstrated and extended to include magic-set techniques. The rewritten program, when evaluated bottom-up, gives correct answers according to the well-founded semantics, but much more efficiently than computing the complete well-founded model. A one-to-one correspondence between steps of the extended top-down method and steps during the bottom-up evaluation of the magic-rewritten program is exhibited, demonstrating that the complexity of the two methods is the same. Extensions of modular stratification to other operators such as set-grouping and aggregation, which have traditionally been stratified to prevent semantic difficulties, are discussed.
Starting Page	1216
Ending Page	1266
Page Count	51
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/195613.195646
Journal	Journal of the ACM (JACM)
Volume Number	41
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1994-11-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Deductive databases Magic sets Modular stratification Rule rewriting Stratification Well-sounded semantics
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Modular stratification and magic sets for DATALOG programs with negation

Decomposition of magic rewriting

The well-founded semantics for general logic programs

An analysis of magic sets and related optimization strategies for logic queries

Update propagation in deductive databases using soft stratification (2004)

Abstract rewriting Approach to solve Datalog programs

Aggregation and negation-as-failure

Mixed integer programming methods for computing nonmonotonic deductive databases

Deciding equivalences among conjunctive aggregate queries

Modular stratification and magic sets for Datalog programs with negation

Similar Documents

Modular stratification and magic sets for DATALOG programs with negation

Decomposition of magic rewriting

The well-founded semantics for general logic programs

An analysis of magic sets and related optimization strategies for logic queries

Update propagation in deductive databases using soft stratification (2004)

Abstract rewriting Approach to solve Datalog programs

Aggregation and negation-as-failure

Mixed integer programming methods for computing nonmonotonic deductive databases

Deciding equivalences among conjunctive aggregate queries

Modular stratification and magic sets for Datalog programs with negation