Logical Methods in Computer Science · 2014 · 15 citations · 18 references
ComputingComputer ScienceKnowledge RepresentationLogicTheory Of ComputationLogic ProgrammingPredicate LogicStructured Query LanguageXml DatabasesAutomated Reasoning With ConstraintsConstraintsExponential Time ComplexityTree StructuresXml Data ModelsXml Query LanguagesXml Query ProcessingXpath
We introduce a logical foundation to reason on tree structures with constraints on the number of node occurrences. Related formalisms are limited to express occurrence constraints on particular tree regions, as for instance the children of a given node. By contrast, the logic introduced in the present work can concisely express numerical bounds on any region, descendants or ancestors for instance. We prove that the logic is decidable in single exponential time even if the numerical constraints are in binary form. We also illustrate the usage of the logic in the description of numerical constraints on multi-directional path queries on XML documents. Furthermore, numerical restrictions on regular languages (XML schemas) can also be concisely described by the logic. This implies a characterization of decidable counting extensions of XPath queries and XML schemas. Moreover, as the logic is closed under negation, it can thus be used as an optimal reasoning framework for testing emptiness, containment and equivalence.
18
M. Marx · ACM Transactions on Database Systems · 2005 · 119 citations
Computing, Computer Science, Logic +14
Helmut Seidl, Thomas Schwentick, Anca Muscholl · 2003 · 73 citations
Silvano Dal Zilio, Denis Lugiez, Charles Meyssonnier · 2004 · 67 citations · Full text