Leonid Libkin

According to our database1, Leonid Libkin authored at least 193 papers between 1989 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 2012, "For contributions to finite model theory and database theory.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
TriAL: A Navigational Algebra for RDF Triplestores.
ACM Trans. Database Syst., 2018

Research Directions for Principles of Data Management (Dagstuhl Perspectives Workshop 16151).
Dagstuhl Manifestos, 2018

Cypher: An Evolving Query Language for Property Graphs.
Proceedings of the 2018 International Conference on Management of Data, 2018

Certain Answers Meet Zero-One Laws.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

An Operational Approach to Consistent Query Answering.
Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Propositional and Predicate Logics of Incomplete Information.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, 2018

Approximating Certainty in Querying Data and Metadata.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, 2018

Explainable Certain Answers.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

How Standard is the SQL Standard?
Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, 2018

An Operational Approach to Consistent Query Answering.
Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, 2018

2017
Correctness of SQL Queries on Databases with Nulls.
SIGMOD Record, 2017

A Formal Semantics of SQL Queries, Its Validation, and Applications.
PVLDB, 2017

20th workshop on logic, language, information and computation - WoLLIC 2013.
J. Comput. Syst. Sci., 2017

Technical Perspective: Data distribution for fast joins.
Commun. ACM, 2017

The VADA Architecture for Cost-Effective Data Wrangling.
Proceedings of the 2017 ACM International Conference on Management of Data, 2017

2017 ACM PODS Alberto O. Mendelzon Test-of-Time Award.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

Schema Mappings for Data Graphs.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

On Querying Incomplete Information in Databases under Bag Semantics.
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017

Data context informed data wrangling.
Proceedings of the 2017 IEEE International Conference on Big Data, BigData 2017, 2017

On the Codd Semantics of SQL Nulls.
Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, 2017

2016
Technical Perspective: Data Distribution for Fast Joins.
SIGMOD Record, 2016

Research Directions for Principles of Data Management (Abridged).
SIGMOD Record, 2016

Querying Graphs with Data.
J. ACM, 2016

Order-Invariant Types and Their Applications.
Logical Methods in Computer Science, 2016

Negative Knowledge for Certain Query Answers.
Proceedings of the Web Reasoning and Rule Systems - 10th International Conference, 2016

Making SQL Queries Correct on Incomplete Databases: A Feasibility Study.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Approximations and Refinements of Certain Answers via Many-Valued Logics.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth International Conference, 2016

Data Wrangling for Big Data: Challenges and Opportunities.
Proceedings of the 19th International Conference on Extending Database Technology, 2016

2015
Certain Answers over Incomplete XML Documents: Extending Tractability Boundary.
Theory Comput. Syst., 2015

Regular expressions for data words.
J. Comput. Syst. Sci., 2015

SQL's Handling of Nulls: Can It Be Fixed?
Proceedings of the 23rd Italian Symposium on Advanced Database Systems, 2015

Path Logics for Querying Graphs: Combining Expressiveness and Efficiency.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

How to Define Certain Answers.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

SQL's Three-Valued Logic and Certain Answers.
Proceedings of the 18th International Conference on Database Theory, 2015

2014
Naïve Evaluation of Queries over Incomplete Databases.
ACM Trans. Database Syst., 2014

Querying Regular Graph Patterns.
J. ACM, 2014

XML Schema Mappings: Data Exchange and Metadata Management.
J. ACM, 2014

Synchronizing Relations on Words.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

Incomplete data: what went wrong, and how to fix it.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

On scale independence for querying big data.
Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Certain Answers as Objects and Knowledge.
Proceedings of the Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, 2014

Pattern logics and auxiliary relations.
Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

Foundations of Data Exchange
Cambridge University Press, ISBN: 9781107016163, 2014

2013
Parameterized regular expressions and their languages.
Theor. Comput. Sci., 2013

Solutions and query rewriting in data exchange.
Inf. Comput., 2013

Graph Logics with Rational Relations
Logical Methods in Computer Science, 2013

Reasoning About Pattern-Based XML Queries.
Proceedings of the Web Reasoning and Rule Systems - 7th International Conference, 2013

Trial for RDF: adapting graph query languages for RDF data.
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

