Satisfiability and Relevance for Queries over Active Documents

Summary: Formalizes "active documents" exchanging input (update) and output (query) streams and introduces satisfiability (a fact can appear in some future query result) and relevance (a call's returned data can affect a query answer). Provides complexity classifications for computing satisfiability in a core insertion-only model and extensions (including deletions), and for computing relevance in the core model. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hdbf0e3a65978d434
Venue: PODS
Year: 2009
Pagerank: 5.2880532e-05
Overall Rank: 8,722 | 41.38%
DOI: 10.1145/1559795.1559810

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA; University of Paris)
2. Pierre Bourhis (INRIA; University of Paris)
3. Bogdan Marinoiu (INRIA; University of Paris)

BibTeX Citation

@inproceedings{abiteboul_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Satisfiability and Relevance for Queries over Active Documents}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559810},
        doi = {10.1145/1559795.1559810},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abiteboul, Serge and Bourhis, Pierre and Marinoiu, Bogdan},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,661	Determining Relevance of Accesses at Runtime	2011	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00046583225
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018859247
875	Queries Independent of Updates	1993	VLDB	0.0001331025
1,393	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00010801562
1,978	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.275331e-05
2,158	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9413031e-05
2,943	Numerical Document Queries	2003	PODS	7.8282079e-05
4,762	The Relational Model Of Data And Cylindrical Algebras	1982	PODS	6.4281372e-05
5,494	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.1065309e-05
7,508	Static Analysis of Active XML Systems	2008	PODS	5.505048e-05
9,335	Positive Active XML	2004	PODS	5.1913554e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,223	Foundations of Semantic Web Databases	2004	PODS
2	6,986	Distributed Computation of Web Queries using Automata	2002	PODS
3	1,917	Formal Models of Web Queries	1997	PODS
4	12,873	Optimization of Multi-Domain Queries on the Web	2008	VLDB
5	897	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS
6	4,449	Keyword Search on Relational Data Streams	2007	SIGMOD
7	12,926	K-Relevance: A Spectrum of Relevance for Data Sources Impacting a Query	2007	SIGMOD
8	12,847	Complexity and Composition of Synthesized Web Services	2008	PODS
9	12,907	Querying Web-Based Applications Under Models of Uncertainty	2008	VLDB
10	12,661	Determining Relevance of Accesses at Runtime	2011	PODS