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: 1479
Venue: PODS
Year: 2009
Pagerank: 5.4119882e-05
Overall Rank: 8,547 | 41.37%
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,364	Determining Relevance of Accesses at Runtime	2011	PODS	5.093636e-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.00047309646
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
853	Queries Independent of Updates	1993	VLDB	0.00013587101
1,361	Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates	1986	VLDB	0.00011037801
1,916	XPath Satisfiability in the Presence of DTDs	2005	PODS	9.4878711e-05
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,875	Numerical Document Queries	2003	PODS	8.0083925e-05
4,662	The Relational Model Of Data And Cylindrical Algebras	1982	PODS	6.5787742e-05
5,360	Lazy Query Evaluation for Active XML	2004	SIGMOD	6.2487273e-05
7,361	Static Analysis of Active XML Systems	2008	PODS	5.6340455e-05
9,153	Positive Active XML	2004	PODS	5.3130241e-05

Semantically Similar Papers

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