Data Path Queries over Embedded Graph Databases
Diego Figueiradiego.figueira@cnrs.fr
Univ. Bordeaux, CNRS, Bordeaux INP,
LaBRI, UMR 5800
Talence, France

Artur Jeżartur.jez@uwr.edu.pl
University of Wrocław
Wrocław, Poland

Anthony W. Lin

anthony.lin@cs.uni-kl.de
Automated Reasoning Group, TU
Kaiserslautern and MPI-SWS
Kaiserslautern, Germany

ABSTRACT

1This paper initiates the study of data-path query languages (in particular, regular data path queries (RDPQ) and conjunctive RDPQ
(CRDPQ)) in the classic setting of embedded finite model theory,
wherein each graph is “embedded” into a background infinite structure (with a decidable FO theory or fragments thereof). Our goal
is to address the current lack of support for typed attribute data
(e.g. integer arithmetics) in existing data-path query languages,
which are crucial in practice. We propose an extension of register
automata by allowing powerful constraints over the theory and the
database as guards, and having two types of registers: registers thatcan store values from the active domain, and read-only registers
that can store arbitrary values. We prove NL data complexity for(C)RDPQ over the Presburger arithmetic, the real-closed field, theexistential theory of automatic structures and word equations withregular constraints. All these results strictly extend the known NL
data complexity of RDPQ with only equality comparisons, and provides an answer to a recent open problem posed by Libkin et al.
Among others, we introduce one crucial proof technique for obtaining NL data complexity for data path queries over embedded graphdatabases called “Restricted Register Collapse (RRC)”, inspired by
the notion of Restricted Quantifier Collapse (RQC) in embedded
finite model theory.

The past decade witnessed a lot of practical and theoretical workin querying graph databases (e.g. [2, 3, 17, 45]), due to their rapidly
growing number of applications, e.g., in social networks, semantic
web, natural science, and supply chain management. On the practical side, graph databases have enjoyed a wide adoption in industry
with many commercial database systems developed for them byvarious companies like Neo4j, Oracle, IBM, DataStax, TigerGraph,
JanusGraph, and Stardog, among many others. Although such systems adopt the so-called “property graph data model”, they differ inmany important aspects (e.g. querying facilities), which has led tothe ongoing standardization efforts of SQL/PGQ and GQL involving
leading researchers and engineers in academia and industry [17].
On the theoretical side, an important research avenue has been
to develop “well-behaved” graph query languages incorporating
topological aspects of the graph, especially the existence of paths ina graph satisfying certain patterns and constraints. Such queries arecalled path queries, and represent an essential feature (called GPML,
which stands for Graph Pattern Matching Languages) in the current
standardization effort [17] of GQL and SQL/PGQ. Historically,
Mendelzon and Wood [38] introduced in the 1990s the Regular Path
Query (RPQ) language, which has been the foundation of most pathquery languages, e.g., Conjunctive Regular Path Queries (CRPQ) [16,18, 23]. One of their main attractive features is that their query
evaluation problem has an NL (Nondeterministic Logspace) data
complexity (i.e. for any fixed query), potentially allowing traversalsof large graphs in practice (e.g. see [4, 44]).

CCS CONCEPTS• Theory of computation → Database query languages (principles); Complexity theory and logic; Finite Model Theory;
Logic and databases; Regular languages.

KEYWORDS
Data graphs, complexity, embedded finite models, regular pathqueries
ACM Reference Format:
Diego Figueira, Artur Jeż, and Anthony W. Lin. 2022. Data Path Queries
over Embedded Graph Databases. In Proceedings of the 41st ACM SIGMODSIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’22),
June 12–17, 2022, Philadelphia, PA, USA. ACM, New York, NY, USA, 13 pages.
https://doi.org/10.1145/3517804.3524159

Permission to make digital or hard copies of part or all of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for third-party components of this work must be honored.
For all other uses, contact the owner/author(s).
PODS ’22, June 12–17, 2022, Philadelphia, PA, USA© 2022 Copyright held by the owner/author(s).
ACM ISBN 978-1-4503-9260-0/22/06.
https://doi.org/10.1145/3517804.3524159

INTRODUCTION

Combining data and topology. RPQ and CRPQ are unfortunately
not suitable for “data querying” in graph databases, which is breadand butter for relational database query languages. More precisely,
in a typical graph database each node is usually associated withsome data like names and ages of the users. In relational algebra(assuming a relational encoding of graph databases), one could easily express the query that outputs two node ids for users with thesame ages. In the past decade, the importance of combining data
and topology in graph query languages has been brought to attention by multiple works, e.g. [6, 28, 36, 37]. There are many natural
examples of such queries, e.g., find two people in the database withthe same age. In particular, walk logic (WL) [28] and regular expressions with memory (REM) [37] emerged as two initial solutions
for overcoming this limitation. While RPQ using REM and register
automata as path constraint has NL data complexity [36, 37], WL
has an non-elementary data complexity [6]. The crucial observationin [36, 37] is that paths in a graph database can be construed as adata word, which enables one to apply automata over data words(e.g. register automata [31], REM [37], data automata [14], etc.) as
path constraints in a path-query. Other automata models over data<latexit sha1_base64="6PoEVW4ZKrvfHFunPEJ0M60EXKY=">AAACkXicdVFNbxMxEHW2QEv4aNoeOCAhiwjEAUW7VVTIoSICIVXikqKmrZRdRV5ntrXq9W7tcWmw9sgv4QoHbv0r/Q3wI3A2BUEDI1l6em/e2POcllIYDMPLRrB04+at5ZXbzTt3791fba2t75vCag5DXshCH6bMgBQKhihQwmGpgeWphIP05M1MPzgDbUSh9nBaQpKzIyUywRl6atx6ECOcY5q5AbOSvtWTeMcVlanGrXbY6YVRbyuiiyDqhHW1X337/unRxe6PwXitkcaTgtscFHLJjBlFYYmJYxoFl1A1Y2ugZPyEHcHIQ8VyMImrN6joE89MaFZofxTSmv3T4VhuzDRPfWfO8Nhc12bkv7SRxexl4oQqLYLi84syvykWdBYHnQgNHOXUA8a18G+l/JhpxtGH1ozfw6n1HYOraXtR4mYPrEddFxG3MyYNPK8nR9uoLSROihR8BAoWDWdMn9rEfRTdRe23LXEKPuB5vWDT/8qv6On/wf5mJ9rqdHe77f5TMq8V8pA8Js9IRF6QPtkhAzIknFTkM/lCvgYbQS/oB6/nrUHjyrNB/qrg3U+ql9EV</latexit><latexit sha1_base64="SMfUHASvNwMNjS2EfEORyzcy1XM=">AAACjnicbVFNbxMxEHWWrxK+UuCGhCwiEAcU7aKocIlaiUtPKEVNWylZRbPObGvV693a49LUypH/wRVuvfWv8BvgR+BsIgQJI1l6em/ezHgmq5S0FMc/GtGNm7du39m427x3/8HDR63Nxwe2dEbgQJSqNEcZWFRS44AkKTyqDEKRKTzMTj/M9cNzNFaWep+mFaYFHGuZSwEUqHHr6YjwgvxHLi0Hrl2RoZmNW+24E9fB10GyBO3tq59fnl/v/eqPNxvZaFIKV6AmocDaYRJXlHowJIXCWXPkLFYgTuEYhwFqKNCmvh5/xl8GZsLz0oSnidfs3w4PhbXTIguZBdCJXdXm5P+0oaP8feqlrhyhFotGuVOcSj7fBZ9Ig4LUNAAQRoZZuTgBA4LCxpqjT3jmQkZ/WW0/Sf18wLrUqkjUy0FZfFNXTnpkHKZeybBOCqdZN5yDOXOpv5Tdde2PLfUaP9NF/cFmuEqyeoN1cPC2k2x1unvd9s4rtogN9oy9YK9Zwt6xHbbL+mzABLtkX9k39j1qRVtRL9pepEaNpecJ+yei3d8fDM8K</latexit><latexit sha1_base64="Zp9cZJEwiBvatcKQGJ8Zg43JzVU=">AAACk3icdVFdaxNBFJ1s/ajxK634IIIMBsUHCbsSakspFvXBB4VUkraQXcLs5G47ZHZ2O3OnNhmCT/4UXy1986/4G/RHONlU0UYvDBzOuefOnTNpKYXBMPxWC5YuXb5ydfla/fqNm7duN1ZWd01hNYceL2Sh91NmQAoFPRQoYb/UwPJUwl46ejXT945BG1GoLo5LSHJ2oEQmOENPDRr3YoQTTDPXLXJmJtTFb6eWT9hoOmg0w9ZGGG2sRXQRRK2wquaLs++fHnzd+dEZrNTSeFhwm4NCLpkx/SgsMXFMo+ASpvXYGigZH7ED6HuoWA4mcdUbpvSRZ4Y0K7Q/CmnF/ulwLDdmnKe+M2d4aC5qM/JfWt9itp44oUqLoPj8osxKigWdBUKHQgNHOfaAcS38rpQfMs04+tjq8Xs4sr6jcz6tGyVutmA16qKIuJUxaeBpNTnaQm0hcVKk4CNQsGg4ZvrIJm4i2ovab1viFHzAk+qBdf8rv6Kn/we7z1rRWqu9025uPybzWib3yUPyhETkOdkmb0iH9AgnH8ln8oWcBneDzeBl8HreGtTOPXfIXxW8+wlFAtI6</latexit>

1913

Paul Erdős

N is a number

1960<latexit sha1_base64="3YOj613D4kMEq/nbEBqJzzHndq8=">AAACg3icdVHLbhMxFHUGSkt4tIVlJWQRgZBA0TiN2mQRUYkNyxQ1baVkVHmcO61Vj2dqX5cGK0s+gW35Bnb8Ct8AH4FnUhC0cCVLR+fcc319nJZKWozjb43o1u2lO8srd5v37j94uLq2/mjfFs4IGIlCFeYw5RaU1DBCiQoOSwM8TxUcpKdvKv3gHIyVhd7DWQlJzo+1zKTgGKjxBOECPeuzzfnRWitux3HMGKMVYNtbcQD9fq/DepRVUqjW6y/fPz75uvtjeLTeSCfTQrgcNArFrR2zuMTEc4NSKJg3J85CycUpP4ZxgJrnYBNf7zynzwIzpVlhwtFIa/ZPh+e5tbM8DZ05xxN7XavIf2ljh1kv8VKXDkGLxUWZUxQLWgVAp9KAQDULgAsjw65UnHDDBYaYmpN3cOZCx/Bq2h5LfLVgPeq6iDjIuLLwqp7MBmgcJF7JFEIEGm4azrk5c4n/ILs3td+2xGt4jxf1A5vhV35FT/8P9jttttXu7nZbO8/JolbIBnlKXhBGtskOeUuGZEQEKcgnckk+R0vRy6gTdRetUePK85j8VdHgJ+OCyw8=</latexit><latexit sha1_base64="cuD9WI3TQlYYNRfdYlLcJyH4lKE=">AAACl3icbVFNaxsxEJW3X6n75bSnUFpETUsPxewW0/YSEgiEXAp2sJOAvRitPBuLaLUbaZTGFT6V/Jgek1z6V/ob2h8R7dqU1u6A4Om9eaOZUVJIYTAMf9aCW7fv3L23dr/+4OGjx08a608PTG41hz7PZa6PEmZACgV9FCjhqNDAskTCYXKyU+qHZ6CNyFUPpwXEGTtWIhWcoadGjRdDhHN0vQnQz0JKytSYlpcdnRszGzWaYSusgq6CaAGaW5e/Ll7+6P7ujNZryXCcc5uBQi6ZMYMoLDB2TKPgEmb1oTVQMH7CjmHgoWIZmNhVc8zoa8+MaZprfxTSiv3b4VhmzDRLfGbGcGKWtZL8nzawmH6KnVCFRVB8/lBqJcWclkuhY6GBo5x6wLgWvlfKJ0wzjn519eE+nFqf0VlU60WxKxusSi2LiJspkwbeVZWjTdQWYidFAn4FClYNZ0yf2th9Fe1V7Y8tdgq+4Hk1YN3/SrT8B6vg4H0r+tBqd9vN7TdkHmvkOXlF3pKIfCTbZI90SJ9w8o18J1fkOtgItoLdYG+eGtQWnmfknwi6NzW90n0=</latexit><latexit sha1_base64="aOrcVujYPNt6Wrx7cx3JPFeGmhs=">AAACjHicdVFdaxNBFJ2sXzVqTeujIINB8UHCroRqkWBBEB9TbdpCsoS7k7vt0NnZ7cydmjjk0b/hq7765l/xN+iPcLKpoo1eGDicc8+dO2eySklLcfytEV26fOXqtbXrzRs3b63fbm1s7tvSGYEDUarSHGZgUUmNA5Kk8LAyCEWm8CA7ebnQD87QWFnqPZpVmBZwpGUuBVCgxq3NEeGUsty/RdC8j1rPx6123NmOk+2thK+CpBPX1X7x5fuHe193f/THG41sNCmFK1CTUGDtMIkrSj0YkkLhvDlyFisQJ3CEwwA1FGhTXy8/5w8CM+F5acLRxGv2T4eHwtpZkYXOAujYXtQW5L+0oaP8WeqlrhyhFsuLcqc4lXyRBJ9Ig4LULAAQRoZduTgGA4JCXs3RGzx1oaN/Pm0vSf1iwXrURZGol4Oy+LienPTIOEy9khmGCDSuGs7AnLrUv5fdVe23LfUa39G0fmAz/Mqv6Pn/wf6TTrLV6e522zsP2bLW2F12nz1iCXvKdthr1mcDJtiUfWSf2OdoPepGz6PesjVqnHvusL8qevUTdTLO0A==</latexit><latexit sha1_base64="2gfh1plzxr2XOwxbnYLTef4Rtsg=">AAACg3icdVHLbhMxFHUGCiW8WlhWQhYRCAkU2VGUJouISt10maKmrZSMKo9zp7Xq8Uzt69IwypJPYAvfwK6/wjfAR+CZFAQtXMnS0Tn3XF8fJ4VWDhn71ohu3V65c3f1XvP+g4ePHq+tP9l3ubcSxjLXuT1MhAOtDIxRoYbDwoLIEg0Hyel2pR+cg3UqN3s4LyDOxLFRqZICAzWZIlxgyQc9tjhaa7E2Y4xzTivAN3ssgMGg3+F9yispVOvt1+8fn13u/hgdrTeS6SyXPgODUgvnJpwVGJfCopIaFs2pd1AIeSqOYRKgERm4uKx3XtAXgZnRNLfhGKQ1+6ejFJlz8ywJnZnAE3ddq8h/aROPaT8ulSk8gpHLi1KvKea0CoDOlAWJeh6AkFaFXak8EVZIDDE1p+/gzIeO0dW0PR6X1YL1qOsi4jAV2sGbejIfovUQl1olECIwcNNwLuyZj8sPqntT+22LSwPv8aJ+YDP8yq/o6f/BfqfNe+3ubre19ZIsa5VskOfkFeFkk2yRHTIiYyJJTj6Rz+RLtBK9jjpRd9kaNa48T8lfFQ1/AuezyxE=</latexit>

