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
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.
Carles Farré, Werner Nutt, Ernest Teniente, Toni Urpí:
Containment of Conjunctive Queries over Databases with Null Values,
Proc. Int. Conf. Database Theory (ICDT 2007)
In this paper there is a proof of the complexity of containment in the presence of predicates and
Back to the course home page