When is naive evaluation possible?
Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Querying graph databases with XPath.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Containment of pattern-based queries over data trees.
Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

Regular Expressions with Binding over Data Words for Querying Graph Databases.
Proceedings of the Developments in Language Theory - 17th International Conference, 2013

Static Analysis and Query Answering for Incomplete Data Trees with Constraints.
Proceedings of the In Search of Elegance in the Theory and Practice of Computation, 2013

2012
Expressive Languages for Path Queries over Graph-Structured Data.
ACM Trans. Database Syst., 2012

Efficient approximations of conjunctive queries.
Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Regular Expressions for Data Words.
Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2012

Graph Logics with Rational Relations and the Generalized Intersection Problem.
Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, 2012

Regular path queries on graphs with data.
Proceedings of the 15th International Conference on Database Theory, 2012

On the complexity of query answering over incomplete XML documents.
Proceedings of the 15th International Conference on Database Theory, 2012

On Low Treewidth Approximations of Conjunctive Queries.
Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, 2012

2011
Closed world data exchange.
ACM Trans. Database Syst., 2011

Incomplete information and certain answers in general data models.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Querying graph patterns.
Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2011

Efficient reasoning about data trees via integer linear programming.
Proceedings of the Database Theory, 2011

Parameterized Regular Expressions and Their Languages.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Tractable XML data exchange via relations.
Proceedings of the 20th ACM Conference on Information and Knowledge Management, 2011

A Direct Translation from XPath to Nondeterministic Automata.
Proceedings of the 5th Alberto Mendelzon International Workshop on Foundations of Data Management, 2011

2010
Relational and XML Data Exchange
Synthesis Lectures on Data Management, Morgan & Claypool Publishers, 2010

An information-theoretic analysis of worst-case redundancy in database design.
ACM Trans. Database Syst., 2010

XML with incomplete information.
J. ACM, 2010

Disjoint pattern matching and implication in strings.
Inf. Process. Lett., 2010

Certain answers for XML queries.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

Expressive languages for path queries over graph-structured data.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

On the Satisfiability of Two-Variable Logic over Data Words.
Proceedings of the Logic for Programming, Artificial Intelligence, and Reasoning, 2010

On the aggregation problem for synthesized web services.
Proceedings of the Database Theory, 2010

On the tradeoff between mapping and querying power in XML data exchange.
Proceedings of the Database Theory, 2010

Algorithmic Metatheorems for Decidable LTL Model Checking over Infinite Systems.
Proceedings of the Foundations of Software Science and Computational Structures, 2010

On Incomplete XML Documents with Integrity Constraints.
Proceedings of the 4th Alberto Mendelzon International Workshop on Foundations of Data Management, 2010

2009
Expressive Power of Query Languages.
Proceedings of the Encyclopedia of Database Systems, 2009

Introduction to PODS 2007 special section.
J. ACM, 2009

The finite model theory toolbox of a database theoretician.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

XML with incomplete information: models, properties, and query answering.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

XML schema mappings.
Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Open and Closed World Assumptions in Data Exchange.
Proceedings of the 22nd International Workshop on Description Logics (DL 2009), 2009

2008
Introduction to the PODS 2007 special section.
ACM Trans. Database Syst., 2008

On the Complexity of Verifying Consistency of XML Specifications.
SIAM J. Comput., 2008

Data exchange and schema mappings in open and closed worlds.
Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2008

Recurrent Reachability Analysis in Regular Model Checking.
Proceedings of the Logic for Programming, 2008

Reasoning about XML with Temporal Logics and Automata.
Proceedings of the Logic for Programming, 2008

2007
Finite Model Theory and Its Applications
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-540-68804-4, 2007

Logical definability and query languages over ranked and unranked trees.
ACM Trans. Comput. Log., 2007

Preface.
Theor. Comput. Sci., 2007

Normalization Theory for XML.
Proceedings of the Database and XMLTechnologies, 5th International XML Database Symposium, 2007

XML design for relational storage.
Proceedings of the 16th International Conference on World Wide Web, 2007

