Monadic Datalog and the expressive power of languages for web information extraction

DOI10.1145/962446.962450MaRDI QIDQ5501186zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Georg Gottlob, Christoph Koch

Publication date 1 August 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0211020

Mathematics Subject Classification ID

Logic in computer science (03B70) Internet topics (68M11) Logic programming (68N17) Database theory (68P15) Information storage and retrieval of data (68P20)

Abstract: Research on information extraction from Web pages (wrapping) has seen much activity recently (particularly systems implementations), but little work has been done on formally studying the expressiveness of the formalisms proposed or on the theoretical foundations of wrapping. In this paper, we first study monadic datalog over trees as a wrapping language. We show that this simple language is equivalent to monadic second order logic (MSO) in its ability to specify wrappers. We believe that MSO has the right expressiveness required for Web information extraction and propose MSO as a yardstick for evaluating and comparing wrappers. Along the way, several other results on the complexity of query evaluation and query containment for monadic datalog over trees are established, and a simple normal form for this language is presented. Using the above results, we subsequently study the kernel fragment Elog${}^{-}$ of the Elog wrapping language used in the Lixto system (a visual wrapper generator). Curiously, Elog${}^{-}$ exactly captures MSO, yet is easier to use. Indeed, programs in this language can be entirely visually specified.

Recommendations

• Logic, languages, and rules for web data extraction and reasoning over data
• SOFSEM 2006: Theory and Practice of Computer Science
• Weighted monadic Datalog
• Monadic Datalog over finite structures of bounded treewidth
• Monadic datalog and regular tree pattern queries

Cited in

(29)

• Compact representation for answer sets of n-ary regular queries
• A logic for document spanners
• Tight lower bounds for query processing on streaming and external memory data
• Deciding twig-definability of node selecting tree automata
• Controlled term rewriting
• A logic for document spanners
• Containment of monadic Datalog programs via bounded clique-width
• Logics and Automata for Totally Ordered Trees
• Inf-datalog, Modal Logic and Complexities
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• Complete Axiomatizations of MSO, FO(TC 1 ) and FO(LFP 1 ) on Finite Trees
• Monadic Datalog Tree Transducers
• Compact Representation for Answer Sets of n-ary Regular Queries
• On the equivalence of distributed systems with queries and communication
• Comparing the succinctness of monadic query languages over finite trees
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Automata for unordered trees
• Combining decidability paradigms for existential rules
• Efficient and Expressive Tree Filters
• Generating Specialized Rules and Programs for Demand-Driven Analysis
• Structural properties of XPath fragments
• Logic, languages, and rules for web data extraction and reasoning over data
• SOFSEM 2006: Theory and Practice of Computer Science
• Regular languages of nested words: fixed points, automata, and synchronization
• Right-adjoints for Datalog programs
• On the expressive power of monadic least fixed point logic
• Automata for XML -- a survey
• Weighted monadic Datalog
• Reasoning about XML with temporal logics and automata

Describes a project that uses

Uses Software

• Lixto
• Datalog

This page was built for publication: Monadic Datalog and the expressive power of languages for web information extraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501186)