Research and Teaching Papers
The following research papers contain material that is complementary to
the content of the course.
Sha Guo, Wei Sun, Mark Allen Weiss:
Solving Satisfiability and Implication Problems in Database
ACM Trans. Database Syst. 21(2): 270-293 (1996)
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
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