{"id":4865,"date":"2022-05-08T14:24:06","date_gmt":"2022-05-08T06:24:06","guid":{"rendered":"http:\/\/tsinghualogic.net\/JRC\/?page_id=4865"},"modified":"2022-07-01T19:11:19","modified_gmt":"2022-07-01T11:11:19","slug":"logic-data-and-incomplete-information","status":"publish","type":"page","link":"http:\/\/tsinghualogic.net\/JRC\/logic-data-and-incomplete-information\/","title":{"rendered":"Logic, Data, and Incomplete Information"},"content":{"rendered":"\n

Lecturer<\/h3>\n\n\n\n

Phokion G.Kolaitis<\/a> \uff08University of California Santa Cruz & IBM Research\uff09<\/p>\n\n\n\n

Time<\/h3>\n\n\n\n

Beijing Time:  9:50 am ~12:15 am<\/p>\n\n\n\n

Venue<\/h3>\n\n\n\n

on Tsinghua campus: to be announced<\/p>\n\n\n\n

Zoom: to be announced<\/p>\n\n\n\n

Course Description:<\/strong><\/h3>\n\n\n\n

During the past fifty years, first-order logic and its variants have been successfully used as a database query language. In traditional applications, the data at hand are assumed to be unambiguous and consistent, which implies that queries (specified in some logical formalism) are posed on a well-defined complete and consistent database. In more recent applications, however, the data may be incomplete, inconsistent, or uncertain. This state of affairs necessitates the introduction and study of the certain answers of database queries, which is an alternative semantics that takes the incompleteness, inconsistency, or uncertainty of the data into account. Intuitively, the certain answers to a query are obtained by first evaluating the query on each \u201ccompletion\u201d of the given incomplete database and then aggregating the answers obtained over all these \u201ccompletions\u201d. The aim of this course is to examine the semantics and the algorithmic aspects of the certain answers to queries in four different such contexts, namely, in the contexts of data exchange and integration, inconsistent databases, probabilistic databases, and voting with partial preferences.    <\/p>\n\n\n\n

Course Outline<\/h3>\n\n\n\n


Lecture 1: Overview of Database Query Languages and Computational Complexity<\/h5>\n\n\n\n

The relational data model; first-order logic as a database query language; conjunctive queries and unions of conjunctive queries; the query evaluation problem; data complexity and combined complexity; algorithmic aspects of conjunctive query evaluation.<\/p>\n\n\n\n


Lecture 2: Schema Mappings, Data Exchange and Integration, Certain Answers<\/h5>\n\n\n\n

Database dependencies and schema mappings; solutions and universal solutions in data exchange and data integration; certain answers and possible answers of queries in data exchange and data integration; algorithmic aspects of the certain answers of conjunctive queries in data exchange and data integration.<\/p>\n\n\n\n


Lecture 3: Inconsistent Databases and Consistent Answers<\/h5>\n\n\n\n

Managing inconsistency in databases using logic; integrity constraints and database repairs; consistent answers of queries; trichotomy theorems for the computational complexity of the consistent answers of conjunctive queries.<\/p>\n\n\n\n


Lecture 4: Probabilistic Databases and Query Answering<\/h5>\n\n\n\n

Modeling uncertainty in data using probabilistic databases; the tuple-independence model for probabilistic databases; semantics of queries on probabilistic databases; dichotomy theorems for the computational complexity of conjunctive-query evaluation on probabilistic databases.<\/p>\n\n\n\n


Lecture 5: Voting with Partial Preferences, Necessary and Possible Winners<\/h5>\n\n\n\n

Social choice and voting rules; modeling incomplete information about voting preferences using partial orders; necessary winners and possible winners; enriching voting with relational database context; necessary answers and possible answers to queries on election databases, and their computational complexity.<\/p>\n\n\n\n

<\/p>\n\n\n\n

Background Knowledge<\/h3>\n\n\n\n

The material covered in this course is in the interface between mathematical logic, algorithms, computational complexity, and relational databases. The goal is to make this material accessible to a broad audience, but some familiarity with at least some of the following topics is desirable:<\/p>\n\n\n\n

Mathematical Logic:<\/strong> Familiarity with the syntax and the semantics of first-order logic. For example, Chapter 2 of the textbook A Mathematical Introduction to Logic by H.B. Enderton is a very good source.<\/p>\n\n\n\n

Algorithms and Computational Complexity:<\/strong> Familiarity with the notions of the running time of algorithms, worst-case complexity, and a basic knowledge of NP-completeness. For example, Chapters 1 and 2 of the monograph Computers and Intractability: A Guide to the Theory of NP-Completeness by M.R. Carey and D.S. Johnson is a very good source.<\/p>\n\n\n\n

Relational Databases:<\/strong> Familiarity with the notion of the relational data model, database queries, and database query languages. For example, Chapter 3 of the textbook Database Systems Concepts by A. Silberschatz, H.F. Korth, and S. Sudarshan is a very good source (but so is any other standard textbook on relational databases).<\/p>\n\n\n\n

<\/p>\n\n\n\n

Slides<\/h3>\n\n\n\n
  1. Lecture 1<\/a><\/li>
  2. Lecture 2<\/a><\/li>
  3. Lecture 3<\/a><\/li>
  4. Lecture 4<\/a><\/li>
  5. Lecture 5<\/a><\/li><\/ol>\n\n\n\n

    Home Assignments<\/h3>\n\n\n\n

    (Submit to haoxuan_yin@foxmail.com)<\/p>\n\n\n\n

    1. The first assignment<\/a> (due: before the class on Wednesday, June 29th) solution<\/a><\/li>
    2. The second assignment<\/a> (due: before the class on Thursday, June 30th)<\/li>
    3. The third assignment<\/a> (due: before the class on Friday, July 1st)<\/li>
    4. Take-home exam<\/a> (due: before 12:00 pm of Sunday, July 3rd)<\/li><\/ol>\n\n\n\n

      General References<\/h3>\n\n\n\n
      • Foundations of Databases<\/em> by S. Abiteboul, R. Hull, V. Vianu, Addison-Wesley<\/li><\/ul>\n\n\n\n

        The standard reference for database theory. Free copy available at http:\/\/webdam.inria.fr\/Alice\/<\/p>\n\n\n\n

        • Computers and Intractability: A Guide to the Theory of NP-Completeness<\/em> by M.R. Garey and D.S Johnson, W. H. Freeman 1979.<\/li><\/ul>\n\n\n\n

          The by-now classical introduction to NP-completeness.<\/p>\n\n\n\n

          • Computational Complexity: A Modern Approach<\/em> by S. Arora and B. Barak, Cambridge University Press<\/li><\/ul>\n\n\n\n

            A comprehensive textbook on modern computational complexity. Free copy of an almost final draft available at https:\/\/theory.cs.princeton.edu\/complexity\/book.pdf<\/p>\n\n\n\n

            • Foundations of Data Exchange<\/em> by M. Arenas, P. Barcel\u00f3, L. Libkin, F. Murlak, Cambridge University Press<\/li><\/ul>\n\n\n\n

              A comprehensive overview of data exchange and query answering in the context of data exchange.<\/p>\n\n\n\n

              • Data Exchange, Integration, and Streams<\/em>, edited by Ph.G. Kolaitis, M. Lenzerini, and N.Schweikardt, Dagstuhl Follow-Ups 5, Schloss Dagstuhl – Leibniz-Zentrum f\u00fcr Informatik, 2013.<\/li><\/ul>\n\n\n\n

                An open-access collection of chapters with topics on data exchange, data integration, and data streams.<\/p>\n\n\n\n

                • Database Repairing and Consistent Query Answering<\/em> by L. Bertossi, Synthesis Lectures on Data Management, Morgan & Claypool Publishers<\/li><\/ul>\n\n\n\n

                  A comprehensive survey of query answering over inconsistent databases.<\/p>\n\n\n\n

                  • Probabilistic Databases<\/em>, by D. Suciu, D. Olteanu, C. R\u00e9, C. Koch, Synthesis Lectures on Data Management, Morgan & Claypool Publishers<\/li><\/ul>\n\n\n\n

                    A comprehensive survey of query answering over probabilistic databases.<\/p>\n\n\n\n

                    • Handbook of Computational Social Choice<\/em> by F. Brandt, V. Conitzer, U. Endriss, J. Lang, A.D. Procaccia, Cambridge University Press.<\/li><\/ul>\n\n\n\n

                      The standard reference for comprehensive surveys of topics in computational social choice; Chapter 1 and Chapter 10 are the most relevant for this course.<\/p>\n","protected":false},"excerpt":{"rendered":"

                      Lecturer Phokion G.Kolaitis \uff08University of California S […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/4865"}],"collection":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/comments?post=4865"}],"version-history":[{"count":11,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/4865\/revisions"}],"predecessor-version":[{"id":5040,"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/pages\/4865\/revisions\/5040"}],"wp:attachment":[{"href":"http:\/\/tsinghualogic.net\/JRC\/wp-json\/wp\/v2\/media?parent=4865"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}