Phokion G. Kolaitis  Phokion G. Kolaitis photo       

contact information

Research Staff Member, Computer Science Principles & Methodologies
Almaden Research Center, San Jose, CA, USA
  +1dash408dash927dash1810

links

Professional Associations

Professional Associations:  ACM  |  ACM SIGACT  |  ACM SIGLOG  |  ACM SIGMOD  |  American Association for the Advancement of Sciences  |  Association for Symbolic Logic

more information

More information:  Phokion Kolaitis' web page at UC Santa Cruz


2009

Laconic Schema Mappings: Computing the Core with SQL Queries
Balder ten Cate, Laura Chiticariu, Phokion G. Kolaitis, Wang Chiew Tan
Proceedings of the VLDB Endowment Journal 2(1), 1006-1017, 2009

Reverse data exchange: coping with nulls
R Fagin, P G Kolaitis, L Popa, W C Tan
Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 23--32, 2009


2008


Quasi-inverses of schema mappings
R Fagin, P G Kolaitis, L Popa, W C Tan
ACM Transactions on Database Systems (TODS) 33(2), 11, ACM, 2008
US Patent App. 11/970,057


2005

Composing schema mappings: Second-order dependencies to the rescue
R Fagin, P G Kolaitis, L Popa, W C Tan
Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 994--1055, ACM, 2005


Year Unknown

Polynomial-time optimization, parallel approximation, and fixpoint logic

Structure in Complexity Theory ..., 2002 - ieeexplore.ieee.org

Exchange, Integration, and Consistency of Data: Report on the ARISE

NISR Workshop. SIGMOD ..., 2005

On the complexity of model checking and inference in minimal models

Logic Programming and Nonmotonic Reasoning, 2001 - Springer

Infinitary logic for computer science

Automata, Languages and Programming, 1992 - Springer, 0

On the boundedness problem for two-variable first-order logic

Logic in Computer Science, 1998. ..., 2002 - ieeexplore.ieee.org


On the complexity of counting the Hilbert basis of a linear Diophantine system

Logic for Programming and Automated ..., 1999 - Springer, 0


Structure identification of Boolean relations and plain bases for co-clones

Journal of Computer and System ..., 2008 - Elsevier

Implicit definability on finite structures and unambiguous computations (preliminary report)

5th Annual IEEE Symposium on Logic in Computer ..., 1990

Approximation properties of NP minimization problems

Journal of Computer and System Sciences, 1995, 0

Unification algorithms cannot be combined in polynomial time

Automated Deduction—Cade-13, 1996 - Springer, 0

Integer programming as a framework for optimization and approximability

... ., Eleventh Annual IEEE ..., 2002 - ieeexplore.ieee.org

How to de ne a linear order on finite models

9th IEEE Symposium on Logic in ..., 1994 - Citeseer, 0

Phase transitions of PP-complete satisfiability problems

Discrete Applied Mathematics, 2007 - Elsevier

A logical approach to constraint satisfaction

Complexity of Constraints, 2008 - Springer

The complexity of counting problems in equational matching

Journal of Symbolic Computation, 1995 - Elsevier, 0

Game quantification

Model-Theoretic Logics, 1985, 0

On the expressive power of logics on finite models

Finite Model Theory and its Applications, 2007 - Springer

Structural characterizations of schema-mapping languages

Communications of the ACM, 2010 - portal.acm.org

Asymptotic enumeration and a 0-1 law for m-clique free graphs

Bulletin, new series, of the ..., 1985 - cat.inist.fr, 0

The containment problem for real conjunctive queries with inequalities

Proceedings of the twenty-fifth ACM ..., 2006 - portal.acm.org

On the complexity of existential pebble games

Computer Science Logic, 2003 - Springer

First-order logic vs. fixed-point logic in finite set theory

Logic in Computer Science, 1999. ..., 2002 - ieeexplore.ieee.org

Computational complexity of simultaneous elementary matching problems

Journal of Automated Reasoning, 1999 - Springer, 0

On the complexity of the decision problem for two-variable rst-order logic

Bulletin of Symbolic Logic, 1997, 0


Repair checking in inconsistent databases: algorithms and complexity

... of the 12th International Conference on ..., 2009 - portal.acm.org

0–1 Laws for Fragments of Existential Second-Order Logic: A Survey

Mathematical Foundations of Computer Science ..., 2000 - Springer

Towards a theory of schema-mapping optimization

Proceedings of the twenty- ..., 2008 - portal.acm.org