1958

Sean Penn<latexit sha1_base64="1Bi/y/OZj6KpIZnJTWXyxBzrGFw=">AAACg3icdVHLbhMxFHUGSkt4tIVlJWQRgZBA0ThK22QRUYkNyxQ1baVkVHmcO61Vj2dqX5cGK0s+gW35Bnb8Ct8AH4FnUhC0cCVLR+fcc319nJZKWozjb43o1u2lO8srd5v37j94uLq2/mjfFs4IGIlCFeYw5RaU1DBCiQoOSwM8TxUcpKdvKv3gHIyVhd7DWQlJzo+1zKTgGKjxBOECPetv9uZHa624HccxY4xWgG1vxQH0+70O61FWSaFar798//jk6+6P4dF6I51MC+Fy0CgUt3bM4hITzw1KoWDenDgLJRen/BjGAWqeg018vfOcPgvMlGaFCUcjrdk/HZ7n1s7yNHTmHE/sda0i/6WNHWa9xEtdOgQtFhdlTlEsaBUAnUoDAtUsAC6MDLtSccINFxhiak7ewZkLHcOraXss8dWC9ajrIuIg48rCq3oyG6BxkHglUwgRaLhpOOfmzCX+g+ze1H7bEq/hPV7UD2yGX/kVPf0/2O+02Va7u9tt7Twni1ohG+QpeUEY2SY75C0ZkhERpCCfyCX5HC1FL6NO1F20Ro0rz2PyV0WDn/ZMyxg=</latexit>

The Mill and The Cross Searching for Debra Winger<latexit sha1_base64="GK8ZOXJryJgGv4AgqxxDQFp83Xg=">AAACm3icbVHLbhMxFHWGVxteKSwrkCECsUDRDIqATUWlskCIRQpNUykZRXecO4lVj2dq3ykNVpZVv4YFG+BX+Ab4CJxJhCDhro7Puef6PpJCSUth+KMWXLp85eq1jc369Rs3b91ubN05tHlpBHZFrnJzlIBFJTV2SZLCo8IgZInCXnK8N9d7p2iszPUBTQuMMxhrmUoB5Klh48GA8IzcBwQjJlKPeZob/hoTA7znn2hmw0YzbIVV8HUQLUHz1Zef5/e/7//qDLdqyWCUizJDTUKBtf0oLCh2YEgKhbP6oLRYgDiGMfY91JChjV01y4w/8syo6iLNNfGK/dvhILN2miU+MwOa2FVtTv5P65eUvoyd1EVJqMXio7RUnHI+XwwfSYOC1NQDEEb6XrmYgAFBfn31wXs8KX1GZ1ntIIrdvMGq1KpItJOCsvi0qhztkCkxdkom6Fegcd1wCuakjN0n2V7X/thip/EjnVUD1v1VotUbrIPDZ63oeau9327uPmaL2GDb7CF7wiL2gu2yN6zDukywC/aZfWXfgnvBXvA2eLdIDWpLz132TwTd3x1l1J0=</latexit>

1963

Tomasz Łuczak<latexit sha1_base64="mo+ztbXvfkiBLfqNGqgvQk7mOTk=">AAACg3icdVHLbhMxFHWmFEp4tIUlErKIQEigaByiNFlEVGLDMkVNWykZVR7nTmvV45na16WplSWfwBa+gR2/wjfAR+CZFAQtXMnS0Tn3XF8fp6WSFuP4WyNaubF689ba7eadu/fur29sPtizhTMCxqJQhTlIuQUlNYxRooKD0gDPUwX76cmbSt8/A2NloXdxXkKS8yMtMyk4BmoyRThHzwa9V4vDjVbcjuOYMUYrwLZ6cQCDQb/D+pRVUqjW6y/fPzz+uvNjdLjZSKezQrgcNArFrZ2wuMTEc4NSKFg0p85CycUJP4JJgJrnYBNf77ygTwMzo1lhwtFIa/ZPh+e5tfM8DZ05x2N7VavIf2kTh1k/8VKXDkGL5UWZUxQLWgVAZ9KAQDUPgAsjw65UHHPDBYaYmtN3cOpCx+hy2i5LfLVgPeqqiDjMuLLwsp7MhmgcJF7JFEIEGq4bzrg5dYm/kN3r2m9b4jW8x/P6gc3wK7+ip/8He50267W7O93W9jOyrDXyiDwhzwkjW2SbvCUjMiaCFOQj+UQ+R6vRi6gTdZetUePS85D8VdHwJ+31yxQ=</latexit><latexit sha1_base64="bP+O9NmxvQYwe5Mjclmq1hGLaLE=">AAAClXicdVHLThsxFHWmL0gfhLJggVRZjVp1UUUzVcRjEYFEhbprQASQklHkce4EC49nsK+BYGXBgm/pFnb9lX5D+xF1JrRqSXslS0fn3OdxUkhhMAy/VYIHDx89fjI3X3367PmLhdriywOTW82hw3OZ66OEGZBCQQcFSjgqNLAskXCYnGxP9MMz0Ebkah9HBcQZGyqRCs7QU/3aSg/hApPUbR8zLXNEoHss85PVcNyv1cPGRhhtrEZ0FkSNsIz65u3361dfd3+0+4uVpDfIuc1AIZfMmG4UFhg7plFwCeNqzxooGD9hQ+h6qFgGJnblFWP6xjMDmubaP4W0ZP+scCwzZpQlPjNjeGzuaxPyX1rXYroeO6EKi6D4dFBqJcWcTiyhA6GBoxx5wLgWflfKvRuMozeu2tuDU+sz2nfd9qPYTRYsW90XEVspkwbel52jFmoLsZMiAW+BgtmCM6ZPbewuRXNW+10WOwXneFEeWPW/8st6+n9w8KERrTaau8361lsyjTmyQl6TdyQia2SLfCJt0iGcXJEv5IbcBstBK/gY7ExTg8pdzRL5K4LPPwH5NNLy</latexit>

Charlotte Rampling<latexit sha1_base64="TgApUJm5Br+ZbwNxDOAYV9UelPM=">AAACjnicdVHRThNBFJ2uKFBUivpmQiY0Gh9Ms0uaKg8NRF9IfCmEAkm7aWand2HC7Owyc6dSJn3kP3jFN9/8Fb9BP8LpFoxSvckkJ+fcc+fOmaSQwmAYfq8EDxYePlpcWq6uPH7ydLW29uzQ5FZz6PJc5vo4YQakUNBFgRKOCw0sSyQcJWcfp/rRCLQRuTrAcQFxxk6USAVn6KlB7UUf4QKT1H2CkVD0A+O5mgxq9bCxFUZbrYjOg6gRllXf/vrjav3b3s/OYK2S9Ic5txko5JIZ04vCAmPHNAouYVLtWwMF42fsBHoeKpaBiV25/oS+8syQprn2RyEt2T8djmXGjLPEd2YMT819bUr+S+tZTN/HTqjCIig+uyi1kmJOp1nQodDAUY49YFwLvyvlp0wzjj6xan8fzq3v6NxOO4hiN12wHHVfRGynTBp4W06O2qgtxE6KBHwECuYNI6bPbewuRXNe+22LnYLPeFE+sOp/5S56+n9wuNmIWo3mXrO+85rMaom8JBvkDYnIO7JDdkmHdAknl+Sa3JAvQS1oBe1ge9YaVG49z8lfFez+Am/lz6w=</latexit>

Kevin Bacon
Mystic River<latexit sha1_base64="nf9sZh+SXe7x2Vl9bjucDZl8nTw=">AAACjXicbVHBThsxEHW2lNJQIJRjpWpFRNUDinZRKBxKi9RDe0EKiABSsoq8zixYeL2LPaZsrRz7Hb22x976K/2G9iPwbiIECSNZenrvzfN4HOeCawyCvzXvydzT+WcLz+uLL5aWVxqrL090ZhSDLstEps5iqkFwCV3kKOAsV0DTWMBpfPmp1E+vQWmeyWMscohSei55whlFRw0aa32EG7QHhUbO/CPuvKNBoxm0gqr8WRBOQPPj73/fX/85/N8ZrNbi/jBjJgWJTFCte2GQY2SpcqECRvW+0ZBTdknPoeegpCnoyFbTj/wNxwz9JFPuSPQr9n6HpanWRRo7Z0rxQk9rJfmY1jOY7EaWy9wgSDa+KDHCx8wvV+EPuQKGonCAMsXLBbALqihDt7B6/wiujHN0JmnHYWTLAauoaRFxL6FCw2aVHO6hMhBZwWNwK5Aw23BN1ZWJ7DfentXu2iIr4SveVA+su18Jp/9gFpxstcJ3rfZhu7n/hoxrgbwi6+QtCckO2SdfSId0CSMF+UF+kl/eirftvfc+jK1ebdKzRh6U9/kWVfHPLQ==</latexit>

1946<latexit sha1_base64="ecDcmLSXq7tmDzlXfvQbEMkVGIo=">AAACg3icdVHLbhMxFHUGCiW8WlgiIYsIhASKxtEoTRYRldiwTFHTVkpGlce501r1eKb2dWmwsuQT2MI3sONX+Ab4CDyTgqCFK1k6Ouee6+vjrFLSYhx/a0XXrq/duLl+q337zt179zc2H+zZ0hkBE1Gq0hxk3IKSGiYoUcFBZYAXmYL97OR1re+fgbGy1Lu4qCAt+JGWuRQcAzWdIZyjZ8Okvzzc6MTdOI4ZY7QGbKsfBzAcDnpsQFktheq8+vL9w+OvOz/Gh5utbDYvhStAo1Dc2imLK0w9NyiFgmV75ixUXJzwI5gGqHkBNvXNzkv6NDBzmpcmHI20Yf90eF5Yuyiy0FlwPLaXtZr8lzZ1mA9SL3XlELRYXZQ7RbGkdQB0Lg0IVIsAuDAy7ErFMTdcYIipPXsLpy50jC+m7bLU1ws2oy6LiKOcKwsvm8lshMZB6pXMIESg4arhjJtTl/r3Mrmq/balXsM7PG8e2A6/8it6+n+w1+uyfjfZSTrbz8iq1skj8oQ8J4xskW3yhozJhAhSko/kE/kcrUUvol6UrFqj1oXnIfmrotFP8AnLFQ==</latexit>

Figure 1: Part of the “Bacon Graph”, where each solid(resp. dotted) edge represents the “acts in” (resp. “is born in”)
relation. Each actor is a black box, and each movie is a whitebox. Birthyears are also nodes.
Table 1: Summary of our data complexity results
L

Data Complexity of RDPQ(L, σ )FO(R×,+ , σ )FO(ZLA , σ )EFO+ (TAut , σ )EFO(TAut , σ )
LPM
L+
WE

NL
NL
NP-hard
NL (under LogH)
NL
NL

