ACM Transactions on Database Systems · 2005 · 119 citations · 29 references
ComputingComputer ScienceLogicNatural Language ProcessingProgramming LanguagesAbstract Syntax TreesFirst-order LogicPredicate LogicRelational AlgebraSyntactic AnalysisSyntax-semantics InterfaceAbstractionCompletenessExpansionTransitive ClosureXml Data ModelsXpath
XPath 1.0 is a variable free language designed to specify paths between nodes in XML documents. Such paths can alternatively be specified in first-order logic. The logical abstraction of XPath 1.0, usually called Navigational or Core XPath, is not powerful enough to express every first-order definable path. In this article, we show that there exists a natural expansion of Core XPath in which every first-order definable path in XML document trees is expressible. This expansion is called Conditional XPath. It contains additional axis relations of the form (child::n[F])+, denoting the transitive closure of the path expressed by child::n[F]. The difference with XPath's descendant::n[F] is that the path (child::n[F])+ is conditional on the fact that all nodes in between the start and end node of the path should also be labeled by n and should make the predicate F true. This result can be viewed as the XPath analogue of the expressive completeness of the relational algebra with respect to first-order logic.
29
Optimal implementation of conjunctive queries in relational data bases
Ashok K. Chandra, Philip M. Merlin · 1977 · 1.2K citations · Full text
On the temporal analysis of fairness
Dov M. Gabbay, Amir Pnueli, Saharon Shelah et al. · 1980 · 731 citations
Dexter Kozen · ACM Transactions on Programming Languages and Systems · 1997 · 522 citations · Full text