ΠΜΣ547 ΘΕΜΕΛΙΩΣΗ ΒΑΣΕΩΝ ΔΕΔΟΜΕΝΩΝ

Εαρινό Εξάμηνο 2007

ΘΕΜΑΤΑ ΠΑΡΟΥΣΙΑΣΕΩΝ

 

  •  Relational Algebra and Relational Calculus Queries with Aggregate Functions
    • Anthony C. Klug:  Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate FunctionsJournal of  ACM 29(3):699-717 (1982)  [Download]
    • Leonid Libkin, Limsoon Wong:  Query Languages for Bags and Aggregate Functions. Journal of Computer and System Sciences 55(2): 241-272 (1997) [Download]

 

  • Constraint Databases
    • Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. Journal of Computer and System Sciences 51(1): 26-52 (1995) [Download]
    • Dina Q. Goldin, Paris C. Kanellakis: Constraint Query Algebras. Constraints Journal 1(1/2): 45-83 (1996) [Download]

 

  • Incomplete (indefinite) information in relational databases
    • Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. Journal of ACM 31(4): 761-791 (1984) [Download]
    • Serge Abiteboul, Paris C. Kanellakis, Gosta Grahne: On the Representation and Querying of Sets of Possible Worlds. Theoretical Computer Science 78(1): 158-187 (1991) [Download]

 

  • Constraints for representing infinite and indefinite information
    • Manolis Koubarakis: Database models for infinite and indefinite temporal information. Information Systems 19(2): 141-173 (1994) [Download]
    • Manolis Koubarakis: Foundations of Indefinite Constraint Databases. PPCP 1994: 266-280. [Download]
    • Manolis Koubarakis: The Complexity of Query Evaluation in Indefinite Temporal Constraint Databases. Theoretical Computer Science 171(1-2): 25-60 (1997)   [Download]                         

 

  • Relational databases vs. First-Order Logic
    • Raymond Reiter: Towards a Logical Reconstruction of Relational Database Theory. (available from Manolis)
    • Raymond Reiter: On Closed World Data Bases. (available from Manolis)
    • Raymond Reiter: Equality and Domain Closure in First-Order Databases. Journal of ACM 27(2): 235-249 (1980) [Download]

 

  • Equivalence of conjunctive queries with inequalities
    • Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160 (1988) [Download]

 

  • Equivalence of Datalog programs
    • Yehoshua Sagiv: Optimizing Datalog Programs. Foundations of Deductive Databases and Logic Programming. 1988: 659-698 [Download]
    • Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 [Download]
    • Michael J. Maher: Equivalences of Logic Programs Foundations of Deductive Databases and Logic Programming. 1988: 627-658 [Download]
    • Michael J. Maher: Equivalences of Logic Programs. ICLP 1986: 410-424 [Download]

 

  • Proof-theoretic semantics for datalog and datalog with negation (two presentations possible)
    • Section 12.4 of the book
    • John Lloyd. Foundations of Logic Programming. Springer, Berlin, Heidelberg, New York, 1987. 
    • Krzysztof R. Apt, Roland N. Bol: Logic Programming and Negation: A Survey. J. Log. Program. 19/20: 9-71 (1994) [Download]

 

  • Static analysis for datalog and extensions
    • Alon Y. Halevy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Static analysis in datalog extensions. J. ACM 48(5): 971-1012 (2001) [Download]

 

  • Logic-based Information Integration
    • Jeffrey D. Ullman: Information integration using logical views. Theor. Comput. Sci. 239(2): 189-210 (2000) [Download]
    • Maurizio Lenzerini: Data Integration: A Theoretical Perspective. PODS 2002: 233-246 [Download] [slides]

 

  • Semantic query optimization
    • Upen S. Chakravarthy, John Grant, Jack Minker: Logic-Based Approach to Semantic Query Optimization. ACM Trans. Database Syst. 15(2): 162-207 (1990) [Download]
    • Sreekumar T. Shenoy, Z. Meral Özsoyoglu: Design and Implementation of a Semantic Query Optimizer. IEEE Trans. Knowl. Data Eng. 1(3): 344-361 (1989) [Download]

 

  • Query optimization for Datalog (bottom up methods)
    • Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299 (1991) [Download]
    • Chapters 13 of Ullman (second volume).

 

  • Query optimization for Datalog (top-down methods)
    • Laurent Vieille: Recursive Query Processing: The Power of Logic. Theor. Comput. Sci. 69(1): 1-53 (1989) [Download]
    • Chapters 12 of Ullman (second volume).

 

  • Presentation of any interesting topic covered in one of the following book chapters: 20, 21 or 22.