Implicit definability and infinitary logic in finite model theory

Automata, Languages and Programming, 1995 - Springer, 0

On the expressive power of variable-confined logics

... in Computer Science, 1996. LICS'96. ..., 2002 - ieeexplore.ieee.org

Answering aggregate queries in data exchange

Proceedings of the twenty-seventh ACM ..., 2008 - portal.acm.org

Constraint satisfaction, databases, and logic

INTERNATIONAL JOINT CONFERENCE ON ..., 2003 - Citeseer

0-1 laws for fragments of second-order logic: an overview

Logic from computer science (Proc. of Workshop, 1989), 1992, 0


Semi-automatic schema integration in clio

Proceedings of the 33rd ..., 2007 - portal.acm.org


How to define a linear order on finite models

Annals of pure and applied logic, 1997 - Elsevier, 0

A dichotomy in the complexity of propositional circumscription

Theory of Computing Systems, 2004 - Springer

Can Datalog be approximated?

... of the thirteenth ACM SIGACT-SIGMOD- ..., 1994 - portal.acm.org, 0


The complexity of data exchange

... of the twenty-fifth ACM SIGMOD- ..., 2006 - portal.acm.org

Constraint propagation as a proof system

Principles and Practice of Constraint ..., 2004 - Springer


0-1 laws for infinitary logics

... in Computer Science, 1990. LICS'90, ..., 2002 - ieeexplore.ieee.org

On preservation under homomorphisms and unions of conjunctive queries

Journal of the ACM (JACM), 2006 - portal.acm.org

On the complexity of the containment problem for conjunctive queries with built-in predicates

Proceedings of the seventeenth ..., 1998 - portal.acm.org, 0

Why not negation by xpoint

Proc. ACM Symp. on Principles of Database ..., 1988, 0

Implicit definability on finite structures and unambiguous computations

Logic in Computer Science, 1990. LICS'90, ..., 2002 - ieeexplore.ieee.org

The complexity of minimal satisfiability problems* 1

Information and Computation, 2003 - ams.org

Almost everywhere equivalence of logics in finite model theory

Bulletin of Symbolic Logic, 1996 - JSTOR, 0

K_l+1-Free Graphs: Asymptotic Structure and a 0-1 Law

Transactions of the American ..., 1987 - JSTOR, 0

A game-theoretic approach to constraint satisfaction

PROCEEDINGS OF THE NATIONAL ..., 2000 - aaai.org

Some computational aspects of circumscription

Journal of the ACM (JACM), 1990 - portal.acm.org

Peer data exchange

ACM Transactions on ..., 2006 - portal.acm.org

Fixpoint logic vs. infinitary logic in finite-model theory

... in Computer Science, 1992. LICS'92., ..., 2002 - ieeexplore.ieee.org

On the unusual effectiveness of logic in computer science

Bulletin of Symbolic ..., 2001 - JSTOR

The decision problem for the probabilities of higher-order properties

Proceedings of the nineteenth annual ACM ..., 1987 - portal.acm.org, 0

Constraint satisfaction, bounded treewidth, and finite-variable logics

Principles and Practice of Constraint ..., 2006 - Springer

0-1 Laws and decision problems for fragments of second-order logic* 1

Information and Computation, 1990 - Elsevier

Generalized quantifiers and pebble games on finite structures

Annals of Pure and Applied Logic, 1995 - Elsevier, 0

Logical definability of NP optimization problems

Information and Computation, 1994 - Elsevier, 0

Approximation properties of NP minimization classes

Journal of Computer and System Sciences, 1995 - Elsevier, 0

The expressive power of stratified logic programs

Information and Computation, 1991 - portal.acm.org, 0

Infinitary logics and 0-1 laws* 1

Information and Computation, 1992 - Elsevier, 0

Schema mappings, data exchange, and metadata management

PROCEEDINGS OF THE ACM SIGACT SIGMOD ..., 2005 - Citeseer

On the expressive power of Datalog: tools and a case study

Journal of Computer and System Sciences, 1995 - Elsevier, 0

On the decision problem for two-variable first-order logic

Bulletin of Symbolic Logic, 1997 - JSTOR, 0

Why not negation by fixpoint?

Journal of Computer and System ..., 1991 - Elsevier, 0

Data exchange: getting to the core

ACM Transactions on Database ..., 2005 - portal.acm.org

Conjunctive-query containment and constraint satisfaction

... of the seventeenth ACM SIGACT-SIGMOD- ..., 1998 - portal.acm.org, 0