First-Order and Temporal Logics for Nested Words.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Combining Temporal Logics for Querying XML Documents.
Proceedings of the Database Theory, 2007

Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
Introduction to special ICDT section.
ACM Trans. Database Syst., 2006

Locality of Queries and Transformations.
Electr. Notes Theor. Comput. Sci., 2006

Embedded Finite Models.
Bulletin of the EATCS, 2006

Data exchange and incomplete information.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

On redundancy vs dependency preservation in normalization: an information-theoretic study of 3NF.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

2005
XML data exchange: consistency and query answering.
Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2005

Temporal Logics over Unranked Trees.
Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

Logics for Unranked Trees: An Overview.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Consistency of XML Specifications.
Proceedings of the Inconsistency Tolerance [result from a Dagstuhl seminar], 2005

2004
Locally Consistent Transformations and Query Answering in Data Exchange.
Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Efficient Incremental Validation of XML Documents.
Proceedings of the 20th International Conference on Data Engineering, 2004

Game-Based Notions of Locality Over Finite Models.
Proceedings of the Computer Science Logic, 18th International Workshop, 2004

Elements of Finite Model Theory
Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-07003-1, 2004

2003
Variable independence for first-order definable constraints.
ACM Trans. Comput. Log., 2003

Definable relations and first-order query languages over strings.
J. ACM, 2003

A collapse result for constraint queries over structures of small degree.
Inf. Process. Lett., 2003

Incremental recomputation in local languages.
Inf. Comput., 2003

An information-theoretic approach to normal forms for relational and XML data.
Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

Logical Definability and Query Languages over Unranked Trees.
Proceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 2003

2002
Editorial.
ACM Trans. Comput. Log., 2002

Lower bounds for invariant queries in logics with counting.
Theor. Comput. Sci., 2002

Aggregate Operators in Constraint Query Languages.
J. Comput. Syst. Sci., 2002

A Normal Form for XML Documents.
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

On Verifying Consistency of XML Specifications.
Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2002

Tree Extension Algebras: Logics, Automata, and Query Languages.
Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

What's Hard about XML Schema Constraints?
Proceedings of the Database and Expert Systems Applications, 13th International Conference, 2002

2001
Reminiscences on Influential Papers.
SIGMOD Record, 2001

On the orthographic dimension of definable sets.
Inf. Process. Lett., 2001

On XML Integrity Constraints in the Presence of DTDs.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

String Operations in Query Languages.
Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

A Model-Theoretic Approach to Regular String Relations.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

Expressive Power of SQL.
Proceedings of the Database Theory, 2001

2000
Logics with counting and local properties.
ACM Trans. Comput. Log., 2000

Relational queries over interpreted structures.
J. ACM, 2000

Logics Capturing Local Properties.
Proceedings of the STACS 2000, 2000

Reachability and Connectivity Queries in Constraint Databases.
Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000

Variable Independence, Quantifier Elimination, and Constraint Representations.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Introduction.
Constraint Databases, 2000

Aggregate Languages for Constraint Databases.
Constraint Databases, 2000

Query Safety with Constraints.
Constraint Databases, 2000

Expressive Power: The Finite Case.
Constraint Databases, 2000

1999
Database Principles Column - Introduction.
SIGMOD Record, 1999

Some Remarks on Variable Independence, Closure, and Orthographic Dimension in Constraint Databases.
SIGMOD Record, 1999

Query languages with arithmetic and constraint databases.
SIGACT News, 1999

Notions of Locality and Their Logical Characterizations over Finite Models.
J. Symb. Log., 1999

Exact and Approximate Aggregation in Constraint Query.
Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31, 1999

Logics with Counting, Auxiliary Relations, and Lower Bounds for Invariant Queries.
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

Logics with Aggregate Operators.
Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999

On the Power of Incremental Evaluation in SQL-Like Languages.
Proceedings of the Research Issues in Structured and Semistructured Database Programming, 1999

What you can and cannot say in SQL or proving folk theorems in database theory.
Proc. 15èmes Journées Bases de Données Avancées, BDA, 1999

1998
Models of Approximation in Databases.
Theor. Comput. Sci., 1998

Unary Quantifiers, Transitive Closure, and Relations of Large Degree.
Proceedings of the STACS 98, 1998

Safe Constraint Queries.
Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1998

