Publications
Last update: April 2020.
Below is the list of my papers. When there exist both conference
and journal versions of a paper, the former is on the list only if the
titles are different.
Here are (possibly outdated) links to web pages of (some of) my co-authors:
Rajeev Alur,
Shun'ichi Amano,
Marcelo Arenas,
Pablo Barceló, Michael Benedikt,
Rada Chirkova,
Marco Console,
Claire David, Guozhu Dong, Ron Fagin, Wenfei Fan, Amélie Gheerbrant, Tim Griffin, Martin Grohe,
Paolo Guagliardo,
Lauri Hella,
Andre Hernich,
Kousha Etessami,
Diego Figueira,
Floris Geerts,
Neil Immerman,
Solmaz Kolahi,
Wim Martens,
Filip Murlak,
Frank Neven, Juha Nurmonen,
Antonella Poggi,
Juan
Reutter,
Nicole Schweikardt,
Thomas Schwentick,Luc Segoufin,
Cristina
Sirangelo,
Tony Tan,
Anthony Widjaja Lin
(To),
Domagoj Vrgoč,
Limsoon Wong.
Click here to email me.
-
Coping with incomplete data: recent advances.
Marco Console, Paolo Guagliardo, Leonid Libkin, and Etienne Toussaint.
In Proceedings of the 39th Symposium on Principles of Database
Systems (PODS'20), to appear.
- Queries with arithmetic on
incomplete databases.
Marco Console, Matthias Hofer, and Leonid Libkin.
In Proceedings of the 39th Symposium on Principles of Database
Systems (PODS'20), to appear.
- Updating graph databases with Cypher.
Alastair Green, Paolo Guagliardo, Leonid Libkin,
Tobias Lindaaker, Victor Marsault, Stefan Platnikow, Martin
Schuster, Petra Selmer, Hannes Voigt.
PVLDB, 12(12): 2242-2253 (2019).
-
Fragments of bag relational algebra: expressiveness and
certain answers.
Marco Console, Paolo Guagliardo, and Leonid Libkin.
In Proceedings of the 22nd International Conference on Database
Theory (ICDT'19).
-
On the Codd semantics of SQL nulls.
Paolo Guagliardo and Leonid Libkin.
In Information Systems, 86: 46-60 (2019).
- Measuring the likelihood of
numerical constraints.
Marco Console, Matthias Hofer, and Leonid Libkin.
In International Joint Conference on Artificial Intelligence
(IJCAI'19), pages 1654-1660.
- Propositional and predicate
logics of incomplete information.
Marco Console, Paolo Guagliardo, and Leonid Libkin.
16th International Conference on Principles of Knowledge
Representation and Reasoning (KR'18), pages 592-601.
- Approximating certainty in
querying data and metadata.
Cristina Civili and Leonid Libkin.
16th International Conference on Principles of Knowledge
Representation and Reasoning (KR'18), pages 582-591.
- Exaplainable certain answers.
Giovanni Amendola and Leonid Libkin.
In International Joint Conference on Artificial Intelligence
(IJCAI'18), pages 1683-1690.
- Certain answers meet zero-one laws.
Leonid Libkin.
In Proceedings of the 37th Symposium on Principles of Database
Systems (PODS'18), pages 195-207.
- An operational approach to
consistent query answering.
Marco Calautti, Leonid Libkin, and Andreas Pieris.
In Proceedings of the 37th Symposium on Principles of Database
Systems (PODS'18), pages 239-251.
- Cypher: An Evolving Query
Language for Property Graphs.
Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin,
Tobias Lindaaker, Victor Marsault, Stefan Platnikow, Mats
Rydberg, Petra Selmer, Andres Taylor.
Proceedings of SIGMOD'18, pages 1433-1445.
- A formal semantics of SQL
queries, its validation, and
applications.
Paolo Guagliardo and Leonid Libkin.
Proceedings of VLDB Endowment (PVLDB), vol 10, No. 11.
- Correctness of SQL queries on
databases with nulls.
Paolo Guagliardo and Leonid Libkin.
SIGMOD Record, 46(3): 5-16 (2017).
- TriAL: a navigational algebra
for RDF triplestores.
Leonid Libkin, Juan Reutter, Adrian Soto, and Domagoj Vrgoč.
ACM Transactions on Database Systems, 43(1): (2018).
- On querying incomplete
information in databases under bag semantics.
Marco Console, Paolo Guagliardo and Leonid Libkin.
In International Joint Conference on Artificial Intelligence (IJCAI'17), pages 993-999.
- Schema mappings for data graphs.
Nadime Francis and Leonid Libkin.
In Proceedings of the 36th Symposium on Principles of Database
Systems (PODS'17), pages 389-401.
- On the Codd semantics of SQL nulls.
Paolo Guagliardo and Leonid Libkin.
In Proceedings of the 36th Alberto Mendelzon Workshop (AMW'17).
- Querying graphs with data.
Leonid Libkin, Wim Martens, and Domagoj Vrgoč.
Journal of the ACM, 63(2) (2016).
- SQL's three-valued logic and
certain answers.
Leonid Libkin.
ACM Transactions on Database Systems 41(1) (2016).
(Note: preliminary version in ICDT'15.)
- Making SQL queries correct on
incomplete databases: a feasibility study.
Paolo Guagliardo and Leonid Libkin.
In Proceedings of the 35th Symposium on Principles of Database
Systems (PODS'16), pages 211-223.
- Certain answers as objects and
knowledge.
Leonid Libkin.
Artificial Intelligence 232 (2016), 1-19.
(Note: preliminary version in 14th
International Conference on Principles of Knowledge Representation
and Reasoning (KR'14).)
- Approximations and refinements of
certain answers via many-valued logics.
Marco Console, Paolo Guagliardo, and Leonid Libkin.
15th International Conference on Principles of Knowledge
Representation and Reasoning (KR'16), pages 349-358.
- Order-invariant types and their applications.
Pablo Barcelo and Leonid Libkin.
Logical Methods in Computer Science, 12(1) (2016).
- Negative knowledge for certain query answers.
Leonid Libkin.
10th International Conference on Web Reasoning and Rule Systems (RR'16), pages 111-127.
- Data wrangling for big data:
challenges and opportunities.
Tim Furche, Georg Gottlob, Leonid Libkin, Giorgio Orsi, and Norman Paton.
19th International Conference on Extending Database Technology
(EDBT'16), pages 473-478.
- How to define certain answers.
Leonid Libkin.
International Joint Conference on Artificial Intelligence (IJCAI'15),
pages 4282-4288.
- Path logics for querying
graphs: combining expressiveness and efficiency.
Diego Figueira and Leonid
Libkin.
Proceedings of the 30th Symposium on Logic in Computer Science
(LICS'15), pages 329-340.
- Certain answers over
incomplete XML documents: extending tractability
boundary
Amélie Gheerbrant and Leonid Libkin.
Theory of Computing Systems, 57(4) (2015), 892-926.
- Synchronizing relations on
words.
Diego Figueira and Leonid
Libkin.
Theory of Computing Systems, 57(2) (2015), 287-318.
(Note: preliminary version in
Symposium on Theoretical Aspects of Computer Science (STACS'14), pages 518-529.)
- Naive evaluation of queries
over
incomplete databases
Amélie Gheerbrant, Leonid Libkin, and Cristina Sirangelo.
ACM Transactions on Database Systems, 39(4), 31
(2014).
(Note:
full version of PODS'13.)
-
Incomplete data: what went wrong, and how to fix it (invited paper).
Leonid Libkin.
In Proceedings of the 33rd Symposium on Principles of Database
Systems (PODS'14), pages 1-13. Slides from the talk
are here.
-
On scale independence for querying big data.
Wenfei Fan, Floris Geerts, and Leonid Libkin.
In Proceedings of the 33rd Symposium on Principles of Database
Systems (PODS'14), pages 51-62.
- XML schema mappings:
data exchange and metadata management.
Snunichi Amano,
Claire David, Leonid
Libkin, and Filip Murlak.
Journal of the ACM, 61(2) (2014).
- Querying regular graph patterns.
Pablo Barceló, Leonid
Libkin, and Juan Reutter.
Journal of the ACM, 61(1) (2014).
- Efficient approximations of
conjunctive queries.
Pablo Barceló, Leonid Libkin, and Miguel Romero.
SIAM Journal on Computing, 43(3) (2014), 1085-1130.
(Note: preliminary version
in Proceedings of the 31th Symposium on Principles of Database Systems (PODS'12), pages 249-260.)
- Pattern logics and auxiliary relations.
Diego Figueira and Leonid
Libkin.
Proceedings of the 29th Symposium on Logic in Computer Science
(LICS'14).
- Graph logics with rational
relations.
Pablo Barceló, Diego Figueira, and Leonid Libkin.
Logical Methods in Computer Science, 9(3) (2013).
-
Solutions and query rewriting in data exchange.
Marcelo Arenas, Pablo Barceló, Ronald Fagin, and Leonid
Libkin.
Information and Computation, 228 (2013), 28-61.
- When is naive evaluation
possible?
Amélie Gheerbrant, Leonid Libkin, and Cristina Sirangelo.
In Proceedings of the 32nd Symposium on Principles of Database
Systems (PODS'13), pages 75-86.
- TriAL for RDF:
Adapting graph query languages for RDF data.
Leonid Libkin, Juan Reutter and Domagoj Vrgoč.
In Proceedings of the 32nd Symposium on Principles of Database
Systems (PODS'13), pages 201-212.
- Reasoning about pattern-based XML
queries (invited paper).
Amélie Gheerbrant, Leonid Libkin, and Cristina Sirangelo.
In Proceedings of the 7th International Conference on Web
Reasoning and Rule Systems (RR'13), pages 4-18.
- Regular expressions with binding
over data words for querying graph databases.
Leonid Libkin, Tony Tan and Domagoj Vrgoč.
In Proceedings of the 17th International Conference on Developments in
Language Theory (DLT'13), pages 325-337.
- Parameterized regular expressions
and their languages.
Pablo Barceló, Leonid
Libkin, and Juan Reutter.
Theoretical Computer Science 474 (2013), 21-45.
(Note: preliminary version
in Proceedings of Foundations of Software Technology and
Theoretical Computer Science (FSTTCS'11), pages 351-362.)
- Containment of pattern-based
queries over data trees.
Claire David, Amélie Gheerbrant, Leonid Libkin, and Wim Martens.
In Proceedings of the 16th International Conference on Database
Theory (ICDT'13), pages 201-212.
- Querying graph databases with XPath.
Leonid Libkin, Wim Martens, and Domagoj Vrgoč.
In Proceedings of the 16th International Conference on Database
Theory (ICDT'13), pages 129-140.
-
On the aggregation problem for synthesized web services.
Ting Deng, Wenfei Fan, Leonid Libkin, and Yinghui Wu.
Journal of Computer and System Sciences 79(6) (2013), 873-891.
(Note: preliminary version
in Proceedings of the 13th
International Conference on Database Theory (ICDT'10))
- Static analysis and query answering
for incomplete data trees with constraints.
Amélie Gheerbrant, Leonid
Libkin, and Juan Reutter.
In Peter Buneman Festschrift,
Springer, 2013, pages 273-290.
- Expressive languages for path
queries over graph-structured data.
Pablo Barceló, Leonid Libkin, Anthony Widjaja Lin, and Peter
Wood.
ACM Transactions on Database Systems, 37(4):
(2012).
(Note: preliminary version
in Proceedings of the 29th Symposium on Principles of Database
Systems (PODS'10), pages 3-14.)
- Graph logics with rational
relations and the generalized intersection
problem.
Pablo Barceló, Diego Figueira, and Leonid Libkin.
In Proceedings of the 27th Symposium on Logic in Computer Science
(LICS'12), pages 115-124.
- Efficient reasoning about data
trees via integer linear programming.
Claire David, Leonid Libkin, and Tony Tan.
ACM Transactions on Database Systems, 37(3): 19 (2012).
(Note: preliminary version in Proceedings
of the 14th International Conference on Database Theory (ICDT'11)).
- On the complexity of query
answering over incomplete XML documents.
Amélie Gheerbrant, Leonid Libkin, and Tony Tan.
In Proceedings of the 15th International Conference on Database
Theory (ICDT'12), pages 169-181.
- Regular path queries on graphs
with data.
Leonid Libkin and Domagoj Vrgoč.
In Proceedings of the 15th International Conference on Database
Theory (ICDT'12), pages 74-85.
- Regular expressions for
data words.
Leonid Libkin and Domagoj Vrgoč.
In Proceedings of the 18th Conferences on Logic for Programming,
Artificial Intelligence, and Reasoning (LPAR'12), pages 274-288.
- On low treewidth approximations of
conjunctive queries.
Pablo Barceló, Leonid Libkin, and Miguel Romero.
In AMW 2012.
- Tractable XML data exchange via
relations.
Rada Chirkova, Leonid Libkin, and Juan Reutter.
Frontiers of Computer Science 6 (3) (2012), 243-263.
(Note: preliminary version
in Proceedings of the 20th Conference on Information and Knowledge
Management (CIKM'11), pages 1629-1638.)
- Incomplete information and
certain answers in general data models.
Leonid Libkin.
In Proceedings of the 30th Symposium on Principles of Database
Systems (PODS'11), pages 59-70.
- Querying graph patterns.
Pablo Barceló, Leonid Libkin, and Juan Reutter.
In Proceedings of the 30th Symposium on Principles of Database
Systems (PODS'11), pages 199-210.
-
Closed world data exchange.
Andre Hernich, Leonid Libkin and Nicole Schweikardt.
ACM Transactions on Database Systems, 36(2): 14 (2011).
-
Data exchange and schema mappings in open and closed
worlds.
Leonid Libkin and Cristina Sirangelo.
Journal of Computer and System
Sciences, 77 (3) (2011), 542-571.
(Note: extended abstract in Proceedings of the 27th Symposium on
Principles of Database
Systems (PODS'08), pages 139-148.)
- A direct translation from XPath to
nondeterministic automata.
Nadime Francis, Claire David, and Leonid Libkin.
In Proceedings of AMW 2011.
- Regular languages of nested
words: automata, fixed-points,
and synchronization.
Marcelo Arenas, Pablo Barceló, and Leonid Libkin.
Theory of Computing Systems, 49(3) (2011), 639-670.
(Note: extended abstract in Proceedings of International
Colloquium on
Automata, Languages and Programming
(ICALP'07),
Springer LNCS, vol. 4596, pages 888-900.)
-
XML with incomplete information.
Pablo Barceló, Leonid Libkin, Antonella Poggi, and Cristina Sirangelo.
Journal of the ACM, 58(1), December 2010.
- Expressive languages for path
queries over graph-structured data.
Pablo Barceló, Carlos Hurtado, Leonid Libkin, and Peter Wood.
In Proceedings of the 29th Symposium on Principles of Database
Systems (PODS'10), pages 3-14.
- Certain answers for XML queries.
Claire David, Leonid Libkin, and Filip Murlak.
In Proceedings of the 29th Symposium on Principles of Database
Systems (PODS'10), pages 191-202.
- On the satisfiability of
two-variable logic over data words.
Claire David, Leonid Libkin, and Tony Tan.
In Proceedings of the 17th Conferences on Logic for Programming,
Artificial Intelligence, and Reasoning (LPAR'10), pages 248-262.
-
On the tradeoff between mapping and querying power in XML
data exchange.
Shunichi Amano, Claire David, Leonid Libkin, and Filip Murlak.
In Proceedings of the 13th
International Conference on Database Theory (ICDT'10).
-
Algorithmic metatheorems for decidable LTL model checking
over infinite systems.
Anthony Widjaja To and Leonid Libkin.
In Proceedings of the 13th
International Conference on
Foundations of Software Science and Computation Structures
(FOSSACS'10), pages 221-236.
-
An information-theoretic analysis of worst-case redundancy
in database design.
Solmaz Kolahi and Leonid Libkin.
ACM Transactions on Database Systems, 35(1): (2010).
-
Reasoning about XML with temporal logics and automata.
Leonid Libkin and Cristina Sirangelo.
Journal of Applied Logic, 8 (2) (2010), 210-232.
(Note: extended abstract in Proceedings of the International
Conferences on Logic for
Programming, ArtificialIntelligence and Reasoning (LPAR'08), pages 97-112.)
-
Disjoint pattern matching and implication in strings.
Leonid Libkin and Cristina Sirangelo.
Information Processing Letters, 110 (4) (2010), 143-147.
- On incomplete XML documents with
integrity constraints.
Pablo Barceló, Leonid Libkin, and Juan Reutter.
In AMW 2010.
- The finite model theory toolbox
of a database theoretician. (invited tutorial)
Leonid Libkin.
In Proceedings of the 28th Symposium on Principles of Database
Systems (PODS'09), pages 65-76.
Here are the slides. The conference
tutorial was a bit shorter, email me if you want to see it.
-
XML with incomplete information: models, properties, and query
answering.
Pablo Barceló, Leonid Libkin, Antonella Poggi, and Cristina Sirangelo.
In Proceedings of the 28th Symposium on Principles of Database
Systems (PODS'09), pages 237-246.
- XML schema mappings.
Shunichi Amano, Leonid Libkin and Filip Murlak.
In Proceedings of the 28th Symposium on Principles of Database
Systems (PODS'09), pages 33-42.
- Open and closed world assumptions in
data exchange (invited paper).
Leonid Libkin and Cristina Sirangelo.
In Proceedings of the 22nd International
Workshop on Description Logics (DL'09), pages 1-6.
- First-order and temporal logics
for nested words.
Rajeev Alur, Marcelo Arenas, Pablo Barceló, Kousha Etessami, Neil
Immerman, and Leonid Libkin.
In Logical Methods in Computer Science, 4 (4) (2008), paper 11.
(Note: Extended abstract in Proceedings of IEEE Symposium on Logic in Computer Science
(LICS'07),
pages 151--160.)
-
Recurrent reachability analysis in regular model checking.
Anthony Widjaja To and Leonid Libkin.
In Proceedings of the International Conferences on Logic for
Programming, Artificial
Intelligence and Reasoning (LPAR'08), pages 198-213.
-
On the complexity of verifying consistency of XML
specifications.
Marcelo Arenas, Wenfei Fan, and Leonid Libkin.
SIAM Journal on Computing, 38 (3) (2008), 841-880.
(Note: extended abstract in
In Proceedings of the 21th Symposium on Principles of Database
Systems (PODS'02), pages 259-270.)
-
XML data exchange: consistency and query answering.
Marcelo Arenas and Leonid Libkin.
Journal of the ACM, 52 (2) (2008).
(Note: extended abstract in
Proceedings of the 24nd Symposium on Principles of Database
Systems (PODS'05), pages 13-24.)
-
Game-based notions of locality over finite models.
Marcelo Arenas, Pablo Barceló, and Leonid Libkin.
Annals of Pure and Applied Logic, 152 (2008), 3-30.
(Note: extended abstract in
Proceedings of Conference for Computer Science Logic
(CSL'04), Springer LNCS vol. 3210, pages 175-189.)
- Normalization theory for XML
(invited paper).
Leonid Libkin.
In Proceedings of International XML Database Symposium
(XSym'07), Springer LNCS, vol. 4704, pages 1-13.
- XML design for relational storage.
Solmaz Kolahi and Leonid Libkin.
In Proceedings of 16th International World Wide Web Conference
(WWW'07), pages 1083--1092.
- Embedded Finite Models and
Constraint Databases.
Leonid Libkin.
Appeared in a
Springer volume based on the Philadelphia Tutorials on finite model
theory, 2007, pages 257-337.
-
Logical definability and query languages over ranked and
unranked trees.
Michael Benedikt, Leonid Libkin, and Frank Neven.
ACM Transactions on Computational Logic (TOCL), 8(2) (2007),
1--62.
(Note: preliminary version in LICS'02 and LICS'03.)
-
Combining temporal logics for querying XML documents.
Marcelo Arenas, Pablo Barceló, and Leonid Libkin.
In
Proceedings of International Conference on Database Theory (ICDT'07),
Springer LNCS, vol. 4353, pages 359-374.
-
Embedded finite models (Logic Column).
Leonid Libkin.
Bulletin of the EATCS, 90 (2006), 134-149.
-
Data exchange and incomplete information.
Leonid Libkin.
In Proceedings of the 25nd Symposium on Principles of Database
Systems (PODS'06), pages 60-69.
-
On redundancy vs dependency preservation in normalization:
an information-theoretic study of 3NF.
Solmaz Kolahi and Leonid Libkin.
In Proceedings of the 25nd Symposium on Principles of Database
Systems (PODS'06), pages 114-123.
- Logics
over unranked trees: an overview.
Leonid Libkin.
Logical Methods in Computer Science, 2 (2006).
(Note: a preliminary version
was an invited paper at International Colloquium on
Automata, Languages and Programming (ICALP'05), pages 35-50.)
-
An information-theoretic approach to normal forms for relational and XML
data.
Marcelo Arenas and Leonid Libkin.
Journal of the ACM, 52 (2005), 246-283.
(Note: preliminary
version in PODS'03, pages 15-26.)
- Temporal logics
over unranked trees.
Pablo Barceló and Leonid Libkin.
In Proceedings of the IEEE Symposium on Logic in Computer Science
(LICS'05), pages 31-40.
-
Locality of queries and transformations (invited paper).
Leonid Libkin.
In Proceedings of the 12th Workshop on Logic, Language,
Information and Computation (WoLLIC'05),
pages 109-120.
-
Consistency of XML specifications.
Marcelo Arenas, Wenfei Fan, and Leonid Libkin.
In Inconsistency Tolerance, Springer LNCS vol. 3300, 2005,
pages 15-41.
-
Locally consistent transformations and query answering in data
exchange.
Marcelo Arenas, Pablo Barceló, Ronald Fagin, and Leonid Libkin.
In Proceedings of the 23nd Symposium on Principles of Database
Systems (PODS'04), pages 229-240.
- A
normal form for XML documents.
Marcelo Arenas and Leonid Libkin.
ACM Transactions on Database Systems (TODS), 29 (2004), 195-232.
(Note: preliminary version in PODS'02, pages 85-96.)
- Definable relations and
first-order query languages over strings.
Michael Benedikt, Leonid Libkin, Thomas Schwentick, and Luc Segoufin.
Journal of the ACM, 50 (2003), 694-751.
- Logical
definability and query languages over unranked trees.
Leonid Libkin and Frank Neven.
In Proceedings of the IEEE Symposium on Logic in Computer Science
(LICS'03), pages 178--187.
- Expressive power of SQL.
Leonid Libkin.
Theoretical Computer Science, 296 (2003), 379-404.
A shorter version was an invited
paper at ICDT'01: 8th International Conference on Database Theory
(Springer LNCS 1973, pages 1-21). - Reachability and connectivity queries
in constraint databases.
Michael Benedikt, Martin Grohe, Leonid Libkin and Luc Segoufin.
Journal of Computer and System Sciences, 66 (2003), 169-206.
(Note: preliminary version in PODS'00, pages 104-115.) - Variable independence for first-order
definable constraints.
Leonid Libkin.
ACM Transactions on Computational Logic (TOCL), 4 (2003),
431-451.
(Note: preliminary version in ICALP'00, pages 260-271.) - Incremental recomputation in local
languages.
Guozhu Dong, Leonid Libkin, Limsoon Wong.
Information and Computation, 181 (2003), 88-98. - A collapse result for constraint
queries over structures of small degree.
Leonid Libkin.
Information Processing Letters, 86 (2003), 277-281. - On XML integrity constraints in the
presence of DTDs.
Wenfei Fan and Leonid Libkin.
Journal of the ACM, 49 (2002), 368-406.
(Note: preliminary version in PODS'01, pages 114-125.) - Tree extension algebras: logics, automata,
and query languages.
Michael Benedikt and Leonid Libkin.
In Proceedings of the IEEE Symposium on Logic in Computer Science
(LICS'02), pages 203-212. - On verifying consistency of XML
specifications.
Marcelo Arenas, Wenfei Fan and Leonid Libkin.
In Proceedings of the 21th Symposium on Principles of Database
Systems (PODS'02), pages 259-270. - What's hard about XML Schema constraints?
Marcelo Arenas, Wenfei Fan and Leonid Libkin.
In Proceedings of Database and Expert Systems Applications (DEXA'02),
Springer LNCS 2453, pages 269-278. - Aggregate operators in constraint
query languages.
Michael Benedikt and Leonid Libkin.
Journal of Computer and System Sciences, 64 (2002), 628-654.
(Note: preliminary version in PODS'99, pages 102-113.) - Lower bounds for invariant queries in
logics with counting.
Leonid Libkin and Limsoon Wong.
Theoretical Computer Science, 288 (2002), 153-180. - Logics with aggregate operators.
Lauri Hella, Leonid Libkin, Juha Nurmonen, Limsoon Wong.
Journal of the ACM, 48 (2001), 880-907.
(Note: preliminary version in LICS'99, pages 35-44.) - A model-theoretic approach to regular
string relations.
Michael Benedikt, Leonid Libkin, Thomas Schwentick and Luc Segoufin.
In Proceedings of the IEEE Symposium on Logic in Computer Science
(LICS'01), pages 431-440. - String
operations in query languages.
Michael Benedikt, Leonid Libkin, Thomas Schwentick and Luc Segoufin.
In Proceedings of the 20th Symposium on Principles of Database
Systems (PODS'01), pages 183-194. - On the orthographic dimension of definable
sets.
Stavros Cosmadakis, Gabriel Kuper and Leonid Libkin.
Information Processing Letters, 79 (2001), 141-145. - Logics capturing local properties.
Leonid Libkin.
ACM Transactions on Computational Logic (TOCL), 2 (2001),
135-153.
(Note: preliminary version in STACS'00, pages 217-229.) - Relational queries over interpreted
structures.
Michael Benedikt and Leonid Libkin.
Journal of the ACM, 47 (2000), 644-680. - Variable independence, quantifier
elimination, and constraint representations.
Leonid Libkin.
In Proceedings of the 27th International Colloquium on Automata,
Languages and Programming (ICALP'00), pages 260-271. - Logics with counting and local properties.
Leonid Libkin.
ACM Transactions on Computational Logic (TOCL), 1 (2000),
33-59. - Safe constraint
queries.
Michael Benedikt and Leonid Libkin.
SIAM Journal on Computing, 29 (2000), 1652-1682.
(Note: preliminary version in PODS'98, pages 99-108.) - Local properties of query languages.
Guozhu Dong, Leonid Libkin and Limsoon Wong.
Theoretical Computer Science, 239 (2000), 277-308.
(Note: preliminary version in ICDT'97, pages 140-154.) - Introduction.
Gabriel Kuper, Leonid Libkin and Jan Paredaens.
In Constraint Databases, Springer-Verlag, 2000, pages 1-16. - Expressive
power: the finite case.
Michael Benedikt and Leonid Libkin.
In Constraint Databases, Springer-Verlag, 2000, pages 55-87. - Query
safety with constraints.
Michael Benedikt and Leonid Libkin.
In Constraint Databases, Springer-Verlag, 2000, pages 109-129. - Aggregate
languages for constraint databases.
Jan Chomicki and Leonid Libkin.
In Constraint Databases, Springer-Verlag, 2000, pages 131-154.
- Counting and locality over finite
structures: a survey.
Leonid Libkin and Juha Nurmonen.
In Generalized Quantifiers and Computation, Springer LNCS 1754,
pages 18-50. - Maintaining the
transitive closure of graphs in SQL.
Guozhu Dong, Leonid Libkin, Jianwen Su and Limsoon Wong.
Int. Journal of Information Technology, 5 (1999), 46-78. - Notions of locality and their logical
characterizations over finite models.
Lauri Hella, Leonid Libkin and Juha Nurmonen.
Journal of Symbolic Logic, 64 (1999), 1751-1773. - Query languages with arithmetic and
constraint databases.
Leonid Libkin.
SIGACT News, (Database Theory Column), December 1999, pages
41-50. - Some
remarks on variable independence, closure, and orthographic dimension
in constraint databases.
Leonid Libkin.
SIGMOD Record, 28 (1999), pages 24-28. - What you can
and cannot say in SQL, or proving folk theorems in database theory (abstract
of invited talk).
Leonid Libkin.
In Proceedings of 15emes Journes Bases de Donnes Avances (BDA'99), p.
425. - On the power of incremental
evaluation in SQL-like languages.
Leonid Libkin and Limsoon Wong.
In Proceedings of Database Programming Languages (DBPL'99). - Logics with counting, auxiliary relations,
and lower bounds for invariant queries.
Leonid Libkin.
In Proceedings of IEEE Symposium on Logic in Computer Science
(LICS'99), pages 316-325. - Exact
and approximate aggregation in constraint query languages.
Michael Benedikt and Leonid Libkin.
In Proceedings of the 18th Symposium on Principles of Database
Systems (PODS'99), pages 102-113. - Verifiable properties of database transactions.
Michael Benedikt, Timothy Griffin and Leonid Libkin.
Information and Computation, 147 (1998), 57-88.
(Note: Preliminary version in PODS'96, pages 117-127.) - On counting logics and local properties.
Leonid Libkin.
In Proceedings of IEEE Symposium on Logic in Computer Science
(LICS'98), pages 501-512. - Relational expressive power of
constraint query languages.
Michael Benedikt, Guozhu Dong, Leonid Libkin and Limsoon Wong.
Journal of the ACM, 45 (1998), 1-34.
(Note: Preliminary version in PODS'96, pages 5-16.) - Unary quantifiers, transitive closure, and
relations of large degree.
Leonid Libkin and Limsoon Wong.
In Proceedings of the 15th Symposium on Theoretical Aspects of
Computer Science (STACS'98), Springer LNCS 1373, pp. 183-193. - A semantics-based approach to design of
query languages for databases with partial information.
Leonid Libkin.
In Semantics in Databases, Springer LNCS 1358, pp. 170-208.
- Models of approximation in databases.
Leonid Libkin.
Theoretical Computer Science, 190 (1998), 167-210. - On the power of aggregation in relational
query languages.
Leonid Libkin and Limsoon Wong.
In Database Programming Languages (DBPL'97), Springer LNCS
1369, pages 260-280. - Incremental
recomputation of recursive queries with nested sets and aggregate
functions.
Leonid Libkin and Limsoon Wong.
In Database Programming Languages (DBPL'97), Springer LNCS
1369, pages 222-238. - Query
languages for bags and aggregate functions.
Leonid Libkin and Limsoon Wong.
Journal of Computer and System Sciences, 55 (2) (1997),
241-272. - On the forms of locality
over finite models.
Leonid Libkin.
In Proceedings of IEEE Symposium on Logic in Computer Science
(LICS'97), pages 204-215. - An
improved algorithm for incremental recomputation of active relational
expressions.
Timothy Griffin, Leonid Libkin and Howard Trickey.
IEEE Transactions on Knowledge and Data Engineering, 9 (3)
(1997), 508-511. - Languages for
relational databases over interpreted structures.
Michael Benedikt and Leonid Libkin.
In Proceedings of the 16th Symposium on Principles of Database
Systems (PODS'97), pages 87-98. - Tractable iteration mechanisms for bag
languages.
Latha Colby and Leonid Libkin.
In Proceedings of the 6th International Conference on Database
Theory (ICDT'97), Springer LNCS 1186, pp. 461-475. - Query languages for bags: expressive
power and complexity.
Stephane Grumbach, Leonid Libkin, Tova Milo and Limsoon Wong.
SIGACT News, (Database Theory Column), June 1996, pages
30-37. - On the structure of
queries in constraint query languages.
Michael Benedikt and Leonid Libkin.
In Proceedings of IEEE Symposium on Logic in Computer Science
(LICS'96), pages 25-34. - A
query language for multidimensional arrays: design, implementation and
optimization techniques.
Leonid Libkin, Rona Machlin and Limsoon Wong.
In Proceedings of the ACM SIGMOD International Conference on
Management of Data (SIGMOD'96), pages 228-239. - Algorithms for deferred view maintenance.
Latha Colby, Timothy Griffin, Leonid Libkin, Inderpal Mumick and Howard
Trickey.
In Proceedings of the ACM SIGMOD International Conference on
Management of Data (SIGMOD'96), pages 469-480.
(Note: reprtinted in Materialized Views, The MIT Press, 1999.) - Query language primitives for programming
with incomplete databases.
Leonid Libkin.
In Proceedings of DBPL'95. - On impossibility of decremental
recomputation of recursive queries in relational calculus and SQL.
Guozhu Dong, Leonid Libkin and Limsoon Wong.
In Proceedings of DBPL'95. - Semantic
representations and query languages for or-sets.
Leonid Libkin and Limsoon Wong.
Journal of Computer and System Sciences, 52 (1) (1996),
125-142. (Note: Preliminary version in PODS'93, pp. 37-48.) - On representation and querying incomplete
information in databases with bags.
Leonid Libkin and Limsoon Wong.
Information Processing Letters, 56 (4) (1995), 209-214. - Trees as semilattices.
Leonid Libkin and Vladimir Gurvich.
Discrete Mathematics, 145 (1995), 321-327. - Approximation in databases.
Leonid Libkin.
In Proceedings of the International Conference on Database Theory
(ICDT'95), Springer LNCS 893, pp. 411-424. - Normalizing incomplete databases.
Leonid Libkin.
In Proceedings of the 14th Symposium on Principles of Database
Systems (PODS'95), pp. 219-230. - Incremental maintenance of views with
duplicates.
Timothy Griffin and Leonid Libkin.
In Proceedings of the ACM SIGMOD International Conference on
Management of Data (SIGMOD'95), pp. 328-339. (Note: reprtinted in Materialized
Views, The MIT Press, 1999.) - Interfacing
HOL90 with a functional database query language.
Elsa Gunter and Leonid Libkin.
In Proceedings of the International Workshop on Higher Order Logic
Theorem Proving and its Applications, 1995, Springer LNCS 971, pp.
328-339. - Direct decompositions of
atomistic algebraic lattices.
Leonid Libkin.
Algebra Universalis, 33 (1995), 127-135. - n-distributivity, dimension and
Caratheodory's theorem.
Leonid Libkin.
Algebra Universalis, 34 (1995), 72-95. - Conservativity of nested relational calculi
with internal generic functions.
Leonid Libkin and Limsoon Wong.
Information Processing Letters, 49 (1994), 273-280. - Comprehension
syntax.
Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen and Limsoon Wong.
SIGMOD Record, 23 (1994), 87-96. - Some properties of query languages for bags.
Leonid Libkin and Limsoon Wong.
In Proceedings of the Workshop on Database Programming Languages, Springer
Verlag, 1994, pp. 97--114. - Aggregate
functions, conservative extension and linear order.
Leonid Libkin and Limsoon Wong.
In Proceedings of the Workshop on Database Programming Languages, Springer
Verlag, 1994, pp. 282--294. - New
techniques for studying set languages, bag languages, and aggregate
functions.
Leonid Libkin and Limsoon Wong.
In Proceedings of the 13th Symposium on Principles of Database
Systems (PODS'94), pp. 155--166. - OR-SML: A functional database programming
language with support for disjunctive information.
Elsa Gunter and Leonid Libkin.
In Proceedings of the International Conference on Database and
Expert Systems Applications, Springer LNCS 856, pp. 641-650. - The lattice of subsemilattices of a
semilattice.
Leonid Libkin and Ilya Muchnik.
Algebra Universalis, 31 (1994), 252--255. - Aspects of Partial Information in Databases
(PhD Thesis).
Leonid Libkin. University of Pennsylvania, 1994. - Direct product decompositions of lattices,
closures and relation schemes.
Leonid Libkin.
Discrete Mathematics, 112 (1993), 119-138. - A remark about algebraicity in complete
partial orders.
Leonid Libkin.
Journal of Pure and Applied Algebra, 86 (1993), 75-77. - On
the interaction between closure operations and choice functions with
applications to relational databases.
Janos Demetrovics, Gusztav Hencsey, Leonid Libkin and Ilya Muchnik.
Acta Cybernetica, 10 (3) (1992), 129-139. - Normal
form relation schemes: a new characterization.
Janos Demetrovics, Gusztav Hencsey, Leonid Libkin and Ilya Muchnik.
Acta Cybernetica, 10 (3) (1992), 141-153. - Functional dependencies in relational
databases: a lattice point of view.
Janos Demetrovics, Leonid Libkin and Ilya Muchnik.
Discrete Applied Mathematics, 40 (1992), 155-185. (Note:
Preliminary version in MFDBS'89.) - An
elementary proof that upper and lower powerdomain constructions commute.
Leonid Libkin.
Bulletin of the EATCS, 48 (1992), 175-177. - Decomposition of domains.
Achim Jung, Leonid Libkin and Hermann Puhlmann.
In Proceedings of the Conference on Mathematical Foundations of
Programming Semantics (MFPS'91), Springer LNCS 598, pp. 235-258. - Quasiconvex
analysis on semilattices and absolutely determined matrices.
Vladimir Gurvich and Leonid Libkin.
Soviet Mathematics Doklady, 44 (1) (1992), 20-25. - Parallel
axiom in convexity lattices.
Leonid Libkin.
Periodica Mathematica Hungarica, 24 (1) (1992), 1-12. - Separatory
sublattices and subsemilattices.
Leonid Libkin and Ilya Muchnik.
Studia Scientiarum Mathematicarum Hungarica, 27 (1992),
471-477. - A relational algebra
for complex objects based on partial information.
Leonid Libkin.
In Proceedings of the Conference on Mathematical Fundamentals of
Database Systems (MFDBS'91), Springer LNCS 495, pp. 29-43. - On
relational database schemes having unique minimal key.
Joachim Biskup, Janos Demetrovics, Leonid Libkin and Ilya Muchnik.
Journal of Information Processing and Cybernetics, 27 (4)
(1991), 217-225. - Separability in lattices.
Leonid Libkin.
In Ordered Sets and Lattices (Russian), Saratov, 1991, pp.
78-88. - Absolutely determined matrices.
Vladimir Gurvich and Leonid Libkin.
Mathematical Social Science, 20 (1) (1990), 1-18. - Investigations on Armstrong relations,
dependency inference and excluded functional dependencies.
Georg Gottlob and Leonid Libkin.
Acta Cybernetica, 9 (4) (1990), 385-402. - Quasilinear
monotone systems.
Leonid Libkin, Ilya Muchnik and Leonid Schvartzer.
Automation and Remote Control, 50 (9) (1989), 1249-1259. - Quasilinear
set-functions and absolute definite matrices.
Vladimir Gurvich and Leonid Libkin.
Automation and Remote Control, 50 (12) (1989), 1706-1709. - Halfspaces
and hyperplanes in convexity lattices.
Leonid Libkin and Ilya Muchnik.
Institute of Mathematics, Budapest, Hungary, 1989. - Functional
dependencies and the semilattice of closed classes.
Janos Demetrovics, Leonid Libkin and Ilya Muchnik.
In Proceedings of the Conference on Mathematical Fundamentals of
Database Systems (MFDBS'89), Springer LNCS 364, pp. 136-147. - Recognition
of choice functions.
Leonid Libkin.
Automation and Remote Control, 49 (10) (1988), 1355-1358. - Minimal
sets of choice functions generating the basic classes.
Leonid Libkin.
Automation and Remote Control, 49 (12) (1988), 1662-1665. - Separatory
subsemilattices and their properties.
Leonid Libkin and Ilya Muchnik.
MTA SZTAKI Kozlemenyek, 39 (1988), 83-92. - Separation
theorems for lattices.
Leonid Libkin.
MTA SZTAKI Kozlemenyek, 39 (1988), 93-100. - On a
subsemilattice-lattice of a semilattice.
Leonid Libkin and Ilya Muchnik.
MTA SZTAKI Kozlemenyek, 39 (1988), 101-110. - Pseudocriteria
induced by set-functions.
Leonid Libkin and Ilya Muchnik.
In Proceedings of the Conference on Decision-Making (Russian), Moscow,
1988, pp. 124-125. - Algebraic methods for construction and
analysis of the choice function classes.
Leonid Libkin.
In Fuzzy Sets and Individual Choice (Russian), Moscow, 1987,
pp. 46-53.