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.2905577e-05
Overall Rank: 8,714 | 41.42%
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,655	Determining Relevance of Accesses at Runtime	2011	PODS	4.9793485e-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.00046602544
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018868173
875	Queries Independent of Updates	1993	VLDB	0.00013316445
1,393	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00010805324
1,976	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.2797174e-05
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,942	Numerical Document Queries	2003	PODS	7.8318328e-05
4,760	The Relational Model Of Data And Cylindrical Algebras	1982	PODS	6.4311817e-05
5,490	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.1094192e-05
7,503	Static Analysis of Active XML Systems	2008	PODS	5.5076551e-05
9,326	Positive Active XML	2004	PODS	5.1938141e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,222	Foundations of Semantic Web Databases	2004	PODS
2	6,983	Distributed Computation of Web Queries using Automata	2002	PODS
3	1,915	Formal Models of Web Queries	1997	PODS
4	12,867	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,447	Keyword Search on Relational Data Streams	2007	SIGMOD
7	12,920	K-Relevance: A Spectrum of Relevance for Data Sources Impacting a Query	2007	SIGMOD
8	12,841	Complexity and Composition of Synthesized Web Services	2008	PODS
9	12,901	Querying Web-Based Applications Under Models of Uncertainty	2008	VLDB
10	12,655	Determining Relevance of Accesses at Runtime	2011	PODS