On Counting Logics and Local Properties.
Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science, 1998

1997
An Improved Algorithm for the Incremental Recomputation of Active Relational Expressions.
IEEE Trans. Knowl. Data Eng., 1997

Query Languages for Bags and Aggregate Functions.
J. Comput. Syst. Sci., 1997

Languages for Relational Databases over Interpreted Structures.
Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1997

On the Forms of Locality over Finite Models.
Proceedings of the Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, June 29, 1997

Local Properties of Query Languages.
Proceedings of the Database Theory, 1997

Tractable Iteration Mechanisms for Bag Languages.
Proceedings of the Database Theory, 1997

Counting and Locality over Finite Structures: A Survey.
Proceedings of the Generalized Quantifiers and Computation, 1997

Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions.
Proceedings of the Database Programming Languages, 6th International Workshop, 1997

On the Power of Aggregation in Relational Query Languages.
Proceedings of the Database Programming Languages, 6th International Workshop, 1997

1996
Query languages for bags: expressive power and complexity.
SIGACT News, 1996

Semantic Representations and Query Labguages for Or-Sets.
J. Comput. Syst. Sci., 1996

A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques.
Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 1996

Algorithms for Deferred View Maintenance.
Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 1996

Verifiable Properties of Database Transactions.
Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1996

Relational Expressive Power of Constraint Query Languages.
Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1996

On the Structure of Queries in Constraint Query Languages.
Proceedings of the Proceedings, 1996

1995
On Representation and Querying Incomplete Information in Databases with Bags.
Inf. Process. Lett., 1995

Trees as semilattices.
Discrete Mathematics, 1995

Interfacing HOL90 with a Functional Database Query Language.
Proceedings of the Higher Order Logic Theorem Proving and Its Applications, 1995

Incremental Maintenance of Views with Duplicates.
Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, 1995

A Semantics-based Approach to Design of Query Languages for Partial Information.
Proceedings of the Semantics in Databases, 1995

Normalizing Incomplete Databases.
Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1995

Approximation in Databases.
Proceedings of the Database Theory, 1995

Query Language Primitives for Programming with Incomplete Databases.
Proceedings of the Database Programming Languages (DBPL-5), 1995

On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL.
Proceedings of the Database Programming Languages (DBPL-5), 1995

1994
Comprehension Syntax.
SIGMOD Record, 1994

Conservativity of Nested Relational Calculi with Internal Generic Functions.
Inf. Process. Lett., 1994

New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions.
Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1994

OR-SML: A Functional Database Programming Language for Disjunctive Information and Its Applications.
Proceedings of the Database and Expert Systems Applications, 5th International Conference, 1994

1993
Direct product decompositions of lattices, closures and relation schemes.
Discrete Mathematics, 1993

Semantic Representations and Query Languages for Or-sets.
Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1993

Aggregate Functions, Conservative Extensions, and Linear Orders.
Proceedings of the Database Programming Languages (DBPL-4), Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, Manhattan, New York City, USA, 30 August, 1993

Some Properties of Query Languages for Bags.
Proceedings of the Database Programming Languages (DBPL-4), Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, Manhattan, New York City, USA, 30 August, 1993

1992
An elementary proof that upper and lower powerdomain constructions commute.
Bulletin of the EATCS, 1992

Functional Dependencies in Relational Databases: A Lattice Point of View.
Discrete Applied Mathematics, 1992

Normal Form Relation Schemes: A New Characterization.
Acta Cybern., 1992

On the Interaction Between Closure Operations and Choice Functions with Applications to Relational Database.
Acta Cybern., 1992

1991
On Relational Database Schemes Having Unique Minimal Key.
Elektronische Informationsverarbeitung und Kybernetik, 1991

Decomposition of Domains.
Proceedings of the Mathematical Foundations of Programming Semantics, 1991

A Relational Algebra for Complex Objects Based on Partial Information.
Proceedings of the MFDBS 91, 1991

1990
Investigations on Armstrong relations, dependency inference, and excluded functional dependencies.
Acta Cybern., 1990

1989
Functional Dependencies and the Semilattice of Closed Classes.
Proceedings of the MFDBS 89, 1989


  Loading...