Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting

Summary: Introduce constrained tree-rules for inferring over heterogeneous JSON and identify a tractable fragment with an automata-based query-rewriting algorithm. Present instance-aware rewrites that leverage NoSQL document stores to scale reasoning to millions of JSON documents. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc9b6da8098a0d444
Venue: VLDB
Year: 2023
Pagerank: 4.9605343e-05
Overall Rank: 11,810 | 20.84%
DOI: 10.14778/3611479.3611481
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Olivier Rodriguez (CNRS; INRIA; Laboratory of Computer Science, Robotics and Microelectronics of Montpellier; University of Montpellier)
2. Federico Ulliana (CNRS; INRIA; Laboratory of Computer Science, Robotics and Microelectronics of Montpellier; University of Montpellier)
3. Marie-Laure Mugnier (CNRS; INRIA; Laboratory of Computer Science, Robotics and Microelectronics of Montpellier; University of Montpellier)

BibTeX Citation

@article{rodriguez_vldb23,
        title = {{Scalable Reasoning on Document Stores via Instance-Aware Query Rewriting}},
        author = {Rodriguez, Olivier and Ulliana, Federico and Mugnier, Marie-Laure},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {11},
        pages = {2699--2713},
        doi = {10.14778/3611479.3611481},
        url = {https://doi.org/10.14778/3611479.3611481},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
50	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00042977538
86	XMark: A Benchmark for XML Data Management	2002	VLDB	0.0003567995
358	Regular Path Queries with Constraints	1997	PODS	0.00020030407
467	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017740891
940	A Scalable Algorithm for Answering Queries Using Views	2000	VLDB	0.00012941424
1,272	Querying XML Views of Relational Data	2001	VLDB	0.00011226794
2,545	A General Datalog-Based Framework for Tractable Query Answering over Ontologies	2009	PODS	8.2970788e-05
2,668	Benchmarking the Chase	2017	PODS	8.1323973e-05
2,830	Secure XML Querying with Security Views	2004	SIGMOD	7.9468777e-05
3,362	JSON: Data model, Query languages and Schema specification	2017	PODS	7.3614068e-05
4,587	The Vadalog System: Datalog-based Reasoning for Knowledge Graphs	2018	VLDB	6.505507e-05
4,849	That's All Folks! LLUNATIC Goes Open Source	2014	VLDB	6.3687416e-05
6,149	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	5.8557417e-05
6,781	Teaching an RDBMS about ontological constraints	2016	VLDB	5.6685378e-05
8,044	Obi-Wan: Ontology-Based RDF Integration of Heterogeneous Data	2020	VLDB	5.3851452e-05
8,055	ForBackBench: A Benchmark for Chasing vs. Query-Rewriting	2022	VLDB	5.3833071e-05
8,280	Couchbase Analytics: NoETL for Scalable NoSQL Data Analysis	2019	VLDB	5.3462773e-05
9,360	Positive Active XML	2004	PODS	5.1741895e-05
10,078	Materializing Knowledge Bases via Trigger Graphs	2021	VLDB	5.0732737e-05
10,080	J-Logic: Logical Foundations for JSON Querying	2017	PODS	5.0732737e-05
10,083	Supervised Wrapper Generation with Lixto	2001	VLDB	5.0732737e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,105	ReCG: Bottom-Up JSON Schema Discovery Using a Repetitive Cluster-and-Generalize Framework	2024	VLDB
2	6,696	Semistructured Models, Queries and Algebras in the Big Data Era	2016	SIGMOD
3	5,796	Consistent Query Answers in Inconsistent Probabilistic Databases	2010	SIGMOD
4	11,430	Towards Principled, Practical Document Database Design	2025	VLDB
5	10,144	Combined Approximations for Uniform Operational Consistent Query Answering	2024	PODS
6	909	Constraint-Based XML Query Rewriting for Data Integration	2004	SIGMOD
7	6,239	Scalable Query Rewriting: A Graph-Based Approach	2011	SIGMOD
8	11,527	Consistent Query Answering for Primary Keys on Rooted Tree Queries	2024	PODS
9	2,691	Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach	2003	VLDB
10	6,460	Query Automata (extended abstract)	1999	PODS