𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounded Arity Datalog(≠) Queries on Graphs

✍ Scribed by Foto N. Afrati

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
627 KB
Volume
55
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We show that there are Datalog({) queries on graphs (i.e., the extensional database contains a single binary relation) that require recursively defined predicates of arbitrarily large width. More specifically, we prove that fixed subgraph homeomorphism queries require width of recursively defined predicates which is at least equal to the number of arcs in the pattern graph.

📜 SIMILAR VOLUMES

On the Expected Size of Recursive Datalo
On the Expected Size of Recursive Datalog Queries
✍ S. Seshadri; J.F. Naughton 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 998 KB

We present asymptotically exact expressions for the expected sizes of relations defined by three well-studied Datalog recursions, namely the "transitive closure," "same generation," and "canonical factorable recursion." We consider the size of the fixpoints of the recursively defined relations in th

On bounded query machines
On bounded query machines
✍ Jose L. Balcázar; Ronald V. Book; Uwe Schöning 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 452 KB
On bounded treewidth duality of graphs
On bounded treewidth duality of graphs
✍ Ne?et?il, Jaroslav; Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 734 KB

For a graph H , the H-coloring problem is to decide whether or not an instance graph G is homomorphic to H . The H-coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H , there is a graph F of treewidth k which is