words (e.g. data automata) increase the data complexity of RPQ
from NL to NP-hard [36].
The need for reasoning about concrete data. Thus far, the solutions [6, 28, 36, 37] to combine data and topology aspects ingraph queries ignore completely the structure of the data. For example, practical database query languages typically allow concrete data (e.g. numbers, words) and a wide variety of data operations/comparisons (e.g. substrings, inequality, difference). Consider,for instance, the “Bacon graph” (see Figure 1) and the query “return
all actors with a finite Bacon number and whose birthyear differs
Bacon’s birthyear by at least 30 years,” whose only answer here isErdős. Alternatively, consider the query “return all users who werein at least four different locations in the last month, but stayed within
a 10km radius from some point in a map,” whose numbers and how
they differ on a monthly basis might be insightful especially during
the time of COVID-19. Finally, for a phylogenetic database, one
might be interested in a path containing only nodes whose center(with respect to some edit distance measure) is not that far awayfrom any DNA sequence along the path [15, 26]. None of the above
features are expressible in the existing path-query languages. For
example, while path query languages like RDPQ [36] may for instance express the existence of a path from Erdős to Bacon, sharing
the same birth years, they only support active-domain values intheir registers, as well as equality comparisons, which restrict themfrom expressing the three aforementioned examples.
Incorporating concrete attribute data and their operations ina first-order query language over relational databases has been
intensively studied by database theorists between 1990 and early
2000s in the context of constraint databases and embedded finite
model theory (e.g. see [25, 34] and [35, Chapter 13]). In particular,
one considers a relational database embedded into the universe of
an infinite structure with a decidable FO theory (e.g. real-closed field

R×,+ or integer linear arithmetic ZLA [25, 34, 35]), and allows firstorder queries to make use of operations in the theory. For example,
over a graph embedded into R×,+ , one could ask if all edges ina graph lie on a line. The first-order query can be found in [35,Chapter 13]: ∃u ∃v ∀x ∈ adom ∀y ∈ adom (E (x, y) → y = u.x + v).
Notice two kinds of quantifiers are in use: ∃u means “there is a real
number (not necessarily in the active domain)”, while ∀x ∈ adommeans “for all elements in the active domain”. The set of such firstorder formulas over the theory T and relational database schema σ
is denoted by FO(T, σ ), and its restrictions with only active-domain
quantifiers by FOact (T, σ ). Despite this, the issue of querying datapaths over embedded graph databases remains hitherto unaddressed
and was only left as an open problem by Libkin et al. [36].
Contributions. This paper initiates the study of data-path queries
in the setting of embedded graph databases, i.e., finite graphs embedded in some infinite structure with a decidable first-order theory
T or fragments thereof. Because of the different graph models in
the literature we assume a general relational database schema σ
and define a graph by means of first-order views over σ and T. Thisis closer to the data model adopted by SQL/PGQ (e.g. see [17] andhttps://pgql-lang.org/), and can be used to encode implicitly, as well
as explicitly, represented property graphs. We study the problem ofquery evaluation over extensions of RDPQ and CRDPQ, allowing
the use of FO(T, σ )-formulas in the queries, which capture a rangeof meaningful queries involving typed attribute values like integers,
reals, and words (e.g. the three aforementioned examples).
Since register automata [36] use untyped attribute data which
can only be compared via equality and disequality, we first define extended register automata (ERA) that allow attribute data in T which
can be manipulated via operations in FO(T, σ ). By analogy to thesetting of embedded finite model theory, we allow two kinds of registers: active-domain registers and unrestricted registers. Each transition is associated with a guard φ(curr , R, R ′, P, P ′ ) ∈ FO(T, σ ),where curr is the value in T representing the current node (called
node ID), R (resp. P) represents the current values of the activedomain (resp. unrestricted) registers, and R ′ (resp. P ′ ) represents
the next values of the active-domain (resp. unrestricted) registers.
The register automata model of [36] can be construed as an instance of ERA with no unrestricted registers, where σ = {E},T = ⟨N; =, {c i }i ∈N ⟩ with each constant c i interpreted as the numberi, and the guard uses only Boolean combinations of FO(T)-atoms.
Without further restrictions, the model easily captures the universal Minsky’s counter machine already with two unrestricted
registers and the theory ⟨N; succ⟩ of natural numbers with successor [41]. Hence, we impose the so-called bounded-rewrite assumptions to the unrestricted registers, i.e., for some constant b ∈ N,each unrestricted register can be rewritten at most b times. The
resulting query languages RDPQ(T, σ ) and CRDPQ(T, σ ) turn out
to be sufficiently general to express many interesting examples(e.g. our three aforementioned examples). Our result on the data
complexity of query evaluation is summarized in Table 1. Note that
under the bounded-rewrite assumption we can assume that b = 0
at the expense of increasing the number of unrestricted registers,
see Proposition 2.4.
First, we obtain NL data complexity for RDPQ(FO, R×,+ , σ ) andRDPQ(FO, ZLA , σ ). With these, we can express the first two out

of our three examples. To prove this, we introduce the so-called
Restricted Register Collapse (RRC) — akin to the notion of Restricted
Quantifier Collapse (RQC) for FO over embedded finite models [35,Chapter 13] — which states that each query in RDPQ(FO, T, σ )is equivalent to a query in RDPQ(FO, T, σ ) without unrestricted
registers and so that no guards contain unrestricted quantifiers. We
show that this holds for R×,+ and ZLA .
The case of words is more involved. To permit reasoning aboutproperties such as edit distance, one needs a sufficiently expressive
word theory T, e.g., the theory TAut of automatic relations [11, 13],or theory TWE of word equations [19]. Unfortunately, FO(TAut , σ )and FO(TWE , σ ) have prohibitive data complexity [11] (hard for thepolynomial hierarchy PH and undecidable, respectively). We provide restrictions that still allow us to reason about interesting properties like edit distance, while admitting NL data complexity. First
we show that the existential fragment EFO(TAut , σ ) admits RQC(i.e. EFO(TAut , σ ) ⊆ FOact (T, σ )), implying an NC1 data complexity.
In contrast, we show that RDPQ(EFO, TAut , σ ) has NP-hard data
complexity and does not admit RRC, unless P = NP. Fortunately,
NL data complexity can be recovered for RDPQ(EFO, TAut , σ ) assuming the LogH hypothesis that the words in the database are oflength logarithmic in the size of the database, which is reasonable
for most graph database applications, with extremely large graphs
and exponentially smaller data sizes (e.g. names, DNA sequences,etc.). Secondly, we provide two fragments of FO(TWE , σ ) (patternmatching fragment LPM and positive quantifier-free fragment L+
WE )that permit NL data complexity for RDPQ(TWE , σ ), even without
assuming LogH. The proof is an intricate application of word equation solving.
Organization. We introduce our data model and query languagein §2. We tackle data complexity of the theories over numbers (reals,
integers) in §3, and over words in §4 (automatic structures) and§5 (word equations). We conclude in §6 with generalizations (e.g.
conjunctive queries and property graphs), and future work.
Complexity Theory Preliminaries. We assume standard complexity classes esp. L (Logspace), NL (Nondeterministic Logspace), P,
NP, PH, PSPACE. In this paper, we will also mention (the uniform
versions of) circuit complexity classes like AC0 , TC0 , NC1 . It is
well-known that AC0 ⊊ TC0 ⊆ NC1 ⊆ L ⊆ NL ⊆ P ⊆ NP ⊆PH ⊆ PSPACE. All reductions mentioned in this paper can be
implemented in Logspace. See [33, 35, 43] for more.

2

DATA MODEL AND QUERIES

Embedded Finite Models. Fix a relational vocabulary σ containing
finitely many relation symbols Ri with arity r i (i.e. σ = {R 1 , . . . , Rk })and an infinite structure T with domain D. A finite σ -model embedk ⟩ such that
ded into T [35, Ch. 13] is a σ -structure S := ⟨U ; {RiS }i=1
Sri
U ⊆ D is finite and Ri ⊆ U for every i. The set U is called theactive domain of S and hence denoted by adom(S). In the sequel,
we shall also refer to such S as (T, σ )-structure.
By FO(T, σ ), we denote first-order logic that may use (T ∪ σ )atomic formulas, active-domain quantification (∃x ∈ adom, ∀x ∈adom), as well as unrestricted quantification (∃x, ∀x). We denote by
FOact (T, σ ) the restriction of FO(T, σ ) that prohibits unrestricted

quantifications. For a formula φ(x̄ ) and ā ∈ D |x̄ | , we define the notion of satisfaction S |=T φ(ā) by interpreting each atomic formulafrom σ (resp. T) with respect to S (resp. T), each active-domain
quantifier ∃x ∈ adom ψ (resp. ∀x ∈ adom ψ ) as “there exists anelement b in U such that ψ ” (resp. “for all elements b in U , ψ ”), andeach unrestricted quantifier ∃x ψ (resp. ∀x ψ ) as “there exists anelement b in D such that ψ ” (resp. “for all elements b in D, ψ ”). See
the example ∃u∃v∀x ∈ adom∀y ∈ adom (E (x, y) → y = u.x + v)
in § 1 and more examples in [25, 35].
We fix now some extra notation that we will use in the sequel.
We write |= instead of |=T , when T is understood. We also write[[φ]] (T,S) to denote the set of all ā ∈ D |x̄ | such that S |=T φ(ā).
Whenever understood, we also use the same notation for a relation
symbol R and the relation R S that instantiates R in S. Finally, for the
purpose of measuring complexity of query evaluation problems,
we assume a size function |.| : D → N that defines the size of therepresentation of a datum; this will be fixed with respect to eachtheory under consideration.
Embedded Graph Databases. Fix a finite alphabet Σ of symbols.
We define our notion of data graphs following [36]. Our results canbe easily adapted to a notion of property graphs [17]; see § 6. We
assume in the following a theory T and a finite (T, σ )-structure S.
Our notion of embedded graphs will be defined with respect to S
via views defined through formulas over a fragment L ⊆ FO(T, σ ).
Fix our view vocabulary ν = {V } ∪ {Ea }a ∈Σ , where V is unary(denoting the vertex view) and each Ea is binary (denoting theview of a-labeled edges). A view definition for a view W with arity
r is an L-formula φW (x̄ ) with r = |x̄ |. Each view W will thenbe interpreted as [[φW ]] ⊆ U r containing all ā ⊆ U r such that
S |= φ(ā). As before, whenever understood, we will confuse eachview W and their interpretation [[φW ]]. We are now ready to define
our notion of (data)-graph G embedded into T (or (T, σ )-graph orjust graph for short): it is a pair (Θ, S), where Θ is a set of view
definitions and S a finite (T, σ )-structure.
In the sequel, instead of writing (v, w ) ∈ Ea , we shall often
write v →a w. A G-path from v to w, where v, w ∈ V , is simply
an alternating sequence v = v 0a 1 · · · an vn = w of vertices andedge labels of G (i.e. each vi ∈ V and each a j ∈ Σ) such thatvi →ai +1 vi+1 for each i ∈ [0, n − 1].
Example 2.1. Consider our Bacon graph G from Figure 1. We
may assume that the database schema used to represent this is σ ={Ea , Eb , Act, Mov, Y }, where Ea (resp. Eb ) is a binary relation representing the “acts in” (resp. “was born in”) relation, Act (resp. Mov)is a unary relation representing all the actors (resp. movies), andY is a unary relation containing all the years in the database. Let
T = ZLA . To embed G into T, we will associate each node with aunique ID, as in Table 2. For example, this embedding has tuples
Eb (1, 1913), Ea (0, −4), etc. We may define the views as follows:
V (x ):=Act (x )E (x 1 , x 2 ):=∃y (Mov (y) ∧ Ea (x 1 , y) ∧ Ea (x 2 , y))Note that two actors are connected by an E-edge iff they act in acommon movie.
Example 2.2. Let T = R×,+ and let σ = ⟨T ⟩, where T is binary.
Each pair (t, n) in T indicates a time stamp t ∈ Q (with day as unit,Table 2: Embedding of Bacon Graph into ZLA . Each year has
itself as node ID.
ID

node

0
1
2
3
4
-1
-2
-3
-4

Kevin Bacon
Paul ErdősTomasz Łuczak
Sean Penn
Charlotte Rampling
N is a number
The Mill and The Cross
Searching for Debra Winger
Mystic River

where fractions are allowed since data are inserted as they become
available) and the total number n ∈ N of active COVID cases attime stamp t. Graph views will contain only the vertex view V anda single edge view E with the following view definitions:
V (x ):=∃y ∈ adom (T (x, y))

E (x 1 , x 2 ):=x 1 < x 2 ∧ ∃y1 , y2 (T (x 1 , y1 ) ∧ T (x 2 , y2 )) ∧¬∃x (x 1 < x < x 2 ∧ ∃y T (x, y))In other words, we obtain a graphical representation of the numberof active COVID cases whose vertices represent time stamps in
the DB and edges represent the time progressions. One might beinterested in a long enough stretch of time stamps in T whose number of active COVID cases exceeds some sufficiently fast growing
function p(t ). We will mention cases which can be answered with
NL data complexity.
Data Path Queries. Fix a fragment L ⊆ FO(T, σ ). For an alphabet
Σ, let Σ# = Σ ∪ {#}, where # < Σ is a fixed “dummy symbol”. In
order to define our query language RDPQ(L, T, σ ) (or RDPQ(L, σ )or just RDPQ(L) in short), we define our notion of extended register
automata (ERA) admitting active-domain and unrestricted registers,
which can take any value in the domain D of T. More precisely, a(σ , T)-register automaton is a tuple A = (R, P, Q, Q 0 , F , ∆), whereR = {r 1 , . . . , rl } is a set of active-domain registers, P = {p1 , . . . , ph }is a set of unrestricted registers, Q is a finite set of states, Q 0 ⊆ Q is
the set of initial states, F ⊆ Q is the set of final states, and ∆ is a finite
set of transitions1 each of the form (q, (a, φ(curr, P, P ′, R, R ′ )), q ′ ),where q, q ′ ∈ Q, a ∈ Σ# , and φ ∈ L with R ′ := {r 1′ , . . . , rl′ } andP ′ := {p1′ , . . . , ph′ }. Intuitively, curr refers to current node ID, P(resp. R) the current values of the unrestricted (resp. active-domain)
registers, and P ′ (resp. R ′ ) the next values of the unrestricted(resp. active-domain) registers. More formally, given a (T, σ )-graph
G, a path in it
π := v 0 →a1 · · · →an vn ,we write that G, π |= A if there is a sequence of transitions
q 0 →t0 · · · →tn qn+1 ,with q 0 ∈ Q 0 , qn+1 ∈ F , and register valuesv = (µ 0 , ν 0 ), . . . , (µ n , νn ) ∈ U R × D P(∗)

1 After gaining familiarity with ERA, the reader is referred to Section 6 for a general-

ization of ERA that directly traverse the relational database S.

such that for every 0 < i ≤ n: (1) t 0 = (q 0 , (#, φ 0 ), q 1 ) and ti =(qi , (ai , φ i ), qi+1 ); and (2) G |= φ i (vi , νi−1 , νi , µ i−1 , µ i ). We write[[A]]G to be the set of all pairs (u, v) ∈ V 2 of vertices in G suchthat there is a path π from u to v such that G, π |= A.
An RDPQ query is a formula F of the form x → A y, suchthat [[F ]]G = [[A]]G . We are concerned with the query evaluation
problem: given a graph G, a pair of vertices (s, t ) ∈ V 2 , and an
RDPQ formula F := x → A y, whether (s, t ) ∈ [[F ]]G .
Unsurprisingly, this problem is undecidable for a fixed A, evenfor the decidable theory ⟨N, succ⟩ of natural numbers with successors, since two unrestricted registers can be used to simulate
universal Minsky’s 2-counter machines (e.g. see [41]). For this reason, we impose the so-called bounded-rewrite restriction for theunrestricted registers. In the sequence of register values in (∗), aregister pi undergoes b rewrites if the number of value changes ofpi in the sequence is b. For example, if the values of p in an A-run
are 7, 7, 7, 3, 3, 10, 1, then p undergoes 3 rewrites. In the sequel, we
will restrict ourselves to runs of A with at most b rewrites for eachunrestricted register, for some constant b ∈ N. We will refer tosuch A as (h, b)-rewrite register automaton, where h is the numberof unrestricted registers of A. We will tacitly assume that each
RDPQ(L, T, σ )-query uses an (h, b)-rewrite register automaton because of the following:
Proposition 2.3. Let L = FO(T, σ ) or L = EFO(T, σ ), and assume that query evaluation for L is decidable. Then, query evaluation
for RDPQ(L, σ ) with (h, b)-rewrite register automata is decidable.
This can be easily proven: it suffices to consider paths in thegraph of length at most |U |l × |Q | × (b + 1)h (remember, l = |R |)and hence we turn each such path π into a formula in L to check if
there is a sequence of A-configurations conforming to π .
In this paper we are concerned mostly about the issue of data
complexity: What is the complexity of the evaluation problem fora fixed RDPQ(T, σ )-query? We count the view definitions in G
also as part of the query, which is consistent with PGQL (seehttps://pgql-lang.org/). Following [36], NL data complexity is of particular interest, which is achieved for the basic RDPQ (i.e. with thebase theory ⟨N; =, {c i }i ∈N ⟩, and σ = ⟨E 1 , . . . , En ⟩). When considering data complexity, the following proposition shows that we may
assume (h, 0)-rewrite register automata, i.e., each unrestricted register behaves like a parameter, a notion that appears in parametric
one-counter automata [27] and parametric timed automata [1].
Proposition 2.4. RDPQ(L, T, σ ) with (h, b)-rewrite register automata is (effectively) equi-expressive with RDPQ(L, T, σ ) with (hb, 0)rewrite register automata.
In the sequel, we assume that each unrestricted register is aparameter and we simplify notation accordingly (e.g. the guard ineach transition is of the form φ(curr, P, R, R ′ )).
Example 2.5. Following Example 2.1, we are interested in finding
the set of pairs (x, y) of actors whose age difference is at least 30.
This can be expressed in RDPQ(ZLA , σ ) as x → A y, where A has
three states q 0 , q 1 , q F (q 0 initial and q F final) and one active-domain
register r . The automaton A is depicted in Figure 2. Intuitively,
A saves the birthyear of the actor x, follows the edges in E, andnondeterministically guesses an actor y whose birthyear differs by<latexit sha1_base64="8jujb5NFm+QwSBZtQ2SOrr+QXAs=">AAACfXicbVHLTttAFJ0YWlL3waNLNhYRVRcoslEEbCKQ2HQZEAGk2ELjyTUZMR6bmTuBYOUX2EL7J/2Ufk0ZOxGicY800tE59965jzgXXKPv/2k4S8vv3q80P7gfP33+srq2vnGuM6MY9FkmMnUZUw2CS+gjRwGXuQKaxgIu4pvj0r8Yg9I8k2c4ySFK6bXkCWcUSynELL9aa/ltv4JXJ8GctA5//yzxq3e13mDhMGMmBYlMUK0HgZ9jVFCFnAmYuqHRkFN2Q69hYKmkKeioqJqdettWGXpJpuyT6FXq24yCplpP0thGphRHetErxf95A4PJQVRwmRsEyWYfJUZ4mHnl5N6QK2AoJpZQprjt1WMjqihDux/XdcNTuDU2pjevdxZERdliVWzRROwmVGjYqWoHXVQGokLwGOwSJNQTxlTdmqh44J2695oWFRLu8L4a0Z4lWDxCnZzvtoO9duek0zr6RmZokk2yRb6TgOyTI/KD9EifMDIij+SJPDf+OtvOjtOehTqNec5X8g+c/Rd36MmG</latexit>@0<latexit sha1_base64="AqtQxc36Y9A2h5WPWLEA1b+mhOA=">AAACfHicbVFNb9NAEF0bCq1paUuPXCxSpEjQyEZR4VJRqReOAZo2UmJF6804WWW9dnZnC8HqT+i1VftP+Cn8GcTaiVAb90krPb03MzsfcS64xiD447hPnq49e76+4b3Y3Hq5vbP76kxnRjHoskxkqhdTDYJL6CJHAb1cAU1jAefx9KT0zy9AaZ7JU5znEKV0LHnCGUUrfZ8Ng+FOI2gFFfw6CZek8fn3bYm7znDXYYNRxkwKEpmgWvfDIMeooAo5E3DpDYyGnLIpHUPfUklT0FFR9Xrpv7XKyE8yZZ9Ev1LvZxQ01XqexjYypTjRq14pPub1DSafooLL3CBItvgoMcLHzC8H90dcAUMxt4QyxW2vPptQRRna9XieN/gGM2NjOst6p2FUlC1WxVZNxKOECg3vq9rhESoDUSF4DHYJEuoJF1TNTFT84u269z8tKiT8wJ/ViPYs4eoR6uTsQys8bLW/thvHTbLAOnlN3pAmCclHcky+kA7pEkbG5Ipckxvnr7vvvnMPFqGus8zZIw/gHv4D5LbIzw==</latexit>

0

9I (⇢1 (curr, I) ^ A = I)<latexit sha1_base64="qIhS1X7s10I8BX2tNXmSNhItLY0=">AAACqXicbVHLbtNAFJ2YV2seTWHJZkSESEUV2SgCNhGVEBLLFDVtRGxF48l1O+p47M7cKUms8BXdtH8CW/gJ/oaxEyFIuNJIR+fce+5jkkIKg0Hwq+Hdun3n7r2tbf/+g4ePdpq7j49NbjWHAc9lrocJMyCFggEKlDAsNLAskXCSnL+v9JNL0Ebk6ghnBcQZO1UiFZyho8bNTgRT18XQOf3a/jBO2hHC1PmU3Gq92J/v0UgyNaH6Be3R+d642Qo6QR10E4Qr0Hr37bqKm/54t8GjSc5tBgq5ZMaMwqDAuGQaBZew8CNroGD8nJ3CyEHFMjBxWS+2oM8dM6Fprt1TSGv274qSZcbMssRlZgzPzLpWkf/TRhbTt3EpVGERFF82Sq2kmNPqSnQiNHCUMwcY18LNSvkZ04yju6Xv+9EnuLAup7/yOwrjshqxNlsXEXspkwb2a++wh9pCXEqRgDuCgs2CS6YvbFzORXdT+1MWlwq+4LRe0X1LuP4Jm+D4VSd83ekedlsHbbKMLfKUPCNtEpI35IB8JH0yIJxcke/kB/npvfQOvaH3eZnqNVY1T8g/4fHfZC/Yrg==</latexit>><latexit sha1_base64="IbJOy7pgQ96lYsCW/HY7v/D1rJo=">AAACsHicbVHLbtNAFJ2YVzGvFJZsRkRIqVQiu4THpqISQmIZUNNGii1rPLlJh47HzsydksQN/wF8CUu28AX8DWMnQpBwpZGOzrn33MekhRQGg+BXw7ty9dr1Gzs3/Vu379y919y9f2Jyqzn0eS5zPUiZASkU9FGghEGhgWWphNP0/HWln16ANiJXxzgvIM7YRImx4AwdlTSfRTBzXQxd0E/tN0najhBmzqfkVuvl/mKPRpKpEb3UTxaXNJrAlD4N9pJmK+gEddBtEK5B69W3z1V86SW7DR6Ncm4zUMglM2YYBgXGJdMouISlH1kDBePnbAJDBxXLwMRlvd+SPnbMiI5z7Z5CWrN/V5QsM2aepS4zY3hmNrWK/J82tDh+GZdCFRZB8VWjsZUUc1odi46EBo5y7gDjWrhZKT9jmnF0J/V9P3oPU+tyemu/4zAuqxFrs00R8XDMpIH92js8RG0hLqVIwR1BwXbBBdNTG5cL0d3W/pTFpYKPOKtXdN8Sbn7CNjg56ITPO9133dZRm6xihzwkj0ibhOQFOSJvSY/0CSdfyXfyg/z0DryBl3hsleo11jUPyD/hffgNpGfbsQ==</latexit>@1<latexit sha1_base64="BiCZvOh2VE97CYPpq44MGyiaKvU=">AAACfHicbVHLTttAFJ0YCtS0QOiSjUWKhASNbBQBGwRSNyzDI4CUWNF4ch1GjMfOzJ1AsPiEblu1f8Kn8DOIsROhNumRRjo659479xFlgmv0/ZeKMzf/YWFx6aO7/Onzyupadf1Kp0YxaLFUpOomohoEl9BCjgJuMgU0iQRcR3ffC/96CErzVF7iKIMwoX3JY84oWuli0A26azW/7pfwZkkwIbXj598F/jS71Qrr9FJmEpDIBNW6HfgZhjlVyJmAJ7djNGSU3dE+tC2VNAEd5mWvT96WVXpenCr7JHql+ndGThOtR0lkIxOKt3raK8T/eW2D8WGYc5kZBMnGH8VGeJh6xeBejytgKEaWUKa47dVjt1RRhnY9rut2zmFgbExzUu8yCPOixbLYtIl4FFOhYbesHRyhMhDmgkdglyBhNmFI1cCE+SNvzHrvaWEu4R4fyhHtWYLpI8ySq716sF9vnDVqJ9tkjCWyQTbJNgnIATkhp6RJWoSRPvlBfpJflVfnq7PjfBuHOpVJzhfyD5z9N+bMyNA=</latexit>

9I (⇢1 (curr, I) ^ |A

I|

30)

@
<latexit sha1_base64="Y26t0XYOIa/zmac8dkFvd++pb8Q=">AAACfHicbVFdS+NAFJ1mdVeju6vroy/BKgi6JVmK64soLIiP9aMqtKFMpjd1cDJJZ+6oNfgT9nUX/Sf+FP+MOEmLaOuBgcM59965H1EmuEbff6o4n6amP3+ZmXXn5r9++76w+ONUp0YxaLJUpOo8ohoEl9BEjgLOMwU0iQScRZd/Cv/sCpTmqTzBQQZhQnuSx5xRtNJxv7PfWaj6Nb+EN0mCEanuPt4XeGh0Fius3U2ZSUAiE1TrVuBnGOZUIWcC7ty20ZBRdkl70LJU0gR0mJe93nlrVul6carsk+iV6tuMnCZaD5LIRiYUL/S4V4gfeS2D8XaYc5kZBMmGH8VGeJh6xeBelytgKAaWUKa47dVjF1RRhnY9ruu2j6BvbExjVO8kCPOixbLYuIm4E1OhYbOsHeygMhDmgkdglyBhMuGKqr4J81ten/Re08JcwjXelCPaswTjR5gkp79qwVatfliv7q2TIWbIMlkh6yQgv8keOSAN0iSM9Mhf8o/8rzw7q86G83MY6lRGOUvkHZytFxKpyOU=</latexit>

Figure 2: Automaton A for the query in Example 2.5.
at least 30 from the birthyear of x. It can be seen that (0, 1) is ananswer to this query (recall that 0 and 1 refer to Erdős and Bacon).
Example 2.6. Following Example 2.2, suppose we are interested
in finding a period of at least 28 days where the total numberof active COVID cases grows exponentially. It is a well-known
open problem (e.g. see [25, Chapter 5]) whether R×,+ with the exponential function e x is decidable. To circumvent this, we could
use the standard trick in numerical methods to approximate λe χ xby the nth Taylor polynomial pn (x ) for sufficiently large n, i.e.,Pni
i=0 λ(χx ) /i!. (In practice, one uses small enough n, e.g., n = 4
is used in [5].) Let д(λ, χ, x ) := pn (x ), with λ and χ treated also
as variables. An example query could be to find any window between two time stamps (t, t ′ ) ∈ E spanning across at least 28 days
(i.e. t ′ − t ≥ 28) such that there exist λ ≥ 1, χ > 0.4 such thatthe total number of active COVID cases at each time step s inthis interval is within B := 50 from д(λ, χ, s) + c for some nonnegative constant c. This can be expressed in RDPQ(R×,+ , σ ) as
x → A y, where A has three states q 0 , q 1 , q 2 (q 0 initial and q 2 final), one active-domain register r and three parameters λ, χ, c. The
transitions are (q 0 ,ψ 0 (curr, P, r , r ′ ), q 1 ), (q 1 ,ψ 1 (curr, P, r , r ′ ), q 1 ),(q 1 ,ψ 2 (curr, P, r, r ′ ), q 2 ), whereψ 0 := r = curr ∧ λ ≥ 1 ∧ χ > 0.4 ∧ c ≥ 0 ∧ θ
ψ 1 := r ′ = r ∧ θ,

ψ 2 := ψ 1 ∧ curr − r ≥ 28

θ := ∃x ∈ adom(T (curr, x ) ∧ |д(λ, χ, curr) + c − x | ≤ B).

3

REALS AND LINEAR ARITHMETICS

This section deals with real-closed field R×,+ = ⟨R; +, ×, ≤, 1, 0⟩ andinteger linear arithmetic ZLA = ⟨Z ; +, ≤, 1, 0, {≡k }⟩, where ≡k is
the congruence modulo k relation. Both admit (effective) quantifier
elimination (QE) [22, 29]: each formula φ(x̄ ) can be effectively
converted into an equivalent quantifier-free formula in the theory.
Notice that each side of an (in)equation can be any general term in
the theory: a multivariate polynomial with integer coefficients inthe case of R×,+ , and a linear multivariate polynomial with integer
coefficients in the case of ZLA . In the case of R×,+ each elementin the database is a rational number, i.e., given as a/b with two
integers a, b. The size of a number is the number of bits required torepresent it. Our main result is:
Theorem 3.1. The data complexity of RDPQ(FO, R×,+ , σ ) andRDPQ(FO, ZLA , σ ) is NL-complete.
The remainder of §3 presents a sketch of proof of Theorem 3.1.
Restricted Quantifier Collapse. We recall the notion of Restricted
Quantifier Collapse (RQC) only for theories T that admit QE; see [35,Definition 13.5] for a general definition, which is not crucial for thepaper, and [35, Chapter 13.4] for positive and negative examples
as well as some properties of RQC. We also give a definition thatapplies to fragments of FO. The logic L ⊆ FO(T, σ ) admits RQC

if L ⊆ FOact (T, σ ), i.e., for every formula φ(x̄ ) ∈ L, there exists
ψ (x̄ ) ∈ FOact (T, σ ) (i.e. without unrestricted quantifiers) such that[[ψ ]]S = [[φ]]S for each finite (T, σ )-structure S. We write “effectively
admits RQC” if the translation from φ to ψ is effective.
Proposition 3.2 ([9, 24]). Both FO(R×,+ , σ ) and FO(ZLA , σ ) effectively admit RQC, and have data complexity TC0 .
The proofs of RQC can also be found in the textbook [35, Theorem 13.19] and in the textbook [25, Proposition 5.32], from whichdata complexity immediately follows, e.g. see [9, 10] for FO(R×,+ , σ ).
The same analysis as in [9, 10], combined with that modulo comparisons are in TC0 (e.g. see [43]), also gives TC0 data complexity
for FO(ZLA , σ ). RQC provides us sometimes with a tool for coming
up with an NL algorithm for RDPQ, as we shall see the case for
R×,+ and ZLA , but this is not always the case (see next section).
Restricted Register Collapse. We define an analogue of RQC for
RDPQ(L, T, σ ). Let RDPQact (L, T, σ ) refer to queries x → A y in
RDPQ(L, T, σ ) such that A has no parameters and L admits RQC.
We say that RDPQ(L, T, σ ) admits Restricted Register Collapse (RRC)
if RDPQ(L, T, σ ) ⊆ RDPQact (FOact , T, σ ). The following lemma is
crucial in obtaining NL data complexity of RDPQ(FO, R×,+ , σ ) andRDPQ(FO, ZLA , σ ).
Lemma 3.3. Both RDPQ(FO, R×,+ , σ ) and RDPQ(FO, ZLA , σ ) admit RRC effectively.
The proof of the lemma is quite technical, and borrows someideas from the proofs of RQC for FO(R×,+ , σ ) and FO(ZLA , σ ). Essentially, it is shown that one can restrict the parameter valuations
to a bounded number of values while preserving equivalence. Although the exact values might depend on the database S, they canbe uniformly FO-defined through the values of active domains, i.e.,
in FOact (R×,+ , σ ) or FOact (ZLA , σ ). This allows us to replace eachparameter by active-domain registers.
We now proceed the proof of RRC for T := R×,+ ; the proof for
ZLA is similar (see full version). Fix a vocabulary σ and a (T, σ )register automaton
A = (R, P, Q, Q 0 , F , ∆)with P = {p1 , . . . , pk }. By RQC of FO(T, σ ), it follows that each
formula φ(curr, P, R, R ′ ) in ∆ can be assumed to have only activedomain quantifiers. We shall construct a (σ , T)-register automaton
A ′ = (R ′, P \ {pk }, Q ′, Q 0′ , F ′, ∆ ′ ),such that [[A]]G = [[A ′ ]]G for all T-embedded graph G over σ . By
recursively eliminating the parameters, we will obtain an equivalent(σ , T)-register automaton with no parameters. Let Z = P ∪ R ∪R ′ ∪ {curr } and Z k := Z \ {pk }.
We may assume (e.g. see proof of [35, Theorem 13.19]) that eachφ(curr , P, R, R ′ ) is of the form
Q 1y1 ∈ adom . . . Qm ym ∈ adom α (ȳ, pk , Z k )where each Q 1 , . . . , Qm denotes an ∀ or ∃ quantifier and α is a
Boolean combination of formulas of(1) atomic σ -formulas R(ū) with ū ⊆ ȳ (e.g. E (pk , r ) is replacedby ∃z, z ′ ∈ adom(E (z, z ′ ) ∧ z = pk ∧ z ′ = r )); and(2) expressions of the form t (ȳ, Z k , pk ) ∼ 0, where t is polynomial with integer coefficients whose variables are among ȳ,Z k and pk , and ∼ ∈ {=, >}.
We will further assume that each term t that appears in someformula (of a transition) in A appears in each formula in A, e.g.,
if t does not appear in a formula ψ , we may simply rewrite it withψ ∧ (t = 0∨t , 0). By the same token, we may for simplicity assume
that each formula φ in A uses the same number m of active-domain
variables y1 , . . . , ym . Letting Yk = ȳ ∪ Z k , we may enumerate all
polynomial terms t involving pk occurring in A as
t 1 (Yk , pk ), . . . , tm (Yk , pk ),where ti has degree di in pk . We introduce two new active-domain
registers r 1 (z) and r 2 (z) for each z ∈ Yk . Let r i (Yk ) denote the set
containing each r i (z) with z ∈ Yk . The crux is to replace pk byeither one of the terms in the set S defined asrootsi (r 1 (Yk )) + roottj (r 2 (Yk )) i, j ∈ [1, m],






:

s ∈ [1, di ], t ∈ [1, d j ] 2∪ {rootsi (r 1 (Yk )) + c : c ∈ {−1, 1} ∧ i ∈ [1, m], s ∈ [1, di ]}where rootsi (Yk ) represents the sth root of ti (Yk , pk ) (treated as a
univariate polynomial in pk ), if exists, otherwise 0. It is easy to
see that there is a FO(R×,+ ) formula Rootsi (Yk , x ) which is true
iff x equals rootsi (Yk ). By quantifier elimination, we may assume
Rootsi (Yk , x ) is quantifier-free. At this point, we state a result fromembedded finite model theory, which we will use later:
Proposition 3.4 (See Lemma 13.20 of [35]). Let S be an finite
structure such that adom(S) , ∅ embedded into T = R×,+ . For
each valuation µ : Z k → R, it is the case that S, µ |=T ∃pk φ iff
WS, µ |=T t ∈S φ[t/pk ], where φ[t/pk ] is φ but with pk replaced by t.
Note that, in this proposition, we interpret an active-domain
register as an active-domain variable.
We now complete the construction of the new register automatonthat replaces pk by active domain registers. Define Q ′ := Q × S,
Q 0′ = Q 0 × S, and F 0′ := F 0 × S. For each transition (q, φ(Z k , pk ), q ′ )and each t ∈ S, we add to ∆ ′ the transition((q, t ), φ ′ (Z k , r 1 (Yk ), r 2 (Yk ), r 1 (Yk′ ), r 2 (Yk′ )), (q ′, t ))where φ ′ is constructed as follows depending on t:
rootsi (r 1 (Yk ))+roottj (r 2 (Yk ))V• t =. Let φ ′ := 2α =1 r α (Yk ) =2r α (Yk′ )∧!
φ(Z k , z)∧Rootis (r 1 (Yk ), z 1 )∧∃z, z 1 , z 2
Root jt (r 2 (Yk ), z 2 )∧ 2z = z 1 + z 2
V• t = rootsi (r 1 (Yk )) + c. Let φ ′ := 2α =1 r α (Yk ) = r α (Yk′ )∧∃z, z 1 (φ(Z k , z) ∧ Rootis (r 1 (Yk ), z 1 ) ∧ z = z 1 + c)
By RQC of FO(R×,+ , σ ), we may assume each φ ′ has only activedomain quantifiers.
We claim now that [[A]]G = [[A ′ ]]G for all (T, σ )-graph G. The
direction [[A]]G ⊇ [[A ′ ]]G is immediate since A ′ restricts therange of values that are permitted to pk in A (i.e. to values in
S, where each r h (Yk ) can be instantiated by any active-domain

values). To prove the other direction [[A]]G ⊆ [[A ′ ]]G , assume an
accepting computation of A
π := (q 0 , ν 0 ) → (a1,φ 1 ) · · · → (an ,φ n ) (qn , νn )for a valuation µ : P → R, i.e., (R×,+ , G), µ |= ∃pk Φ(Z k , pk ), whereΦ(Z k , pk ) is:∃s̄, R̄ ∈ adom

n−1
^
i=0

(φ i (si , Ri , Ri+1 , P) ∧ Eai (si , si+1 )).

By assumption, Φ shares the same polynomial terms with any oneof φ i (up to renaming curr , R and R ′ with respectively si , Ri , andRi+1 ). Using Proposition 3.4, there exist i, j ∈ [1, m], i ∈ [1, di ],j ∈ [1, d j ], and two tuples ā, b̄ over adom(G), each of length |Yk |,such that (R×,+ , G) with valuation µ satisfies_
Φ(Z k , (rootsi (ā) + roottj (b̄))/2) ∨Φ(Z k , rootsi (ā) + c)c ∈ {−1,1}

Hence, A ′ may simply instantiate r 1 (Yk ) (resp. r 2 (Yk )) with ā(resp. b̄) and keep them constant throughout the computation, as
is done in the definition of A ′ . Extend each νi with this instantiation yielding νi′ . Let µ ′ := µ |Z be the restriction of µ to Z k . Thekfollowing path is then an accepting path of A ′ with valuation µ ′ :π ′ := (q 0 , ν 0′ ) → (a1,δ 0′ ) · · · → (an ,δn′ ) (qn , νn ).
This completes the proof of Theorem 3.3.
NL algorithm. Theorem 3.1 is a direct consequence of the following lemma, Proposition 3.2, and Lemma 3.3.
Lemma 3.5. We assume a sublogic L of FO(T, σ ) with NL data
complexity. Then, RDPQ(L, T, σ ) without parameters is NL-complete.
It remains NL if we allow parameters that can be instantiated by data
values whose sizes are logarithmically bounded.
Proof idea. One nondeterministically simulates a run of A ina query x → A y over RDPQ(L, T, σ ), while using the NL algorithm
for L as a subprocedure. References to active-domain values are
saved in the working tape, hence keeping the algorithm running in
NL. Full proof is in the appendix.
□

4

THEORY OF AUTOMATIC RELATIONS

We consider the theory of automatic relations on finite words. Let˙Γ be a finite alphabet, and Γ⊥ be Γ ∪{⊥}.
Given u 1 , . . . , uk ∈ Γ ∗ ,the convolution u 1 ⊗ · · · ⊗ uk of these words is defined as the wordw ∈ (Γ⊥k ) ∗ such that the projection onto the i-th component of w
yields ui · ⊥ |w |−|ui | , for every 1 ≤ i ≤ k. An automatic relation ofarity k is a relation R ⊆ (Γ ∗ ) k such thatR = {(u 1 , . . . , uk ) : u 1 ⊗ · · · ⊗ uk ∈ L}(1)

for some regular language L over (Γ⊥ ) k . Let Rel be the set of
all automatic relations over some fixed alphabet Γ. TAut is then
the theory ⟨Γ ∗ ; {R}R ∈Rel ⟩. Some examples of automatic relations
are the prefix relation · ⪯ ·, the equal length relation eq-len(·, ·)and the unary relation lsta (·) stating that the last letter of theword is an a ∈ Γ. In fact, in the relational calculus, these relations coincide with the automatic relations, in the sense that thefollowing are equivalent: (1) R is an automatic relation from Relof arity k; (2) there is φ(x 1 , . . . , x k ) ∈ FO(Γ ∗ , ⪯, eq-len, {lsta }a ∈Γ )such that R = [[φ]] = {ū ∈ (Γ ∗ ) k : Γ ∗ |= φ[ū]} [21]. This is whyFO(Γ ∗ , ⪯, eq-len, {lsta }a ∈Γ ) is sometimes called the “universal automatic structure” [12]. Another example of an automatic relation isthe edit-distance-k binary relation (see [7]), for any fixed k. Observethat regular languages are exactly the class of automatic relationsof arity 1.
We assume that words are represented as a list of letters, andrelations as lists of lists of words. The size of a word is its length.
We represent automatic relations inside formulas via an NFA recognizing the language L in (1).
Example 4.1. Consider a phylogenetic database, with each node
defining a DNA sequence (and perhaps some other data). Using
FO(TAut , σ ) we can query, whether the DNA sequence of the current element is at edit distance at most 5 from parameter p:φ(curr, p) = ∃y dna-seq(curr, y) ∧ edit-distance-5(y, p),
where dna-seq(curr, y) specifies that y is the DNA sequence of thecurrent node curr and edit-distance-5(·, ·) is an automatic relation(of being at edit distance at most 5).
Unfortunately, model checking of FO over TAut -embedded structures is hard for the polynomial hierarchy (PH) [11, Prop. 4.12],
implying untractability for RDPQ querying:
Proposition 4.2 ([11]). RDPQ(FO, TAut , σ ) is hard for every levelof PH in data complexity, even without parameters.
Hence, we focus on the EFO fragment of FO-formulas in prenex
form using no universal quantifiers. The set of EFO formulas using
no negation is denoted by EFO+ .
Lemma 4.3 (proof in Appendix). EFO(TAut , σ ) has effective RQC.
Thus, model checking for EFO is tractable, since model checking
for FOact (TAut , σ ) is in NC1 .
Lemma 4.4. [11, proof of Corollary 4.15] The model checking problem for FOact (TAut , σ ) is in NC1 in data complexity.
By Lemma 4.3, every EFO(TAut , σ ) formula is effectively equivalent to a FOact (TAut , σ ) formula which in turn, by Lemma 4.4, isin NC1 , hence in NL. Thus, by Lemma 3.5 the bound transfers to
RDPQ evaluation.
Corollary 4.5 (of Lemma 4.3, Lemma 4.4, and Lemma 3.5). Evaluation of RDPQ(EFO, TAut , σ ) and RDPQ(FOact , TAut , σ ) withoutparameters is NL-complete in data complexity.
However, as soon as unrestricted parameters are allowed, welose tractability, as we show next (proof in Appendix B.2).
Lemma 4.6. Evaluation of RDPQ(EFO+ , TAut , σ ) is NP-hard indata complexity, even with no registers and one parameter.
To regain tractability we assume LogH on the (TAut , σ )-structure
S, that is, that for some constant c, every word w ∈ adom satisfies|w | ≤ c · log(|S|). In fact, LogH implies that parameters can be taken
to have a logarithmic size, and in light of Lemmas 4.3 and 3.5, wededuce that RDPQ(EFO, TAut , σ ) evaluation (under LogH) is in NL.
To prove this, we use a corollary of the proof of Lemma 4.3 (inAppendix B.1):

Corollary 4.7 (of Lemma 4.3). Every EFO(TAut , σ ) formulaψ (z̄) is effectively equivalent to a disjunction of EFOact (TAut , σ )formulas ψ ′ of the form A′ (z̄) ∧ ∃¯r ∈ adom τ (z̄r¯), where A′ is a
TAut -atom, τ is a EFOact (σ ) formula.
Let N = maxw ∈adom |w | and let v : z̄ → Γ ∗ be a satisfying
assignment for ψ ′ (z̄), and z ∈ z̄ such that |v (z)| > N . Suppose
there is a word u ∈ Γ ∗ such that |u| > N and Γ ∗ , v ′ |= A′ (z̄) forv ′ = v[z 7→ u]. Then, v ′ is also a satisfying assignment for ψ ′ .
Theorem 4.8. Evaluation of RDPQ(EFO, TAut , σ ) with parameters under LogH is NL-complete in data complexity.
Proof. Let G be a TAut -embedded graph over σ , F = ∃P :x → A, P y be an RDPQ(EFO, TAut , σ ) query, and (s, t ) ∈ V 2 be
two vertices of G. Let N be the maximum size of a word in theactive domain (of logarithmic size by LogH).
Let s = v 0 →a1 · · · →an vn = t be an accepting G-path withtransitions t 0 , . . . , tn , where ti = (qi , (ai ,ψi ), qi+1 ) and a 0 = #.
Then for some register valuations µ 0 , . . . , µ n+1 ∈ V R the formulaV
φ(P) = i ψi (vi , P, µ i , µ i+1 ) is satisfiable. We show that if φ issatisfiable, then it is satisfied with a valuation for P with log-sizewords.
Suppose there is a parameter valuation ν ∈ U P which satisfies
φ. By Corollary 4.7, for each i, ψi can be written as a disjunctionof formulas of the form Ri (z̄) ∧ ∃¯r ∈ adom τ (z̄r¯) where Ri is a
TAut -atom and τ is a FOact (σ ) formula. Consider the DFA Ai overΓ⊥ni corresponding to the relation denoted by Ri , let it have ni freevariables. Let v̄i be a satisfying assignment for ȳi . Hence, there
is an accepting run of Ai over the convolution w of the words
vi ν µ i µ i+1v̄i . These words are of logarithmic size, since they arefrom adom, with a possible exception of those from ν , which areparameters. Let w ′ be the N -prefix of w, and let qi be the stateof Ai after reading w ′ from the initial state. We define Ai′ to be
the same automaton as Ai but (1) setting qi as initial state, and (2)removing any transition reading a non-⊥ symbol on any component
which is not of the parameters. It then follows that, if w ′′ is any
word in the language of Ai′ , then w ′ · w ′′ is in the language of
Ai . Let π (Ai′ ) be the automaton corresponding to the projection
onto the components of the parameters of L(Ai′ ). Consider a wordTu ∈ i L(π (Ai′ )) ⊆ (Γ⊥| P | ) ∗ ; observe that its description is bounded
by a function of the (fixed) RDPQ F , and hence u is of constant size.
It then follows, by Corollary 4.7, that u ′ ·u witnesses also a satisfying
assignment for φ, where u ′ is the N -prefix of ν . This shows that we
can assume that the parameter valuation for witnessing a word in
the language is also of logarithmic size. Since parameters can betaken to have a logarithmic size, by Lemmas 4.3, 4.4, and 3.5 we getan NL bound.
□

5

WORD EQUATIONSThis section deals with the theory of word equations with concatenation and regular languages, i.e., let TWE be the theory of⟨Γ ∗ ; ·, {R}R ∈Reg ⟩, where Γ is a finite alphabet, · is the concatenation, and Reg is the set of all regular languages (over Γ). The data
complexity of FO(TWE , σ ) is undecidable [11], so we consider two+
fragments of FO(TWE , σ ): (1) L+
WE = EFOact (TWE , σ ) of existential
positive formula with active-domain quantifiers, and (2) LPM of

existential positive formulas without regular relations and whose alV
lowed TWE -formulas have atoms of the form ∃ȳ( i ∈I x i = βi ) withthe left-hand side x i being a single element from curr ∪ R ∪ R ′ ∪ P
and the right-hand side βi being a concatenation of elements inȳ ∪ R ∪ R ′ ∪ {curr} and constants, and that each existentially quantified variable occurs at most once in an equation whose left-handside is from P. (Note that it can occur at multiple equations inwhich the left-hand side is from curr ∪ R ∪ R ′ .)Example 5.1. Consider a query in a phylogenetic database, defined in Example 4.1: is there a path, such that all DNA sequences on
it are at edit distance at most k from some (unknown) DNA sequence?
Answering such query is related to the closest string problem [15,26]. It is known [7, Eq. (3)], that the edit distance between p, w is at
most k if and on only if_∃x 0 , . . . , x k p = x 0a 1x 1 · · · x k −1ak x k ∧a 1, ...,a k ∈Γ∪{ε }b1, ...,bk ∈Γ∪{ε }w = x 0b1x 1 · · · x k −1bk x k .

When p is a parameter and w in curr, this formula is in LPM and so
this query is expressible in RDPQ(LPM , TWE , σ ).
Theorem 5.2. RDPQ(L+WE , TWE , σ ) has NL-complete data complexity, similarly RDPQ(LPM , TWE , σ ).
Proof idea. As in both cases the guards on a G-path are positive formulas, the guard on any G-path π are a positive Boolean
combination of word equations over some variables and traversing
such a path can be seen as constructing a system of word equations.
In particular, given a valuation of the parameters and existentiallyquantified variables such that G, π |= A we can determine, which
atomic equations were true and this valuation can be seen as asolution to the system of word equations (i.e. the equations thatare made true in the guards). Hence evaluating a query can be seen
as solving a system of word equations, though this system is not
given explicitly. The best algorithms solving word equations run
in PSPACE, so in order to answer RDPQ queries in NL, we needsome insight into the structure of the systems of equations that we
obtain in this case. Those turn out to be different for L+
WE and LPM .
For LPM : each atomic equation is of the form p = β or α = β,where p is a parameter, α ∈ curr ∪ R ∪ R ′ and β is a sequence of(existentially quantified) variables and elements from Γ ∪ curr ∪R ∪ R ′ . In the second case α ∈ adom(S), so every (existentiallyquantified) variable in β is a substring of an element in adom(S), so it
can be represented in NL. For equations p = β, fix a parameter p andconsider all such equations in the system created while traversing
the G-path. Every variable at the right-hand side is used once in thesystem and not used in any other such subsystem. Such system issatisfiable if and only if each of the equations satisfies a condition
on a prefix and suffix of its sides; in particular, we do not needto consider all the equations simultaneously, they can be checked
one by one, see Lemma C.1 in the appendix. The NL algorithm
guesses for each parameter p an appropriate prefix and suffix, it
can be shown that those can be represented as concatenations of at
most |A| many constants and substrings of elements from adom(S).
Then in G it guesses consecutive edge views and evaluates theguard φ using the condition on prefixes and suffixes mentioned
above, i.e. the one from Lemma C.1.

Concerning L+
WE , for simplicity of presentation, we ignore regular relations; the appendix contains a brief discussion how to
generalize to this case. The (existential) active domain quantifiers
are instantiated by elements of adom(S) using nondeterministic
guesses. Therefore the equations occurring in guards are only invariables that are parameters. We first observe that if words substituted for parameters are polynomial-length and there is an NL
access to individual letters in them, then RDPQ(L+WE , TWE , σ ) has
NL data complexity, as desired.
Lemma 5.3. Assume a logarithmic-size representation of valuations of parameters P, such that each parameter is of polynomial(in |G|) length and individual letter of each parameter and length ofeach parameter can be accessed in NL. Then we can evaluate a given
RDPQ(L+WE , TWE , σ ) query for those parameters on G in NL.
Proof. We guess consecutive vertices on a G-path. At a given
node we guess the next node in G, the letter and transition of A,
which yields a guard φ that should be satisfied. To verify φ, we
guess the existentially quantified variables, which are an elementfrom adom, and then evaluate the atomic equations in the guards
one by one. For a given equation u (x̄ ) = v (x̄ ) we already havethe substitutions for each variable in x̄, which is either an activedomain quantified (so was guessed) or a parameter (so we have avaluation for it). Hence we verify the equation symbol by symbol,
which can be done in NL, as each substituted value is of polynomial
length and individual letters can be accessed in NL. As each atomof φ is evaluated in NL, we can also evaluate φ in NL.
If we have ended in t then the traversed path π yields G, π |= A.
On the other hand, if there is π such that G, π |= A then we guess
π ’s consecutive nodes, the transitions of A and substitutions forvariables, for which we end up at t, as desired.
□
We show that if there is an accepting G-path π , and parameter
valuation ν : P → Γ ∗ such that G, π |= A then this also holds for avaluation ν ′ such that each assigned value is polynomial-size andits letters can be accessed in NL.
So assume such a path π and corresponding sequence of transitions in A. For any guard φ take the equations made true under ν ,they form a system of word equations in k variables P; the sum oflengths of equations is polynomial in |G|: the length |π | is polynomial (discussion after Proposition 2.3), and each atom in it is fromΓ ∗ ∪ curr ∪ R ∪ R ′ , hence of linear size. Lemma C.2 in the Appendix
show that such a system has a polynomial-size solution. Moreover,
it is known [40] that for (some) such solutions the length of thesubstitutions together with the system of equations uniquely determines the solution and yield access to letters in the substitutions,in this case the access is in NL; see the appendix. However, thesize of this representation is polynomial, as there are (potentially)polynomially many equations.
We exploit the form of equations in the system: fix an atomic
equation u (p̄, x̄ ) = v (p̄, x̄ ), where p̄ are from P and x̄ are fromcurr, R, R ′ and active domain quantified variables. For different
substitutions for x̄, the obtained equations have the same sequenceof variables (from P), separated with different words; call such
equations similar. We show that given two similar equations we
can deduce a partial valuation of variables, which makes those twoequations equivalent (in appropriate sense). By considering consecutive equations we get a partial substitution that makes increasing
set of equations equivalent. Moreover, this process “simplifies” theresulting equation and we can perform it O(m) times, where m isthe number of occurrences of variables in the equation. As a result,among a system of similar equations we can choose O(m) which
unify this system. This is done for each equation u (p̄, x̄ ) = v (p̄, x̄ ) inA, yielding a system of O(m|A|) equations, which can be used toaccess the substitution for parameters. See appendix for details. □6

GENERALIZATIONS AND CONCLUSIONS

We conclude by mentioning related issues and future work.
Conjunctive Queries. NL data complexity of RDPQ easily extends
to CRDPQ [36], which enriches RDPQ by conjunctions. Here weenrich RDPQ(L, T, σ ) not only by conjunctions, but also by anadditional constraint in L. Namely, queries in CRDPQ(L, T, σ ) areconjunctions of the formn^
Q (z̄) ←x i → Ai yi ∧ φ(P, x̄, ȳ)
i=1

where z̄ ⊆ x̄ ∪ ȳ, x i → Ai yi is an RDPQ(L, T, σ )-query, andφ(P, x̄, ȳ) ∈ L. Here, P contains all parameters used across all
register automata in Q, which may among themselves share parameters. Given a (T, σ )-structure S with active domain U , let [[Q]]S be
the set of all β : z̄ → U such that for some ν : x̄ ∪ ȳ → U , with
β (z) = ν (z) for each z ∈ z̄, and µ : P → D, it is the case that
S |= φ(µ (P), ν (x̄ ), ν (ȳ)) and ν (x i ) → Ai ν (yi ). In other words, eachpath constraint x i → Ai yi is satisfied where a parameter valuationµ that conforms to φ. One example of a CRDPQ query is the querythat there are two actors with finite Bacon graphs whose ages differ
from Bacon by an even number k, i.e., this is of the form
Q (y, z) ← x → A y ∧ x → A z ∧ k ≡ 0 (mod 2) ∧ x = Bacon,
where A uses one active-domain register r to save the birthyear
y0 of the first person in the path, and a parameter k that is nondeterministically guessed and is checked against the difference
between y0 and the birthyear of the final person in the path. We
sketch in the appendix a log-space reduction from CRDPQ(L, T, σ )to RDPQ(L, T, σ ) query evaluation, where the output query depends only on the input query. This extends NL data complexity to
CRDPQ(L, T, σ ).
Property Graphs. Property graphs are the data models used bymost modern graph database systems [17]. A property graph associates unique IDs to both nodes and edges in a graph, i.e., they areboth first-class citizens. The main difference to the standard datagraph model in database theory (e.g., see [36]) is three-fold. First,
some edges could be unordered and there could be multiple edges
from a node to another node. second, nodes (as well as edges) may
also carry labels from Σ. Finally, edges (as well as nodes) may be
associated with a property value. Since we allow first-order views,
we may easily view a property graph G as a data graph G ′ in thesense of [36] by interpreting nodes and edges in G as nodes in G ′ .
Indeed, view definitions allow a huge amount of flexibility, e.g., one
can reverse the edge relation, make an edge relation symmetric, etc.
This allows us to also obtain NL data complexity of RDPQ(L, T, σ )on the property graph data model.

Combined Complexity. The primary concern of our paper is developing data path query languages with NL data complexity. The
consideration of data complexity is standard and sensible for database query evaluation since typically the size of the database isvery large and the size of the query small. The combined complexity of our query languages is higher than that of the basic RDPQ
from [36] (i.e. PSPACE), primarily because of the high complexityof the theories that we consider, e.g., the best known algorithm for
FO(R×,+ ) is double-exponential time (see [8]) and FO(ZLA ) would
require at least double exponential-time [33]. We leave it for future work to identify fragments of FO(T, σ ) that could match the
PSPACE combined complexity of the basic RDPQ.
Integrating views into the automaton. Thus far, our presentation
has kept the view definitions G = (V , {Ea }a ∈Σ ) of the relational
database S rather “separate” from the automaton A in the queryx → A y. In effect, the automaton A is forced to explore the relational database S through the graph views as defined by G. Although
this is more in line with the data model of SQL/PGQ (e.g. see [17]and https://pgql-lang.org/), a further generalization that enables A
to directly traverse the relational structure S is possible, which wewill discuss next.
For a start, we dispense completely with the view definitions
over the database S. How does A then traverse S? The answer issimple. Each transition of A can be associated with a next variableindicating which element in S it can go to, i.e., it is of the form(q, φ(curr, next, R, R ′, P, P ′ ), q ′ ),where φ is a formula over the vocabulary σ of S. Notice that Σ does
not exist, and therefore an automata transition does not have anyΣ entry. The semantics of a transition is the same as defined in § 2,
except that by taking this transition the automaton A goes fromcurr to next. This setting is strictly more general than the setting
defined in § 2 in that the graph views allowed by this extended
automaton might depend on the register and parameter values. All
the results in this paper generalize easily to this extended data
model.
Future Work. We now mention several open questions. Firstly, inwhat way can our query languages be extended with aggregation(e.g., summing values along a path, taking average, etc.) without
sacrificing NL data complexity? To this end, we conjecture that
decidable subclasses of counter automata (e.g. [32, 42]) could prove
useful. Secondly, identify the fragment of the graph pattern matching language (GPML) over property graphs [17] that can be captured
in CRDPQ(L, T, σ ). Concerning word equations, can we extend themethods used for L+
WE to obtain NL data complexity for RDPQ overfragment with negation and/or with existential quantification?

ACKNOWLEDGMENTS
We are grateful to the anonymous reviewers for the helpful feedback.
We also thank Michael Benedikt, Leonid Libkin, Domagoj Vrgoč,
and Zhilin Wu for the discussion and insightful comments. Diego
Figueira is partially supported by ANR QUID, grant ANR-18-CE400031. Artur Jeż work is supported under National Science Centre,
Poland project number 2017/26/E/ST6/00191. Anthony Lin was
supported by the ERC Starting Grant 759969 (AV-SMP) and a MaxPlanck Society Fellowship.

REFERENCES[1] Étienne André. 2019. What’s decidable about parametric timed automata? Int. J.
Softw. Tools Technol. Transf. 21, 2 (2019), 203–219. https://doi.org/10.1007/s10009017-0467-0[2] Renzo Angles and Claudio Gutiérrez. 2008. Survey of graph database models. ACM
Comput. Surv. 40, 1 (2008), 1:1–1:39. https://doi.org/10.1145/1322432.1322433[3] Pablo Barceló Baeza. 2013. Querying graph databases. In Proceedings of the 32nd
ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,
PODS 2013, New York, NY, USA - June 22 - 27, 2013, Richard Hull and Wenfei Fan(Eds.). ACM, 175–188. https://doi.org/10.1145/2463664.2465216[4] Jorge Baier, Dietrich Daroch, Juan L. Reutter, and Domagoj Vrgoc. 2017. Evaluating Navigational RDF Queries over the Web. In Proceedings of the 28th ACM
Conference on Hypertext and Social Media, HT 2017, Prague, Czech Republic, July
4-7, 2017, Peter Dolog, Peter Vojtás, Francesco Bonchi, and Denis Helic (Eds.).
ACM, 165–174. https://doi.org/10.1145/3078714.3078731[5] Abebe Alemu Balcha. 2020. Curve Fitting and Least Square Analysis to Extrapolate for the Case of COVID-19 Status in Ethiopia. Advances in Infectious Diseases
10 (2020). Issue 3.
[6] Pablo Barceló, Gaëlle Fontaine, and Anthony Widjaja Lin. 2015. Expressive Path
Queries on Graph with Data. Log. Methods Comput. Sci. 11, 4 (2015). https://doi.org/10.2168/LMCS-11(4:1)2015[7] Pablo Barceló, Leonid Libkin, Anthony Widjaja Lin, and Peter T. Wood. 2012.
Expressive Languages for Path Queries over Graph-Structured Data. ACM Trans.
Database Syst. 37, 4 (2012), 31:1–31:46. https://doi.org/10.1145/2389241.2389250[8] Saugata Basu. 2014. Algorithms in Real Algebraic Geometry: A Survey. CoRR
abs/1409.1534 (2014). arXiv:1409.1534 http://arxiv.org/abs/1409.1534[9] Michael Benedikt and Leonid Libkin. 1996. On the Structure of Queries inConstraint Query Languages. In Proceedings, 11th Annual IEEE Symposium on
Logic in Computer Science, New Brunswick, New Jersey, USA, July 27-30, 1996. IEEE
Computer Society, 25–34. https://doi.org/10.1109/LICS.1996.561300[10] Michael Benedikt and Leonid Libkin. 2000. Relational queries over interpreted
structures. J. ACM 47, 4 (2000), 644–680. https://doi.org/10.1145/347476.347477[11] Michael Benedikt, Leonid Libkin, Thomas Schwentick, and Luc Segoufin. 2003.
Definable relations and first-order query languages over strings. J. ACM 50, 5(2003), 694–751. https://doi.org/10.1145/876638.876642[12] Achim Blumensath and Erich Grädel. 2000. Automatic Structures. In 15th AnnualIEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA,
June 26-29, 2000. IEEE Computer Society, 51–62. https://doi.org/10.1109/LICS.
2000.855755[13] Achim Blumensath and Erich Grädel. 2004. Finite presentations of infinite
structures: Automata and interpretations. Theory of Computing Systems 37, 6(2004), 641–674.
[14] Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick, and Luc
Segoufin. 2011. Two-variable logic on data words. TOCL 12, 4 (2011), 27:1–27:26.
https://doi.org/10.1145/1970398.1970403[15] Christina Boucher and Bin Ma. 2011. Closest string with outliers. BMC Bioinform.
12, S-1 (2011), S55. https://doi.org/10.1186/1471-2105-12-S1-S55[16] Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi.
2000. Containment of Conjunctive Regular Path Queries with Inverse. In KR
2000, Principles of Knowledge Representation and Reasoning Proceedings of theSeventh International Conference, Breckenridge, Colorado, USA, April 11-15, 2000,
Anthony G. Cohn, Fausto Giunchiglia, and Bart Selman (Eds.). Morgan Kaufmann,
176–185.
[17] Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin,Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak,
Stefan Plantikow, Petra Selmer, Hannes Voigt, Oskar van Rest, Domagoj VrgoÄŊ,Mingxi Wu, and Fred Zemke. 2021. Graph Pattern Matching in GQL and SQL/PGQ.
arXiv:2112.06217 [cs.DB][18] Alin Deutsch and Val Tannen. 2001. Optimization Properties for Classes ofConjunctive Regular Path Queries. In Database Programming Languages, 8thInternational Workshop, DBPL 2001, Frascati, Italy, September 8-10, 2001, Revised
Papers (Lecture Notes in Computer Science, Vol. 2397), Giorgio Ghelli and Gösta
Grahne (Eds.). Springer, 21–39. https://doi.org/10.1007/3-540-46093-4_2[19] Volker Diekert. 2002. Makanin’s Algorithm. In Algebraic Combinatorics on Words,
M. Lothaire (Ed.). Encyclopedia of Mathematics and its Applications, Vol. 90.
Cambridge University Press, Chapter 12, 387–442.
[20] Volker Diekert, Artur Jeż, and Wojciech Plandowski. 2016. Finding all solutionsof equations in free groups and monoids with involution. Inf. Comput. 251 (2016),
263–286. https://doi.org/10.1016/j.ic.2016.09.009 Conference version in Proc. CSR
2014, LNCS 8476 (2014).
[21] S Eilenberg, C.C Elgot, and J.C Shepherdson. 1969. Sets recognized by n-tapeautomata. Journal of Algebra 13, 4 (1969), 447–464. https://doi.org/10.1016/00218693(69)90107-0[22] Herbert B. Enderton. 2001. Introduction to Mathematical Logic (2 ed.). Academic
Press.
[23] Daniela Florescu, Alon Y. Levy, and Dan Suciu. 1998. Query Containment for
Conjunctive Queries with Regular Expressions. In Proceedings of the Seventeenth

ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,
June 1-3, 1998, Seattle, Washington, USA, Alberto O. Mendelzon and Jan Paredaens(Eds.). ACM Press, 139–148. https://doi.org/10.1145/275487.275503[24] Jörg Flum and Martin Ziegler. 1999. Pseudo-Finite Homogeneity and Saturation.
J. Symb. Log. 64, 4 (1999), 1689–1699. https://doi.org/10.2307/2586806[25] E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema,
and S. Weinstein. 2007. Finite Model Theory and Its Applications. Springer.
[26] Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. 2003. Fixed-Parameter
Algorithms for CLOSEST STRING and Related Problems. Algorithmica 37, 1(2003), 25–42. https://doi.org/10.1007/s00453-003-1028-3[27] Christoph Haase, Stephan Kreutzer, Joël Ouaknine, and James Worrell. 2009.
Reachability in Succinct and Parametric One-Counter Automata. In CONCUR
2009 - Concurrency Theory, 20th International Conference, CONCUR 2009, Bologna,
Italy, September 1-4, 2009. Proceedings (Lecture Notes in Computer Science, Vol. 5710),
Mario Bravetti and Gianluigi Zavattaro (Eds.). Springer, 369–383. https://doi.
org/10.1007/978-3-642-04081-8_25[28] Jelle Hellings, Bart Kuijpers, Jan Van den Bussche, and Xiaowang Zhang. 2013.
Walk logic as a framework for path query languages on graph databases. In Joint
2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22,
2013, Wang-Chiew Tan, Giovanna Guerrini, Barbara Catania, and Anastasios
Gounaris (Eds.). ACM, 117–128. https://doi.org/10.1145/2448496.2448512[29] Wilfrid Hodges. 1997. A Shorter Model Theory. Cambridge University Press.
[30] Artur Jeż. 2016. Recompression: a simple and powerful technique for word
equations. J. ACM 63, 1 (Mar 2016), 4:1–4:51. https://doi.org/10.1145/2743014[31] Michael Kaminski and Nissim Francez. 1994. Finite-Memory Automata. Theor.
Comput. Sci. 134, 2 (1994), 329–363. https://doi.org/10.1016/0304-3975(94)90242-9[32] Eryk Kopczynski and Anthony Widjaja To. 2010. Parikh Images of Grammars:
Complexity and Applications. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United
Kingdom. 80–89. https://doi.org/10.1109/LICS.2010.21[33] Dexter C. Kozen. 2006. Theory of Computation. Springer.
[34] G. M. Kuper, L. Libkin, and J. Paredaens (Eds.). 2000. Constraint Databases.
Springer.
[35] Leonid Libkin. 2004. Elements of Finite Model Theory. Springer.
[36] Leonid Libkin, Wim Martens, and Domagoj Vrgoc. 2016. Querying Graphs with
Data. J. ACM 63, 2 (2016), 14:1–14:53. https://doi.org/10.1145/2850413[37] Leonid Libkin and Domagoj Vrgoc. 2012. Regular path queries on graphs withdata. In 15th International Conference on Database Theory, ICDT ’12, Berlin, Germany, March 26-29, 2012, Alin Deutsch (Ed.). ACM, 74–85. https://doi.org/10.
1145/2274576.2274585[38] Alberto O. Mendelzon and Peter T. Wood. 1995. Finding Regular Simple Paths in
Graph Databases. SIAM J. Comput. 24, 6 (1995), 1235–1258. https://doi.org/10.
1137/S009753979122370X[39] Wojciech Plandowski. 2004. Satisfiability of word equations with constants is in
PSPACE. J. ACM 51, 3 (2004), 483–496. https://doi.org/10.1145/990308.990312[40] Wojciech Plandowski and Wojciech Rytter. 1998. Application of Lempel-Ziv
Encodings to the Solution of Word Equations. In ICALP (LNCS, Vol. 1443),
Kim Guldstrand Larsen, Sven Skyum, and Glynn Winskel (Eds.). Springer, 731–
742. https://doi.org/10.1007/BFb0055097[41] Luc Segoufin and Szymon Torunczyk. 2011. Automata based verification overlinearly ordered data domains. In 28th International Symposium on Theoretical
Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany(LIPIcs, Vol. 9), Thomas Schwentick and Christoph Dürr (Eds.). Schloss Dagstuhl Leibniz-Zentrum für Informatik, 81–92. https://doi.org/10.4230/LIPIcs.STACS.
2011.81[42] Anthony Widjaja To. 2009. Model Checking FO(R) over One-Counter Processes
and beyond. In Computer Science Logic, 23rd international Workshop, CSL 2009,18th Annual Conference of the EACSL, Coimbra, Portugal, September 7-11, 2009.
Proceedings. 485–499. https://doi.org/10.1007/978-3-642-04027-6_35[43] Heribert Vollmer. 1999. Introduction to Circuit Complexity. Springer.
[44] Domagoj Vrgoc, Carlos Rojas, Renzo Angles, Marcelo Arenas, Diego Arroyuelo,
Carlos Buil Aranda, Aidan Hogan, Gonzalo Navarro, Cristian Riveros, and Juan
Romero. 2021. MillenniumDB: A Persistent, Open-Source, Graph Database. CoRR
abs/2111.01540 (2021). arXiv:2111.01540 https://arxiv.org/abs/2111.01540[45] Peter T. Wood. 2012. Query languages for graph databases. SIGMOD Rec. 41, 1(2012), 50–60. https://doi.org/10.1145/2206869.2206879

A APPENDIX TO SECTION 3
A.1 Proof of Lemma 3.5
Fix a (T, σ )-register automaton with parameters
A = (R, P, Q, Q 0 , F 0 , ∆),and a logarithmic function f . Say |R | = k. Given two vertices s, tof a given graph G with set V of nodes and universe D of datavalues, we want to know if there is some parameter assignmentµ : P → {d ∈ D : |d | ≤ f (|G|)} for which the query returns (s, t ).
The NL machine T first guesses µ (using logarithmic space) andthen simply traverses G, while simultaneously simulating A (asin standard product automata construction). More precisely, it will
initially guess a state q 0 ∈ Q 0 in the simulation, and set the registervalues in R to an arbitrary active-domain values r0 ∈ D k , and start
the procedure from configuration (s, q 0 , r). From any configuration(v, q, r), the machine T guesses a node v ′ and a label a ∈ Σ suchthat (v, v ′ ) ∈ Ea , the next register (active-domain) values r ′ , and atransition(q, (a, φ(curr , P, R, R ′ )), q ′ )such that G |= φ(v, µ, r, r ′ ). The simulation proceeds to the next
configuration (v ′, q ′, r ′ ). It will stop and accept as soon as a configuration of the form (t, q F , r), for some q F ∈ F and register values r,
is visited.
Recall that an NL machine has an input tape, and a log-spaceworking memory tape. To ensure an NL simulation, we use thestandard trick of using pointers that refer to the parts of the input
tape that contain the node/datum of interest in G. Each such a
pointer reference uses space that is logarithmic in the size of the
input (i.e. G).

B APPENDIX TO SECTION 4
B.1 Proof of Lemma 4.3
We actually show that, in terms of expressive power, we have:(1) EFO+ (TAut , σ ) ⊆ EFO+
act (TAut , σ ) and(2) EFO(TAut , σ ) ⊆ FOact (TAut , σ ).
To prove (1), first note that an existential-positive input formulaφ(x̄ ) is equivalent to a disjunction of formulas of the form φ ′ (x̄ ) =V∃ȳ ψ (z̄) ∧ i ∈I Hi (z̄i ), where variables from z̄ and z̄i range overx̄ȳ, each Hi is a relation from the schema σ , and ψ is a formula of
EFO+ (TAut ). We can further push any existential quantification ofSvariable from ȳ which is not in i ∈I z̄i inside ψ . In other words,
we can assume that every variable of ȳ is either free (i.e., in x̄)or in some z̄i . Now we can consider the automatic relation Rψ ={ū : Γ ∗ |= ψ [ū]} and redefine φ ′ as the equivalent formula ∃ȳ ∈Vadom Rψ (z̄) ∧ i ∈I Hi (z̄i ).
The proof for (2) is similar to the existential positive case witha twist. By a similar reasoning as before, it suffices
 V to assume that
we deal with the formula φ(x̄ ) of the form ∃ȳi ∈I (¬)R i (z̄i ) ∧A(z̄) , where y = y1 , . . . , yn , Ri ∈ σ and A is an automatic relation.
Furthermore, we may assume that ȳ ∩ z̄i , ∅ and ȳ ∩ z̄ , ∅;otherwise, we pull the corresponding atom out of the scope of ȳ.
Let <l ex be the ‘shortlex’ lexicographic order on Σ-words (here,
we implicitly assume a total ordering on Σ). That is, v <l ex w iff(i) |v | < |w |, or (ii) |v | = |w | = n, v = a 1 · · · an , w = b1 · · · bn , andthere is i ∈ [1, n] such that ai < bi and a 1 · · · ai−1 = b1 · · · bi−1 .
Observe that <l ex is a total linear order and is also automatic. We
assume below that the variables x, x 1 , x 2 , . . . do not appear in z̄.

Define θ (x 1 , x 2 ) and maxadom (x ) as follows:θ (x 1 , x 2 ) := x 1 <l ex x 2 ∧ ¬∃x ∈ adom(x 1 <l ex x <l ex x 2 ),max (x ) := ∀x 1 ∈ adom(x 1 <l ex x ),adom

min (x ) := ∀x 1 ∈ adom(x <l ex x 1 ).

adom

Then, φ is equivalent to a big disjunction ofψC̄ , where C̄ = (C 1 , . . . , Cn )and Ci ∈ {minadom (r i ), θ (r i , r i′ ), maxadom (r i )}. The idea is that bya satisfying valuation of Ci we guess where the valuation of yi appears w.r.t. the <l ex order: either before the first adom word (caseCi = minadom (r i )), or between two consecutive adom words (caseCi = θ (r i , r i′ )), or after the last adom word, should there be one(case Ci = maxadom (r i )). Let Y+ ⊆ ȳ be the set of all variables z
appearing in a positive literal Ri (z̄i ) with z ∈ z̄i . Here ψC̄ is definedasn^_∃r 1 , r 1′ , . . . , r n , r n′ ∈ adom *. Ci ∧χY +/Y ⊆(ȳ\Y+ ),i=1-

where Y is intuitively the variables whose valuations are guessed
to be not in adom (which of course cannot intersect Y+ ). The formula χY is defined as follows. Let ηY be the variable substitution
replacing each yi < Y by r i , and for any formula ξ , let us write
ξ [ηY ] to denote the result of substituting the variables according
to ηY in ξ . Thus, χY is a conjunction consisting of each R(z̄i )[ηY ]appearing positive, each negative ¬R(z̄i )[ηY ], where z̄i ∩ Y = ∅,and the formulaχY′ := ∃Y (A(z̄)[ηY ] ∧ µ (Y ))where µ (Y ) =yi ∈Y νi (yi ) withV

yi <l ex r i



′
r
<
νi (yi ) := i l ex yi <l ex r ir i <l ex yiif, Ci = minadom (r i )if, Ci = θ (r i , r i′ ) and,if, Ci = maxadom (r i )Observe that χY′ is automatic, and hence can be written as an
atom A′ (z̄) for some A′ ∈ Rel. The reason why ¬R(z̄i )[ηY ], withz̄i ∩ Y , ∅, can be removed is that the above formula alreadyensures that at least one of the arguments in z̄i [ηY ] will not bein the active domain, which implies ¬R(z̄i )[ηY ]. Observe that χY′
is in FO(TAut ) and so is an automatic relation. Thus, we obtain aformula in FOact (TAut , σ ).
□Corollary B.1 (implying Corollary 4.7). Every EFO(TAut , σ )formula ψ (z̄) is effectively equivalent to an EFOact (TAut , σ ′ ) formulaψ ′ , where σ ′ is the extension of σ with{θ (·, ·), max (·), min (·)},
adom

adom

interpreted as in the proof of Lemma 4.3. Further, ψ ′ (z̄) is a disjunctionof formulas of the form A′ (z̄) ∧ ∃¯r ∈ adom τ (z̄r¯), where A′ is a TAut atom, τ is a conjunction of σ ′ -atoms and negated σ -atoms.
Let N = maxw ∈adom |w | and let v : z̄ → Γ ∗ be a satisfying
assignment for ψ ′ (z̄), and z ∈ z̄ such that |v (z)| > N . Suppose
there is a word u ∈ Γ ∗ such that |u| > N and Γ ∗ , v ′ |= A′ (z̄) forv ′ = v[z 7→ u]. Then, v ′ is also a satisfying assignment for ψ ′ .

B.2

Proof of Lemma 4.6

We reduce from 3-SAT. Consider a (σ , TAut )-register automatonwith no registers and having just three states q 0 , q, q F , where q 0 is
initial and q F is final, one parameter p, and three transitions:• (q 0 , (#, ⊤), q),• (q, (a, ⊤), q F ), and• (q, (a,ψ (curr, p)), q),withψ (curr, p) = ∃p ′, x ′, x value(curr, x ) ∧ x ′ ≺ x ∧ p ′ ≺ p ∧eq-len(p ′, x ′ ) ∧ lst1 (x ′ ) ∧((lst1 (p ′ ) ∧ lst1 (x )) ∨ (lst0 (p ′ ) ∧ lst0 (x ))).
Note that ψ says that there is a position i so that the current value
x is such that: (1) the i-th letter of the parameter and the last letterof x coincide, and (2) x has a 1 at position i. The idea will be thatp encodes a satisfying assignment (where the i-th variable is true
iff the i-th position of p is 1), and x is of the form 0i−1 10 · · · 0b if
it encodes a literal of the i-th variable appearing either positive if
b = 1 or negative if b = 0.
Given a 3-SAT formula
φ :=

m
^

(ℓi,1 ∨ ℓi,2 ∨ ℓi,3 )

i=1

Consider the TAut -embedded graph over a singleton relation
signature {a}, an attribute-assigning relation value(·, ·), a vertex set
˙ 0 , v F } and edges
V = {vi, j : i ∈ [1, m], j ∈ {1, 2, 3}} ∪{v
Ea = {(v 0 , v 1, j ), (vm, j , v F ) : j ∈ {1, 2, 3}} ∪{(vi, j , vi+1, j ′ ) : i ∈ [1, n − 1], j, j ′ ∈ {1, 2, 3}}.
The interpretation of value contains (v 0 , ε), (v F , ε); and for any
other vi, j such that ℓi, j = x k (resp. ℓi, j = ¬x k ) it contains (vi, j , u),where u is the word over {0, 1} of length m + 1 such that:

A standard proof follows by giving explicit values for the variables.
Concerning the L+
WE , as in the main part of the paper, to streamline the presentation, we present the proofs for the fragment withno regular relations on the words. The proofs generalize to the casewith regular relations using a standard approach of alphabet closure [20]: we consider a finite monoid recognizing all used regular
languages (so, roughly speaking, the Boolean transition matrices of
product of automata recognizing those languages). Then for eachelement τ in this monoid that corresponds to some word over the input alphabet, we introduce a fresh letter aτ . Solving word equations(with regular relations) over such extended alphabet is equivalent
to solving them over the input alphabet. However, the solutions
over the extended alphabet have “nicer properties” and in essence
behave like solutions when no regular relations are allowed.
Size of length-minimal solutions. A solution s̄ of a system E ofword equations is length-minimal, when for each other solution s̄ ′it holds thatXX
|e (s̄)| ≤|e (s̄ ′ )| .
e ∈E

e ∈E

It is known that the length of the length-minimal solution is doubly
exponential [30, 39]. In our setting we need more refined bounds.
P
Lemma C.2. Consider a system of equations E. Let n = e ∈E |e |,nv = maxe ∈E |e |x̄ and k be the number of variables.
Let s̄ be a length-minimal solution (over some alphabet). ThenX
|e (s̄)| ≤ p(n) · д(k, nv ) ,e ∈Ewhere p is a polynomial (with degree depending on nv , k) and д istriply exponential function not depending on n.

x = vi (ȳ) for i = 1, . . . , h ,The proof utilises the same approach as the standard one [30]but focuses on the bound in terms of number of occurrences ofthe variables in the equations. When compared to the standard
proof, we try to eliminate strongly similar equations: recall that
equations u (x̄ ) = v (x̄ ) and u ′ (x̄ ) = v ′ (x̄ ) are similar, when thesequence of variables (obtained by removing all letters) in u (x̄ ) andu ′ (x̄ ) is the same and the sequence of variables in v (x̄ ) and v ′ (x̄ ) is
the same. They are strongly similar, when additionally the lengthsof words between the corresponding variables in u, u ′ and v, v ′are the same. Then it can be shown that if two strongly similar
equations have a common solution, then either they are the same
equation or can be reduced to a system of equivalent equations
whose size is at most the size of one such equation. By employing
this observation in the known proof [30], we limit the size of thesystem and obtain improved bounds; note that the bound is general,
i.e. applies to any system, but the bound is triply exponential in
number of occurrences of variables, this is a cost of lowering thedependence on sum of equations’ lengths.

where x is a fixed variable other than variables in ȳ and each variablefrom ȳ appears at most once in v 1 , . . . , vh and each vi contains atleast one variable (from ȳ).
Let w i , si be the longest prefix and suffix of each vi consisting ofletters, i.e. no variables are allowed. Then the system has a solution if
and only if there are w, s such that w i ⪯ w and s ⪰ si for each i.

Length functions and their properties. We employ the notionof length functions and corresponding solutions introduced by
Plandowski and Rytter [40]. A length function f assigns to eachvariable a length; a solution s̄ is an f -solution, when f (x i ) = |si |for each variable x i . Similarly, given a solution s̄ we call such f
its length function. Given a length function, we can compute the• its k-th position has a 1,
• its last position has a 1 (resp. 0), and• every other position has a 0.
If φ is satisfiable by setting variables x i 1 , . . . , x i r to true and theremaining ones to false, then there is a path from v 0 to v F in thelanguage with the parameter assignment {0, 1}m+1 which has a
1-symbol on the i j -th position, for every 1 ≤ j ≤ r , and a 0-symbol
otherwise. Conversely, for any path from v 0 to v F in the language,
the m-prefix of the parameter assignment witnessing membershipyields a satisfying assignment for φ.
□

C

APPENDIX TO SECTION 5
Lemma C.1. Consider a system of word equations of the form

lengths of each side of equation under (any) f -solution and therefore infer equalities of individual letters in the substitutions. For asystem of equations E and length function f we define a relation
R f , E on positions of letters from the equation and positions of substitutions for a variable: Two positions are in a relation R f , E when
they represent the same position inside a variable (for different
occurrences of said variable) or are the corresponding positions on
the two sides of the equation, see [40] for a formal definition; notethat this formalizes the intuitive way one would try to solve anequation, when the lengths of the variables are known. Let R f∗, E be
the transitive closure of the relation; clearly this is an equivalence
relation. R f∗, E can be used to test, whether there is an f -solution
and if so to determine the letters of the substitution for variables.
Lemma C.3 ([40, Lemma 4]). Given a system of word equations
E and a length function f there is an f -solution of E if and only ifthere are no different letters in an equivalence class of R f∗, E .
When s̄ is length-minimal and f is its length function, there isa position of a letter from the equation in each equivalence class of
R f∗, E and all letters at positions from one equivalence class are equal.
Lemma C.3 gives an oracle with NL access to the letters of alength-minimal solution: after guessing f (for a length-minimal solution), we can verify, whether there is an f -solution: Treating positions as nodes and R f , E as an edge relation, this is a co-reachability,
which is in NL. Then using the second point we can use it for accessto letters of a variable: we look for a position of a letter from theequation that is in R f∗, E with our position of the variable. This is areachability problem in the same setting as before, which is in NL.
However, such a representation does not fit in NL, as it requires
all equations and there are polynomially many of them (and they
are not written down, just obtained when traversing the G-path π ).
Choosing small subsystem. Our final step is to show that we canchoose a small subsystem E ′ (in fact, |E ′ | depends only on |A|) suchthat R f∗, E ′ also has a position of a letter in each equivalence class.
Note, that we will be using the relation induced by the subsystem,
i.e. E ′ is enough to deduce each letter of the solution, yet we will
be using lengths guessed for the larger system. In particular, there
is no guarantee that f -solution for E ′ is in fact a length-minimal
solution. Formally, we show thatS
Lemma C.4. Suppose that E = i Ei is a system of word equations
such that for each i the subsystem Ei consists of similar equations.
Let f be the length function of a length-minimal solution for E. Let mbe the maximal number of occurrences of variables in equations in E.
Then there are subsystems Ei′ ⊆ Ei , where |Ei′ | = O(m) such thatS
the relation R f∗, E ′ on positions of equations in E ′ = i Ei′ , has a letterfrom equation in each equivalence class.
The main observation needed to show Lemma C.4 is that given
two similar equations either they have the same set of f -solutions
or we can infer a partial solution, in the sense that we can computefor some variables {x i }i ∈I prefixes {si }i ∈I such that each f -solution
assigns to x i a word with a prefix si , for each i, and afterwards those
two equations have exactly the same f -solutions. Moreover, sucha substitution “simplifies” the equation: only O(m) such partial
substitutions can be made in total; intuitively, either they remove

an occurrence of a variable or remove “overlap” between variables
at different sides of the equation. The actual statement is rather
technical and is given in the full version of the paper; in particular,
we need to analyze how the substitutions affect the R relation of
the subsystem. By considering the equations one by one we canconstruct the desired Ei′ : this is the set of equations whose addition
caused a partial substitution, so |Ei′ | = O(m). It can be shown thatR f∗, E ′ is the same as R f∗, E and so also R f∗, E ′ is the same as R f∗, E ,iiwhich yields the claim of the Lemma.
In our case, all equations that are instances of a fixed equationfrom a guard (i.e. are obtained by substitution of curr, R, R ′ and active domain quantified variables) are similar and in total there are at
most |A| such classes. Hence we can choose O(m|A|) ≤ O(|A| 2 )many equations from the whole system and the relation R they
define (together with f ) determines each letter of the substitution
for variables. Note that those equations can be guessed beforehand,i.e. before traversing the path we guess some equations from A andthe curr, R, R ′ and active domain quantified variables in them andalso guess the length function f . Then we check, whether the fand the guessed equation are consistent and determine each letterof a substitution. If so, we have an NL oracle. If not, we reject.

D APPENDIX FOR SECTION 6
Reduction from CRDPQ(L, T, σ ) to RDPQ(L, T, σ )Assume a CRDPQ(L, T, σ )-query:n^
Q (z̄) ←x i → Ai yi ∧ φ(P, x̄, ȳ).
i=1

Let x̄ ∪ ȳ has a total of N variables. Assume w.l.o.g. that each Ai
has precisely l active-domain registers R := {r 1 , . . . , rl }. Let G
be the graph consisting of view definitions (V , {Ea }a ∈Σ ) and theunderlying T-structure S. Finally, let µ be the given instantiationof z̄. We construct a new A with l + N active-domain registers
R 1 := R ∪ x̄ ∪ ȳ. Let Q i be the set of states of Ai . The set Q of statesof A is defined to be the union of {q 0 } and a disjoint union of all Q i ,say, consisting of states of the form (q, i) for each q ∈ Q i . For eachz ∈ z̄, we add the new unary relation S z = {µ (z)} to S. Let Σ ′ :=SΣ [1, n] (assume [1, n] ∩ Σ = ∅). Define Ei (z, z ′ ) := θ i (z) ∧ θ i (z ′ ).
Here, θ i (z) := V (z) if i = 1 or i > 1 and yi−1 < z̄; otherwise,θ i (z) := ∃y ∈ adom(z = y ∧ Syi −1 (y)). Similarly, θ i′ (z) := V (z) if
x i < z̄; otherwise, θ i′ (z) := ∃x ∈ adom(z = x ∧ S x i (x )). The output
RDPQ(L, T, σ ) query evaluation problem is Q ′ := x → A y with
two arbitrary start and final nodes s, t. The automaton A starts
with q 0 , from which there is a transition (q 0 , (1, φ(P, x̄, ȳ), q 01 ), foreach start state q 01 of A1 . A will then simulate A1 , . . . , An in thisorder, while transitioning from Ai to Ai+1 using Ei+1 . To keep the
instantiations of x̄ and ȳ consistent, we do a check curr = x i in any
outgoing transition from (qi0 , i), for each start state qi0 of Ai , andcurr = yi in any incoming transition to (q F , i), for each final stateq F of Ai . [WLOG, we assume that each start state has no incomingtransitions, and each final state has no outgoing transitions.]
It is easy to see that the above reduction can be performed inlogspace, and the output query Q ′ depends only on Q.