Research and Teaching Papers
The following research papers contain material that is complementary to
the content of the course.
Stephen G. Simpson,
Theorems of Church and Trakhtenbrot,
Material for Course "Math 557: Mathematical Logic" at Penn State University
Alan M. Turing,
On Computable Numbers, with an Application to the Entscheidungsproblem,
Proceedings of the London Mathematical Society, Series 2, 42 (1936-7), pp 230-265
Sha Guo, Wei Sun, Mark Allen Weiss:
Solving Satisfiability and Implication Problems in Database
ACM Trans. Database Syst. 21(2): 270-293 (1996)
Ashok Chandra, Philip Merlin,
Optimal Implementation of Conjunctive Queries in Relational Databases,
9th Annual ACM Symposium on Theory of Computing, 77-90 (1977)
This is the classical paper that laid the foundation for the theory of equivalence, containment, and minimization of conjunctive queries.
Sara Cohen, Werner Nutt, Yehoshua Sagiv:
Deciding Equivalences among Conjunctive Aggregate Queries,
J. ACM 54(2): (2007)
The paper contains, among other things, a formal characterization of containment among conjunctive
queries with comparisons
and proves characterizations of the equivalence of conjunctive queries
under bag-set semantics.
Tomasz Imielinski, Witold Lipski:
Incomplete Information in Relational Databases,
J. ACM 31(4): (1984)
The paper introduces Codd, v, and c-tables and defines weak and strong representation systems.
Werner Nutt, Sergey Paramonov, Ognjen Savkovic:
Implementing Query Completeness Reasoning,
Proc. of the Conference on Information and Knowledge Management (CIKM) 2015
The paper presents our model for reasoning about incomplete information and its implementation in disjunctive datalog.
Ron van der Meyden:
The Complexity of Querying Indefinite Data about Linearly Ordered Domains,
J. of Computer and System Sciences (JCSS) 54(1): 113-135 (1997)
In this paper there is the first proof of the complexity of containment of queries with comparisons.
Back to the course home page