DBScholar

Back to papers

Universal Finiteness and Satisfiability

Summary: Reduce universal finiteness to satisfiability (and vice versa), so decidability/undecidability results transfer between them for Datalog variants. Define acyclicity as non‑satisfiability of a recursive program and show such acyclicity preserves decidability, while arbitrary constraints do not. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h4afd1cfed63bac5f
Venue
PODS
Year
1994
Pagerank
4.9605343e-05
Overall Rank
13,360 | 10.45%
DOI
10.1145/182591.182612

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

BibTeX Citation

@inproceedings{mumick_pods94,
        address = {New York, NY, USA},
        series = {{PODS} '94},
        title = {{Universal Finiteness and Satisfiability}},
        url = {https://dl.acm.org/doi/10.1145/182591.182612},
        doi = {10.1145/182591.182612},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Mumick, Inderpal Singh and Shmueli, Oded},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
62 Maintaining Views Incrementally 1993 SIGMOD 0.00038944207
179 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00026563438
533 The Magic of Duplicates and Aggregates 1990 VLDB 0.00016794756
1,443 Magic is Relevant 1990 SIGMOD 0.00010618161
1,842 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.5141238e-05
2,075 A Decidable Class of Bounded Recursions 1987 PODS 9.0631365e-05
2,727 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS 8.0704592e-05
3,898 Constraints and Redundancy in Datalog 1992 PODS 6.9199453e-05
4,728 Tools for Datalog Boundedness 1991 PODS 6.4324136e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,622 Modular Acyclicity and Tail Recursion in Logic Programs 1991 PODS
2 1,842 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS
3 8,702 Checking Consistency of Database Constraints: a Logical Basis 1986 VLDB
4 8,324 Decidability and Undecidability Results for the Termination Problem of Active Database Rules 1998 PODS
5 1,667 On the Decidability of Query Containment under Constraints 1998 PODS
6 2,727 Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions 1993 PODS
7 4,728 Tools for Datalog Boundedness 1991 PODS
8 6,422 Finite Queries do not Have Effective Syntax 1995 PODS
9 8,160 On the First-Order Expressibility of Recursive Queries 1989 PODS
10 6,219 Safety of Datalog Queries over Infinite Databases 1989 PODS