{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:34:54Z","timestamp":1753889694768,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,12,22]],"date-time":"2015-12-22T00:00:00Z","timestamp":1450742400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We consider query answering using views on graph databases, i.e. databases\nstructured as edge-labeled graphs. We mainly consider views and queries\nspecified by Regular Path Queries (RPQ). These are queries selecting pairs of\nnodes in a graph database that are connected via a path whose sequence of edge\nlabels belongs to some regular language. We say that a view V determines a\nquery Q if for all graph databases D, the view image V(D) always contains\nenough information to answer Q on D. In other words, there is a well defined\nfunction from V(D) to Q(D). Our main result shows that when this function is\nmonotone, there exists a rewriting of Q as a Datalog query over the view\ninstance V(D). In particular the rewriting query can be evaluated in time\npolynomial in the size of V(D). Moreover this implies that it is decidable\nwhether an RPQ query can be rewritten in Datalog using RPQ views.<\/jats:p>","DOI":"10.2168\/lmcs-11(4:14)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:46:40Z","timestamp":1479736000000},"source":"Crossref","is-referenced-by-count":7,"title":["Datalog Rewritings of Regular Path Queries using Views"],"prefix":"10.46298","volume":"Volume 11, Issue 4","author":[{"given":"Nadime","family":"Francis","sequence":"first","affiliation":[]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[]},{"given":"Cristina","family":"Sirangelo","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2015,12,22]]},"reference":[{"key":"1115:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1615\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1615\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:07:58Z","timestamp":1681243678000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,22]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(4:14)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1511.00938","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1511.00938","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"arxiv","id":"1802.01554","asserted-by":"subject"},{"id-type":"doi","id":"10.1145\/3209108.3209120","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arxiv.1802.01554","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,12,22]]},"article-number":"1615"}}